Doubly Linked Lists

Doubly Linked Lists Explained

We have already discussed various types of linked lists. We covered singly linked lists, where the head node is followed by the last node pointing to NULL. We also talked about circular linked lists, which have no end but do have a designated head node. In both types, we explored basic operations like traversal, insertion, deletion, and searching.

Takeaway:

The main takeaway is that we can perform all these operations on any variant of a linked list, regardless of its structure or properties. Today, we'll look at another type of linked list and see how it relates to what we’ve learned so far.

What is a Doubly Linked List?

In a doubly linked list, each node contains a data part and two pointers: one pointing to the previous node and the other to the next node.

Below is a visual representation of a doubly linked list with three nodes, where both the end pointers point to NULL.

How is it Different from a Singly Linked List?

• A doubly linked list allows traversal in both directions. Each node contains the address of both the next node and the previous node, giving us the flexibility to move either right or left.
• A node consists of three parts: the data, a pointer to the next node, and a pointer to the previous node.
• The head node has its pointer to the previous node set to NULL.

Memory Considerations:

The extra pointer to the previous node allows for bidirectional traversal, but it also requires more memory for each node. This is a trade-off compared to a singly linked list, which only stores the data and the next node's address.

Implementation in C:

Let’s consider implementing a doubly linked list. The structure (struct Node) is similar to what we’ve seen before, with the addition of a pointer to the previous node. This new pointer, often named prev, enables travel in both directions but comes with an added memory cost for each node, now having three parts.

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

Code Snippet 1: Implementation of a doubly linked list.

Operations on a Doubly Linked List:

Insertion and deletion in a doubly linked list are performed by adjusting pointer connections, just like in a singly linked list.

The key difference here is that we need to adjust two pointers (prev and next) instead of just one (next) like we did with singly linked lists. It reflects the saying, "With great power, comes great responsibility." :)

Task:

Try implementing a traversal algorithm that:

• Traverses once to the right (using the next pointer).
• Traverses once to the left (using the prev pointer).

Print the data in both cases.

That’s all for linked lists! It has been a great segment, and we hope you’ve found it helpful. Keep an eye out for upcoming topics, and remember to revisit and revise things regularly.

Code as described/written in the all docs:

#include<stdio.h>
#include<stdlib.h>

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

void linkedListTraversal(struct Node *head){
    struct Node *ptr = head;
    do{
        printf("Element is %d\n", ptr->data);
        ptr = ptr->next;
    }while(ptr!=head);
}

struct Node * insertAtFirst(struct Node *head, int data){
    struct Node * ptr = (struct Node *) malloc(sizeof(struct Node));
    ptr->data = data;

    struct Node * p = head->next;
    while(p->next != head){
        p = p->next;
    }
    // At this point p points to the last node of this circular linked list

    p->next = ptr;
    ptr->next = head;
    head = ptr;
    return head;

}

int main(){
    
    struct Node *head;
    struct Node *second;
    struct Node *third;
    struct Node *fourth;

    // Allocate memory for nodes in the linked list in Heap
    head = (struct Node *)malloc(sizeof(struct Node));
    second = (struct Node *)malloc(sizeof(struct Node));
    third = (struct Node *)malloc(sizeof(struct Node));
    fourth = (struct Node *)malloc(sizeof(struct Node));

    // Link first and second nodes
    head->data = 4;
    head->next = second;

    // Link second and third nodes
    second->data = 3;
    second->next = third;

    // Link third and fourth nodes
    third->data = 6;
    third->next = fourth;

    // Terminate the list at the third node
    fourth->data = 1;
    fourth->next = head;

    printf("Circular Linked list before insertion\n");
    linkedListTraversal(head);
    head = insertAtFirst(head, 54);
    head = insertAtFirst(head, 58);
    head = insertAtFirst(head, 59);
    printf("Circular Linked list after insertion\n");
    linkedListTraversal(head);
    return 0;
}