Doubly Linked Lists: One Step at a Time!

Jyotiprakash MishraJyotiprakash Mishra
12 min read

Before starting this tutorial, make sure to check out Linked Lists: One Step at a Time! to understand the basics of singly linked lists first.

First Step: What is a doubly linked list node made up of?

Explanation:

  • A doubly linked list is made up of nodes, just like a singly linked list.

  • Each node contains some data and TWO pointers: one to the next node and one to the previous node.

  • This allows traversal in both directions (forward and backward).

  • Define a structure for the node that includes an integer and pointers to both next and previous nodes.

Code:

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

// Define the doubly linked list node structure
struct Node {
    int data;           // Integer data
    struct Node* next;  // Pointer to the next node
    struct Node* prev;  // Pointer to the previous node
};

Second Step: Creating Two Nodes and Linking Them

Explanation:

  • Create two nodes.

  • Set the first node's next pointer to the second node.

  • Set the second node's previous pointer to the first node.

  • Set the first node's previous pointer to NULL (start of list).

  • Set the second node's next pointer to NULL (end of list).

  • Assign values to the nodes using scanf.

Code:

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

// Define the node structure
struct Node {
    int data;
    struct Node* next;
    struct Node* prev;
};

int main() {
    struct Node* first = (struct Node*)malloc(sizeof(struct Node));
    struct Node* second = (struct Node*)malloc(sizeof(struct Node));

    // Get values from the user
    printf("Enter value for the first node: ");
    scanf("%d", &first->data);
    first->prev = NULL;
    first->next = second;

    printf("Enter value for the second node: ");
    scanf("%d", &second->data);
    second->prev = first;
    second->next = NULL;

    // Free allocated memory
    free(first);
    free(second);

    return 0;
}

Third Step: Creating Three Nodes and Linking Them

Explanation:

  • Create three nodes.

  • Link them in a chain where each node points to the next and previous nodes.

  • The first node's previous pointer is NULL.

  • The last node's next pointer is NULL.

Code:

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

// Define the node structure
struct Node {
    int data;
    struct Node* next;
    struct Node* prev;
};

int main() {
    struct Node* first = (struct Node*)malloc(sizeof(struct Node));
    struct Node* second = (struct Node*)malloc(sizeof(struct Node));
    struct Node* third = (struct Node*)malloc(sizeof(struct Node));

    // Get values from the user
    printf("Enter value for the first node: ");
    scanf("%d", &first->data);
    first->prev = NULL;
    first->next = second;

    printf("Enter value for the second node: ");
    scanf("%d", &second->data);
    second->prev = first;
    second->next = third;

    printf("Enter value for the third node: ");
    scanf("%d", &third->data);
    third->prev = second;
    third->next = NULL;

    // Free allocated memory
    free(first);
    free(second);
    free(third);

    return 0;
}

Fourth Step: Creating a Doubly Linked List of 10 Nodes in a Loop

Explanation:

  • Create a doubly linked list with 10 nodes using a loop.

  • Use a head pointer to point to the first node.

  • Use temporary pointers to build the list.

  • Each new node must link to the previous node (if any).

  • Use scanf to get values for each node from the user.

Code:

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

// Define the node structure
struct Node {
    int data;
    struct Node* next;
    struct Node* prev;
};

int main() {
    struct Node* head = NULL;    // Head of the list
    struct Node* temp = NULL;    // Temporary pointer
    struct Node* newNode = NULL; // Pointer to new node

    // Create 10 nodes
    for (int i = 0; i < 10; i++) {
        newNode = (struct Node*)malloc(sizeof(struct Node));
        printf("Enter value for node %d: ", i + 1);
        scanf("%d", &newNode->data);
        newNode->next = NULL;
        newNode->prev = NULL;

        if (head == NULL) {
            // If the list is empty, set head to the new node
            head = newNode;
        } else {
            // Otherwise, link the new node to the last node
            temp->next = newNode;
            newNode->prev = temp;
        }

        // Move the temp pointer to the new node
        temp = newNode;
    }

    return 0;
}

Fifth Step: Printing the Doubly Linked List (Forward and Backward)

Explanation:

  • Write functions to print the list in both directions.

  • For forward traversal, start from head and move using next pointers.

  • For backward traversal, first find the tail, then move using prev pointers.

  • Print the data of each node.

Code:

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

// Define the node structure
struct Node {
    int data;
    struct Node* next;
    struct Node* prev;
};

