Create and Traverse Doubly Linked List : Algorithm and Program

A doubly linked list is a type of linked list in which each node has three parts: the data it stores, a pointer to the next node, and a pointer to the previous node. This makes it easier to traverse in both directions, unlike a singly linked list which can be traversed only forward.

In this blog, we will explore how to create a doubly linked list, traverse it, and understand it with a simple example before diving into the program.

Example to Understand Doubly Linked List

imagine you have a train with coaches:

• Each coach represents a node.
• Each coach stores passenger information (data).
• Every coach has two connectors: one to the coach in front (prev) and one to the coach behind (next).

For example, consider a train with 3 coaches:

Here:

• Coach 1’s prev is NULL (start of train), next points to Coach 2.
• Coach 2’s prev points to Coach 1, next points to Coach 3.
• Coach 3’s prev points to Coach 2, next is NULL (end of train).

This is exactly how a doubly linked list works

Why Traversing a Doubly Linked List is Needed ?

Traversing a doubly linked list is an essential operation in data structures. It allows you to visit each node in the list and access or display its data. Traversing is needed for many reasons:

1. To Display Data: Often we need to print the contents of the list for debugging or user interaction.
2. To Search for a Value: Traversal helps locate a node with specific data.
3. To Perform Operations: Insertion, deletion, or updating a node requires traversal to reach the correct position.
4. To Count Nodes: Traversing allows you to determine the number of nodes in the list.
5. To Reverse or Sort the List: Many algorithms require moving through each node, which is done via traversal.

Advantages of Doubly Linked List

• Efficient traversal in both directions.
• Easy to insert or delete nodes from both ends.
• Ideal for applications like browser history, playlist management, and undo-redo functionality.

Algorithm to Create Doubly Linked List

1. Start with an Empty List: Initialize head as NULL to indicate that the list is empty.
2. Create a Node:
   • Allocate memory dynamically for a new node newNode.
   • Assign data to newNode->data.
   • Set newNode->next and newNode->prev to NULL. As this new node does not yet have any connections in the list.
3. Insert the Node:
   • Check if the list is empty (i.e., head is NULL). If it is empty then it is the first node. Set head to newNode.
   • If the list is not empty, find the last node by traversing the list. Then, set the next pointer of the last node to newNode, and set the prev pointer of newNode to this last node.
4. Traverse the List:
   • Start from head.
   • While the head is not NULL, print its data.
   • Use a loop to visit each node until you reach a node whose next pointer is NULL (the end of the list).
   • Print the data of each node as you traverse.
   • Move to the next node by updating the current node pointer to currentNode->next.

Algorithm to Traverse Doubly Linked List

Forward Traversal:

1. Start from the head node.
2. While the current node is not NULL:
   • Print current->data.
   • Move to the next node: current = current->next.

Backward Traversal:

1. Reach the last node using forward traversal.
2. While the current node is not NULL:
   • Print current->data.
   • Move to the previous node: current = current->prev

Program to Create and Traverse Doubly Linked List

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

// Doubly linked list Structure
struct Node {
    int data;
    struct Node *next;
    struct Node *prev;
}; 

typedef struct Node Node;

// Create a new node for Doubly linked list
Node *createNode(int data) {
    Node *newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    newNode->prev = NULL;
    return newNode;
}

// Insert a node at the end of Doubly linked list
void insertAtEnd(Node** head, int data) {
    Node *newNode = createNode(data);
    if (*head == NULL) {
        *head = newNode;
        return;
    }

    Node *temp = *head;
    while (temp->next != NULL) {
        temp = temp->next;
    }
    temp->next = newNode;
    newNode->prev = temp;
}

// Traverse and print the Doubly linked list
void traverseDoublyLinkedList(Node* head) {
    Node *temp = head;
    printf("Doubly Linked List: ");
    while (temp != NULL) {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    printf("\n");
}

int main() {
    Node *head = NULL;
    insertAtEnd(&head, 5);
    insertAtEnd(&head, 10);
    insertAtEnd(&head, 15);
    insertAtEnd(&head, 20);
    traverseDoublyLinkedList(head);
    return 0;
}

Output

Doubly Linked List: 5 10 15 20 

Explanations of the Code

Node Structure:

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

typedef struct Node Node;

This code creates a structure called Node, which is like a box for storing information in a doubly linked list. Each node has three things: data, which holds the value next, which is a pointer to the next node and prev, which is a pointer to the previous box. Because of these pointers, we can move forward and backward through the list. The line typedef struct Node Node is just a shortcut so we can write Node instead of struct Node when we make a new node, making the code simpler and easier to read..

createNode Function:

// Create a new node for Doubly linked list
Node *createNode(int data) {
    Node *newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    newNode->prev = NULL;
    return newNode;
}

This function createNode is used to make a new node for a doubly linked list. It takes a number data as input and creates a new node to store it. First, it allocates memory for the node using malloc. Then it sets the node’s data to the value we pass, and sets both next and prev pointers to NULL because it is not connected to any other nodes yet. Finally, it returns the new node so we can use it in our list.

insertAtEnd Function:

// Insert a node at the end of Doubly linked list
void insertAtEnd(Node** head, int data) {
    Node *newNode = createNode(data);
    if (*head == NULL) {
        *head = newNode;
        return;
    }

    Node *temp = *head;
    while (temp->next != NULL) {
        temp = temp->next;
    }
    temp->next = newNode;
    newNode->prev = temp;
}

The insertAtEnd function is used to add a new node at the end of a doubly linked list. It first creates a new node with the given data using the createNode function. Then it checks if the list is empty (i.e., head is NULL). If the list is empty, the new node becomes the head of the list. If the list is not empty, it goes through the list using a temporary pointer temp until it reaches the last node. After reaching the last node, it links the new node to the end by setting the last node’s next pointer to the new node and the new node’s prev pointer back to the last node. This way, the new node is successfully added at the end of the list.

traverseDoublyLinkedList Function:

// Traverse and print the Doubly linked list
void traverseDoublyLinkedList(Node* head) {
    Node *temp = head;
    printf("Doubly Linked List: ");
    while (temp != NULL) {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    printf("\n");
}

The traverseDoublyLinkedList function is used to go through all the nodes in a doubly linked list and print their data. It starts with a temporary pointer temp set to the head of the list. Then, using a while loop, it moves from one node to the next until it reaches the end (when temp becomes NULL). In each step, it prints the data stored in the current node. This allows us to see all the values in the list in order from the first node to the last. Finally, it prints a new line to keep the output clean.

main Function:

int main() {
    Node *head = NULL;
    insertAtEnd(&head, 5);
    insertAtEnd(&head, 10);
    insertAtEnd(&head, 15);
    insertAtEnd(&head, 20);
    traverseDoublyLinkedList(head);
    return 0;
}

In the main function, we first create a pointer head and set it to NULL because the doubly linked list is empty at the beginning. Then, we use the insertAtEnd function to add four nodes with the values 5, 10, 15, and 20 to the end of the list, one by one. After inserting all the nodes, we call the traverseDoublyLinkedList function to print all the values in the list. Finally, the program ends by returning 0. When this program runs, it will display the list as: 5 10 15 20, showing that all the nodes were added correctly in order

Use Cases of Doubly Linked List

• Browser back/forward navigation.
• Music/Video playlist management.
• Implementing Undo/Redo functionality in applications.
• Deque (double-ended queue) implementation

Conclusion

The doubly linked list is a versatile data structure that provides bi-directional traversal and efficient node insertion/deletion. By understanding its algorithm and implementing it in C, beginners can grasp fundamental data structures concepts while improving programming skills.