Create and Traverse Doubly Linked List : Algo and Program

by

A doubly linked list is a type of linked list where each node is interconnected in both directions. Means each node keep the address of its previous node and next node.

In this tutorial we will learn how you can create the Doubly Linked List, Also will see its algorithm and program in C. This tutorial will help you to understand the topic and prepare for your interviews and semester exams.

Algorithm to Create and Traverse 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.

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

Create and Traverse Doubly Linked List Program Explanations

Node Structure:

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

typedef struct Node Node;

The struct Node defines the structure of each node in the doubly linked list. It contains an int data to store the value, and two pointers next and prev pointing to the next and previous nodes, respectively.

The typedef is used to define Node as an alias for struct Node at the beginning. After that you can simply use Node to refer to this structure.

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 creates a new node with the given data. It allocates memory for a new node, sets its data, and initializes its next and prev pointers to NULL.

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;
}

This function inserts a new node at the end of the list. It first creates a new node with the given data. If the list is empty (head is NULL), it sets head to the new node. Otherwise, it traverses to the end of the list and updates the pointers to insert the new node.

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");
}

This function prints the data in each node of the list. Starting from head, it goes through each node until it reaches the end, printing the data stored in each node.

main Function:

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

The main function demonstrates creating a doubly linked list by inserting nodes and then traversing the list to print its contents. It starts with an empty list, inserts three nodes (5, 10, 15, 20), and then traverses the list to print these values.

Hope this tutorial helped you to understand how you can create and traverse the linked list.