# Doubly Linked Lists: One Step at a Time!

Before starting this tutorial, make sure to check out [Linked Lists: One Step at a Time!](https://blog.jyotiprakash.org/linked-lists-one-step-at-a-time) [to understand the basics of sing](https://blog.jyotiprakash.org/linked-lists-one-step-at-a-time)ly 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:

```c
#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:

```c
#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:

```c
#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:

```c
#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:

```c
#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:

```c
#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:

```c
#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:

```c
#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:

```c
#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:

```c
#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;
}
```