What Is Doubly Linked List in Data Structure in C?

Doubly Linked List in Data Structure in C

A doubly linked list is a data structure that consists of a sequence of nodes. Each node contains three fields: the data field, and two pointers, one pointing to the previous node and one pointing to the next node. This allows traversal in both directions, unlike a singly linked list where traversal is only possible in one direction.

Advantages of Doubly Linked List

• Bidirectional traversal: As mentioned earlier, a doubly linked list allows traversal in both directions. This makes it easier to navigate through the elements, especially when there is a need to move back and forth.
• Insertion and deletion: Insertion and deletion operations are more efficient compared to arrays or singly linked lists.

  In a singly linked list, insertion or deletion requires updating multiple pointers, whereas in a doubly linked list, it can be done by adjusting just two pointers.

• Reverse traversal: With the help of the previous pointers, reverse traversal becomes possible. This can be useful in scenarios where accessing elements from the end of the list is required.

Disadvantages of Doubly Linked List

• Increased memory usage: The presence of an extra pointer for each node increases memory consumption compared to singly linked lists.
• Complexity: The presence of additional pointers complicates the implementation and maintenance of doubly linked lists compared to singly linked lists.

Doubly Linked List Implementation in C

To implement a doubly linked list in C, we need to define a structure for each node containing the necessary fields:

struct Node {
    int data;
    struct Node* prev;
    struct Node* next;
};

To create a new node, we can use the following function:

struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->prev = NULL;
    newNode->next = NULL;
    return newNode;
}

Next, we need to define functions for various operations on the doubly linked list, such as insertion, deletion, and traversal.

Insertion Operation

The insertion operation in a doubly linked list can be performed at the beginning, end, or any specific position in the list. Here’s an example of inserting a node at the beginning:

void insertAtBeginning(struct Node** headRef, int data) {
    struct Node* newNode = createNode(data);
    
    if (*headRef == NULL) {
        *headRef = newNode;
        return;
    }
    
    (*headRef)->prev = newNode;
    newNode->next = *headRef;
    
    *headRef = newNode;
}

Deletion Operation

The deletion operation can also be performed at various positions in the doubly linked list. Here’s an example of deleting a node from the beginning:

void deleteFromBeginning(struct Node** headRef) {
    if (*headRef == NULL)
        return;

    struct Node* temp = *headRef;

    if ((*headRef)->next != NULL)
        (*headRef)->next->prev = NULL;

    *headRef = (*headRef)->next;

    free(temp);
}

Traversal Operation

To traverse a doubly linked list, we can start from the head and move to the next nodes until we reach the end. Here’s an example of traversing and printing the elements:

void traverse(struct Node* head) {
    struct Node* current = head;

    while (current != NULL) {
        printf("%d ", current->data);
        current = current->next;
    }
}

These are just basic implementations of operations on a doubly linked list. There are many other operations that can be performed, such as searching for a particular element, reversing the list, and sorting the list.

Conclusion

A doubly linked list is a versatile data structure that provides bidirectional traversal and efficient insertion/deletion operations. However, it comes with increased memory usage and added complexity compared to singly linked lists. Understanding how to implement and work with doubly linked lists in C can be beneficial in solving various problems efficiently.