Understanding Doubly Linked Lists in C: Insertion and Traversal

Understanding Doubly Linked Lists in C: Insertion and Traversal

Mastering Doubly Linked Lists in C: Efficient Insertions, Deletions, and Traversal

Tanay Toshniwal's photo
Tanay Toshniwal
·

5 min read

Table of contents

Doubly Linked Lists (DLL) are a type of linked list where each node contains two references (or pointers) — one pointing to the next node and another pointing to the previous node. This structure allows traversal in both directions, making it more flexible compared to single linked lists.

In this blog, we will walk through an implementation of a Doubly Linked List (DLL) in C, including how to insert nodes at the beginning, end, and a specific position, as well as how to traverse and print the list.

What is a Doubly Linked List?

A Doubly Linked List consists of nodes, where each node has three components:

  1. Data: The actual data or value stored in the node.

  2. Next: A pointer/reference to the next node in the list.

  3. Prev: A pointer/reference to the previous node in the list.

In a DLL, the first node's prev pointer is NULL, and the last node's next pointer is NULL. The key benefit of a doubly linked list is that you can traverse the list in both directions (forward and backward).

Code Walkthrough

Let’s break down the implementation of a doubly linked list in C, starting with defining the structure and working through different insertion methods.

  1. Defining the Node Structure

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

    Explanation:

    • Each node contains:

      • data: Stores the value of the node.

      • next: Pointer to the next node in the list.

      • pre: Pointer to the previous node in the list.

    • We define a Node structure to represent each node in the doubly linked list.

  2. Insert at the End of the List

     Node* append(Node* head, int data) {
     Node* node = (Node*)malloc(sizeof(struct Node));
     node->data = data;
     if (head == NULL) {
         node->next = NULL;
         node->pre = NULL;
         head = node;
         return head;
     }
     Node* temp = head;
     while (temp->next != NULL) {
         temp = temp->next;
     }
     temp->next = node;
     node->pre = temp;
     node->next = NULL;
     return head;
 }

    Explanation:

    • Create a New Node: A new node is created with the given data.

    • Empty List: If the list is empty (head == NULL), the new node becomes the head, and its next and pre pointers are set to NULL.

    • Traverse to the End: If the list is not empty, traverse the list until the last node (where next is NULL).

    • Update Pointers: The last node’s next pointer is updated to point to the new node, and the new node’s pre pointer is updated to point to the previous node (last node).

  3. Insert at the beginning of the List

     Node* push(Node* head, int data) {
     Node* node = (Node*)malloc(sizeof(struct Node));
     node->data = data;
     if (head == NULL) {
         node->next = NULL;
         node->pre = NULL;
         head = node;
         return head;
     }
     node->next = head;
     node->pre = NULL;
     head->pre = node;
     head = node;
     return head;
 }

    Explanation:

    • Create a New Node: A new node is created and assigned the data.

    • Empty List: If the list is empty, the new node becomes the head, and its next and pre pointers are NULL.

    • Update Pointers: If the list is not empty, the new node's next pointer is set to the current head, and the current head's pre pointer is updated to point to the new node. The new node becomes the new head of the list.

  4. Insert at a Specific Position

     Node* insert(Node* head, int data, int pos) {
     Node* node = (Node*)malloc(sizeof(struct Node));
     node->data = data;
     if (head == NULL) {
         return NULL;
     }
     Node* cur = head;
     while (cur->next != NULL && --pos > 0) {
         cur = cur->next;
     }
     Node* pre = cur->pre;
     pre->next = node;
     node->pre = pre;
     node->next = cur;
     cur->pre = node;
     return head;
 }

    Explanation:

    • Create a New Node: A new node is created with the given data.

    • Traverse to the Desired Position: Traverse the list until the node at the desired position is reached (pos decreases as we move).

    • Update Pointers: The pre the pointer of the node at the given position is updated to point to the new node and the next the pointer of the previous node is updated to point to the new node. Similarly, the new node’s next pointer is updated to point to the current node, and the current node’s pre pointer is updated to point to the new node.

  5. Print the List

     void print(Node* head) {
     if (head == NULL) {
         return;
     }
     Node* temp = head;
     while (temp != NULL) {
         printf("%d ", temp->data);
         temp = temp->next;
     }
 }

    Explanation:

    • Traverse the List: Starting from the head, print each node’s data.

    • Loop Until the End: Continue traversing and printing the nodes until temp is NULL.

  6. Main Function

     int main() {
     Node* head = NULL;
     int n;
     scanf("%d", &n);
     while (n--) {
         int t;
         scanf("%d", &t);
         head = push(head, t);
     }

     head = insert(head ,69, 3);

     print(head);
     return 0;
 }

    Explanation:

    1. Input the Number of Nodes: Read the number of elements (n) to be inserted.

    2. Insert Nodes at the Beginning: Use the push function to insert nodes at the beginning.

    3. Insert at a Specific Position: Use the insert function to insert the value 69 at position 3.

    4. Print the List: Finally, the print function is called to display the elements of the list.

Example Input and Output

Input:

5
10 20 30 40 50

Output:

50 40 30 20 10 69

Explanation:

  1. Insert the elements 10, 20, 30, 40, and 50 at the beginning.

  2. Insert the element 69 at the position 3.

  3. Print the updated list: 50 40 30 20 10 69.

Advantages of Doubly Linked Lists

  1. Bidirectional Traversal: DLLs allow traversal in both directions — from head to tail and tail to head.

  2. Efficient Insertion/Deletion: Inserting or deleting a node at the beginning or end is efficient.

  3. Flexible Memory Management: DLLs can grow and shrink dynamically, optimizing memory usage.

Conclusion

Doubly Linked Lists are powerful data structures used for various applications where bidirectional traversal and efficient insertion/deletion operations are required. In this blog, we’ve explored how to implement a DLL in C, including insertion at the beginning, end, and specific positions, as well as traversing and printing the list.

By mastering DLLs, you can efficiently solve problems that involve linked data structures in real-world applications. Happy coding! 😊

References

  1. Find the code for the above explanation here.
DSAdata structuresProgramming BlogsalgorithmsC