Doubly Linked List

A Doubly Linked List (DLL) is a linear data structure where each node is connected in two directions. Unlike a singly linked list, a doubly linked list stores two links inside every node:

• A pointer to the next node
• A pointer to the previous node

This two-way connection allows traversal in both forward and backward directions, making the structure more flexible for insertion, deletion, and navigation-based operations.

Structure of a Node

Each node in a doubly linked list generally contains three parts:

1. Previous Pointer (prev) – Stores the address of the previous node.
2. Data Field – Stores the actual value.
3. Next Pointer (next) – Stores the address of the next node.

Example representation:

NULL ← [10] ⇄ [20] ⇄ [30] → NULL

• The first node has NULL in its prev field.
• The last node has NULL in its next field.

Memory Representation

In memory, nodes of a doubly linked list are stored at different locations rather than continuously.

Example:

Address    Prev    Data    Next
1000       NULL     10     2000
2000       1000     20     3000
3000       2000     30     NULL

The head pointer stores the address of the first node.

Because each node contains two pointers, doubly linked lists require more memory compared to singly linked lists.

Operations in Doubly Linked List

1. Traversal

Traversal means visiting nodes one by one.

Forward Traversal

Start from the head node and move using the next pointer.

HEAD → [10] ⇄ [20] ⇄ [30] → NULL

Traversal order:

10 → 20 → 30

Backward Traversal

Start from the tail node and move using the prev pointer.

NULL ← [10] ⇄ [20] ⇄ [30] ← TAIL

Traversal order:

30 → 20 → 10

Backward traversal is one of the biggest advantages of a DLL.

2. Insertion Operations

Insert at Beginning

A new node becomes the first node of the list.

Steps

1. Create a new node.
2. Set newNode->next = head.
3. Set newNode->prev = NULL.
4. Update old head's prev pointer.
5. Move head to the new node.

Example

Before insertion:

HEAD → [20] ⇄ [30]

Insert 10

After insertion:

HEAD → [10] ⇄ [20] ⇄ [30]

Insert at End

The new node is attached after the last node.

Steps

1. Create a new node.
2. Traverse to the last node.
3. Connect the last node with the new node.
4. Set the new node's next pointer to NULL.

Example

Before insertion:

HEAD → [10] ⇄ [20]

Insert 30

After insertion:

HEAD → [10] ⇄ [20] ⇄ [30]

Insert at Specific Position

A node can also be inserted between two existing nodes.

Example

Before insertion:

HEAD → [10] ⇄ [30]

Insert 20 at position 2.

After insertion:

HEAD → [10] ⇄ [20] ⇄ [30]

3. Deletion Operations

Delete from Beginning

The first node is removed and the second node becomes the new head.

Example

Before deletion:

HEAD → [10] ⇄ [20] ⇄ [30]

After deletion:

HEAD → [20] ⇄ [30]

Delete from End

The last node is removed from the list.

Example

Before deletion:

HEAD → [10] ⇄ [20] ⇄ [30]

After deletion:

HEAD → [10] ⇄ [20]

Delete from Specific Position

A node located at a particular position can be deleted by updating neighboring pointers.

Example

Before deletion:

HEAD → [10] ⇄ [20] ⇄ [30]

Delete node 20

After deletion:

HEAD → [10] ⇄ [30]

4. Searching

Searching means finding a specific element in the list.

Steps

1. Start from the head node.
2. Compare each node value with the target value.
3. If matched, return its position.
4. Continue until the value is found or the list ends.

Example

HEAD → [10] ⇄ [20] ⇄ [30]

Search 30

Result:

Found at position 3

Advantages of Doubly Linked List

1. Bidirectional Traversal

Nodes can be traversed in both directions.

2. Easier Deletion

Deletion becomes simpler because access to the previous node is directly available.

3. Efficient Insertions

Insertion at both ends can be performed efficiently.

4. Useful in Real Applications

DLLs are used in:

• Browser history navigation
• Undo and redo operations
• Music playlist management
• Image viewers
• Navigation systems

Disadvantages of Doubly Linked List

1. Extra Memory Usage

Each node stores two pointers, increasing memory consumption.

2. Complex Pointer Management

Both prev and next pointers must be updated carefully.

3. Slower Random Access

Unlike arrays, direct indexing is not possible.

Time Complexity

If a tail pointer is maintained, insertion and deletion at the end can also become O(1).

Space Complexity

Each node stores:

• Data field
• Previous pointer
• Next pointer

Therefore, the total space complexity for n nodes is:

O(n)

C Program for Doubly Linked List

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

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

struct Node* head = NULL;

struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->prev = NULL;
    newNode->next = NULL;
    return newNode;
}

void insertAtBeginning(int data) {
    struct Node* newNode = createNode(data);

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

    head = newNode;
}

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

    while(temp != NULL) {
        printf("%d ", temp->data);
        temp = temp->next;
    }
}

int main() {
    insertAtBeginning(30);
    insertAtBeginning(20);
    insertAtBeginning(10);

    displayForward();

    return 0;
}

Conclusion

A Doubly Linked List is an important dynamic data structure that allows movement in both forward and backward directions. Although it uses extra memory because of the additional pointer, it provides flexible insertion and deletion operations. Due to these advantages, doubly linked lists are widely used in systems that require navigation, history tracking, and dynamic memory handling.