// Function to print the linked list forward
void printListForward(struct Node* head) {
    struct Node* temp = head;
    printf("Forward: ");
    while (temp != NULL) {
        printf("%d <-> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

// Function to print the linked list backward
void printListBackward(struct Node* head) {
    struct Node* temp = head;

    // Find the tail node
    if (temp == NULL) return;

    while (temp->next != NULL) {
        temp = temp->next;
    }

    // Print from tail to head
    printf("Backward: ");
    while (temp != NULL) {
        printf("%d <-> ", temp->data);
        temp = temp->prev;
    }
    printf("NULL\n");
}

int main() {
    struct Node* head = NULL;
    struct Node* temp = NULL;
    struct Node* newNode = NULL;

    // Create 5 nodes for demonstration
    for (int i = 0; i < 5; i++) {
        newNode = (struct Node*)malloc(sizeof(struct Node));
        printf("Enter value for node %d: ", i + 1);
        scanf("%d", &newNode->data);
        newNode->next = NULL;
        newNode->prev = NULL;

        if (head == NULL) {
            head = newNode;
        } else {
            temp->next = newNode;
            newNode->prev = temp;
        }

        temp = newNode;
    }

    // Print the list in both directions
    printListForward(head);
    printListBackward(head);

    // Free allocated memory
    temp = head;
    while (temp != NULL) {
        struct Node* next = temp->next;
        free(temp);
        temp = next;
    }

    return 0;
}

Sixth Step: Adding a Node to the Beginning

Explanation:

  • Write a function that takes a double pointer to the head of the list.

  • Create a new node, assign its value from the function parameter.

  • Make the new node's next pointer point to the current head.

  • If head exists, update its previous pointer to point to the new node.

  • Update the head to point to the new node.

  • Use printListForward to print the updated list.

Code:

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

// Define the node structure
struct Node {
    int data;
    struct Node* next;
    struct Node* prev;
};

// Function to print the linked list forward
void printListForward(struct Node* head) {
    struct Node* temp = head;
    printf("Forward: ");
    while (temp != NULL) {
        printf("%d <-> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

// Function to add a node at the beginning of the list
void addNodeAtBeginning(struct Node** pointerToHead, int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->next = *pointerToHead;
    newNode->prev = NULL;

    if (*pointerToHead != NULL) {
        (*pointerToHead)->prev = newNode;
    }

    *pointerToHead = newNode;
}

int main() {
    struct Node* head = NULL;
    struct Node* temp = NULL;
    struct Node* newNode = NULL;

    // Create 3 nodes
    for (int i = 0; i < 3; i++) {
        newNode = (struct Node*)malloc(sizeof(struct Node));
        printf("Enter value for node %d: ", i + 1);
        scanf("%d", &newNode->data);
        newNode->next = NULL;
        newNode->prev = NULL;

        if (head == NULL) {
            head = newNode;
        } else {
            temp->next = newNode;
            newNode->prev = temp;
        }

        temp = newNode;
    }

    // Add a new node at the beginning
    int newValue;
    printf("Enter value for the new node at the beginning: ");
    scanf("%d", &newValue);
    addNodeAtBeginning(&head, newValue);

    // Print the list
    printListForward(head);

    // Free allocated memory
    temp = head;
    while (temp != NULL) {
        struct Node* next = temp->next;
        free(temp);
        temp = next;
    }

    return 0;
}

Seventh Step: Inserting a Node After the Nth Node

Explanation:

  • Write a function that takes the head of the list, a position n, and a value.

  • Traverse the list to find the nth node.

  • If the nth node exists, create a new node.

  • Update the links: new node's prev points to nth node, new node's next points to nth node's next.

  • If nth node's next exists, update its prev to point to new node.

  • Update nth node's next to point to new node.

Code:

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

// Define the node structure
struct Node {
    int data;
    struct Node* next;
    struct Node* prev;
};

// Function to print the linked list forward
void printListForward(struct Node* head) {
    struct Node* temp = head;
    printf("Forward: ");
    while (temp != NULL) {
        printf("%d <-> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

// Function to insert a node after the nth node
void insertNodeAfterNth(struct Node* head, int n, int value) {
    struct Node* temp = head;

    // Traverse to the nth node
    for (int i = 0; i < n; i++) {
        if (temp == NULL) return; // If n is beyond the end of the list
        temp = temp->next;
    }

    if (temp != NULL) {
        struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
        newNode->data = value;
        newNode->next = temp->next;
        newNode->prev = temp;

        if (temp->next != NULL) {
            temp->next->prev = newNode;
        }

        temp->next = newNode;
    }
}

int main() {
    struct Node* head = NULL;

    // Create a simple list with 3 nodes for testing
    head = (struct Node*)malloc(sizeof(struct Node));
    head->data = 1;
    head->prev = NULL;

    head->next = (struct Node*)malloc(sizeof(struct Node));
    head->next->data = 2;
    head->next->prev = head;

    head->next->next = (struct Node*)malloc(sizeof(struct Node));
    head->next->next->data = 3;
    head->next->next->prev = head->next;
    head->next->next->next = NULL;

    printf("Original list:\n");
    printListForward(head);

    // Insert a new node after the nth node
    int n = 1, value = 99;
    insertNodeAfterNth(head, n, value);

    printf("After inserting %d after position %d:\n", value, n);
    printListForward(head);

    // Free allocated memory
    struct Node* temp = head;
    while (temp != NULL) {
        struct Node* next = temp->next;
        free(temp);
        temp = next;
    }

    return 0;
}

Eighth Step: Deleting the Head Node

Explanation:

  • Write a function that takes a double pointer to the head of the list.

  • If the list is not empty, save the current head.

  • Make the head point to the second node.

  • If the new head exists, update its prev pointer to NULL.

  • Free the memory of the old head node.

Code:

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

// Define the node structure
struct Node {
    int data;
    struct Node* next;
    struct Node* prev;
};

// Function to print the linked list forward
void printListForward(struct Node* head) {
    struct Node* temp = head;
    printf("Forward: ");
    while (temp != NULL) {
        printf("%d <-> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

// Function to delete the head node
void deleteHeadNode(struct Node** head) {
    if (*head != NULL) {
        struct Node* temp = *head;
        *head = (*head)->next;

        if (*head != NULL) {
            (*head)->prev = NULL;
        }

        free(temp);
    }
}

int main() {
    struct Node* head = NULL;

    // Create a simple list with 3 nodes for testing
    head = (struct Node*)malloc(sizeof(struct Node));
    head->data = 1;
    head->prev = NULL;

    head->next = (struct Node*)malloc(sizeof(struct Node));
    head->next->data = 2;
    head->next->prev = head;

    head->next->next = (struct Node*)malloc(sizeof(struct Node));
    head->next->next->data = 3;
    head->next->next->prev = head->next;
    head->next->next->next = NULL;

    // Print the list
    printf("Original list:\n");
    printListForward(head);

    // Delete the head node
    deleteHeadNode(&head);

    // Print the list again
    printf("After deleting head:\n");
    printListForward(head);

    // Free allocated memory
    struct Node* temp = head;
    while (temp != NULL) {
        struct Node* next = temp->next;
        free(temp);
        temp = next;
    }

    return 0;
}

Ninth Step: Deleting a Node with a Specific Value

Explanation:

  • Write a function that takes a double pointer to the head of the list and a value.

  • Traverse the list to find the node with the given value.

  • If found, update the links to bypass the node.

  • Handle three cases: deleting head node, deleting middle node, deleting tail node.

  • Free the memory of the deleted node.

Code:

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

// Define the node structure
struct Node {
    int data;
    struct Node* next;
    struct Node* prev;
};

// Function to print the linked list forward
void printListForward(struct Node* head) {
    struct Node* temp = head;
    printf("Forward: ");
    while (temp != NULL) {
        printf("%d <-> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

// Function to delete a node with a specific value
void deleteNodeWithValue(struct Node** head, int value) {
    struct Node* temp = *head;

    // Search for the node with the given value
    while (temp != NULL && temp->data != value) {
        temp = temp->next;
    }

    // If the value was not found
    if (temp == NULL) return;

    // If it's the head node
    if (temp == *head) {
        *head = temp->next;
        if (*head != NULL) {
            (*head)->prev = NULL;
        }
    }
    // If it's not the head node
    else {
        // Update the previous node's next pointer
        if (temp->prev != NULL) {
            temp->prev->next = temp->next;
        }

        // Update the next node's prev pointer
        if (temp->next != NULL) {
            temp->next->prev = temp->prev;
        }
    }

    free(temp);
}

int main() {
    struct Node* head = NULL;

    // Create a simple list with 3 nodes for testing
    head = (struct Node*)malloc(sizeof(struct Node));
    head->data = 1;
    head->prev = NULL;

    head->next = (struct Node*)malloc(sizeof(struct Node));
    head->next->data = 2;
    head->next->prev = head;

    head->next->next = (struct Node*)malloc(sizeof(struct Node));
    head->next->next->data = 3;
    head->next->next->prev = head->next;
    head->next->next->next = NULL;

    // Print the list
    printf("Original list:\n");
    printListForward(head);

    // Delete a node with a specific value
    int valueToDelete = 2;
    deleteNodeWithValue(&head, valueToDelete);

    // Print the list again
    printf("After deleting node with value %d:\n", valueToDelete);
    printListForward(head);

    // Free allocated memory
    struct Node* temp = head;
    while (temp != NULL) {
        struct Node* next = temp->next;
        free(temp);
        temp = next;
    }

    return 0;
}

Bonus Step: Reversing a Doubly Linked List

Explanation:

  • Write a function that reverses the entire doubly linked list.

  • Traverse the list and swap the next and prev pointers for each node.

  • Update the head to point to the last node (which becomes the new first node).

Code:

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

// Define the node structure
struct Node {
    int data;
    struct Node* next;
    struct Node* prev;
};

// Function to print the linked list forward
void printListForward(struct Node* head) {
    struct Node* temp = head;
    printf("Forward: ");
    while (temp != NULL) {
        printf("%d <-> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

// Function to reverse the doubly linked list
void reverseList(struct Node** head) {
    struct Node* temp = NULL;
    struct Node* current = *head;

    // Swap next and prev for all nodes
    while (current != NULL) {
        temp = current->prev;
        current->prev = current->next;
        current->next = temp;
        current = current->prev;
    }

    // Before changing head, check for empty list or single node
    if (temp != NULL) {
        *head = temp->prev;
    }
}

int main() {
    struct Node* head = NULL;

    // Create a simple list with 4 nodes for testing
    head = (struct Node*)malloc(sizeof(struct Node));
    head->data = 1;
    head->prev = NULL;

    head->next = (struct Node*)malloc(sizeof(struct Node));
    head->next->data = 2;
    head->next->prev = head;

    head->next->next = (struct Node*)malloc(sizeof(struct Node));
    head->next->next->data = 3;
    head->next->next->prev = head->next;

    head->next->next->next = (struct Node*)malloc(sizeof(struct Node));
    head->next->next->next->data = 4;
    head->next->next->next->prev = head->next->next;
    head->next->next->next->next = NULL;

    // Print the original list
    printf("Original list:\n");
    printListForward(head);

    // Reverse the list
    reverseList(&head);

    // Print the reversed list
    printf("Reversed list:\n");
    printListForward(head);

    // Free allocated memory
    struct Node* temp = head;
    while (temp != NULL) {
        struct Node* next = temp->next;
        free(temp);
        temp = next;
    }

    return 0;
}
0
Subscribe to my newsletter

Read articles from Jyotiprakash Mishra directly inside your inbox. Subscribe to the newsletter, and don't miss out.

data structureslinked listDSA#DoublyLinkedListdata structure and algorithms

Written by

Jyotiprakash Mishra
Jyotiprakash Mishra

I am Jyotiprakash, a deeply driven computer systems engineer, software developer, teacher, and philosopher. With a decade of professional experience, I have contributed to various cutting-edge software products in network security, mobile apps, and healthcare software at renowned companies like Oracle, Yahoo, and Epic. My academic journey has taken me to prestigious institutions such as the University of Wisconsin-Madison and BITS Pilani in India, where I consistently ranked among the top of my class. At my core, I am a computer enthusiast with a profound interest in understanding the intricacies of computer programming. My skills are not limited to application programming in Java; I have also delved deeply into computer hardware, learning about various architectures, low-level assembly programming, Linux kernel implementation, and writing device drivers. The contributions of Linus Torvalds, Ken Thompson, and Dennis Ritchie—who revolutionized the computer industry—inspire me. I believe that real contributions to computer science are made by mastering all levels of abstraction and understanding systems inside out. In addition to my professional pursuits, I am passionate about teaching and sharing knowledge. I have spent two years as a teaching assistant at UW Madison, where I taught complex concepts in operating systems, computer graphics, and data structures to both graduate and undergraduate students. Currently, I am an assistant professor at KIIT, Bhubaneswar, where I continue to teach computer science to undergraduate and graduate students. I am also working on writing a few free books on systems programming, as I believe in freely sharing knowledge to empower others.