Doubly Linked List in C

A Doubly Linked List (DLL) is a type of linked list in which each node contains three parts: data, a pointer to the next node, and a pointer to the previous node.

Unlike a singly linked list, a doubly linked list allows traversal in both forward and backward directions.

1. Structure of Doubly Linked List

Each node contains:

• Data → Stores the value

• prev → Pointer to previous node

• next → Pointer to next node

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

The first node's prev pointer is NULL and the last node's next pointer is NULL.

2. Basic Operations

1. Insertion

2. Deletion

3. Forward Traversal

4. Backward Traversal

3. C Program to Create and Display Doubly Linked List

This program inserts nodes at the end and displays the list in forward direction.

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

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

struct Node *head = NULL;

void insert(int value) {
    struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->prev = NULL;
    newNode->next = NULL;

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

void displayForward() {
    struct Node *temp = head;
    while(temp != NULL) {
        printf("%d <-> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

int main() {
    insert(10);
    insert(20);
    insert(30);
    insert(40);

    printf("Doubly Linked List (Forward):\n");
    displayForward();

    return 0;
}

Output:
Doubly Linked List (Forward):
10 <-> 20 <-> 30 <-> 40 <-> NULL

4. Backward Traversal

To traverse backward:

1. Move to the last node.

2. Use prev pointer to move backward.

void displayBackward() {
    struct Node *temp = head;

    if(temp == NULL) return;

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

    while(temp != NULL) {
        printf("%d <-> ", temp->data);
        temp = temp->prev;
    }
    printf("NULL\n");
}

5. Deletion from Beginning

Steps:

1. Store head in temp.

2. Move head to next node.

3. Set head->prev = NULL.

4. Free old node.

void deleteBeginning() {
    if(head == NULL) return;

    struct Node *temp = head;
    head = head->next;

    if(head != NULL)
        head->prev = NULL;

    free(temp);
}

6. Advantages of Doubly Linked List

• Can traverse in both directions.

• Easy insertion and deletion from both ends.

• More flexible than singly linked list.

7. Disadvantages

• Requires extra memory for prev pointer.

• Slightly more complex implementation.

Conclusion

A Doubly Linked List is an advanced version of a linked list where each node contains pointers to both next and previous nodes.

It allows bidirectional traversal and efficient insertion and deletion operations, making it useful in applications like browser history, undo-redo functionality, and navigation systems.