Doubly Linked List

As the name recommends, the doubly connected rundown contains two pointers. We can characterize the doubly connected rundown as a straight information structure with three sections: the information part and the other two location part.

All in all, a doubly connected rundown is a rundown that has three sections in a solitary hub, incorporates one information section, a pointer to its past hub, and a pointer to the following hub.

Assume we have three hubs, and the location of these hubs are 100, 200 and 300, separately. The portrayal of these hubs in a doubly-connected rundown is appeared beneath:

As we can see in the above figure, the hub in a doubly-connected rundown has two location parts; one section stores the location of the following while the other piece of the hub stores the past hub's location.

The underlying hub in the doubly connected rundown has the NULL incentive in the location part, which gives the location of the past hub.

Memory Representation of a doubly linked list

Memory Representation of a doubly connected rundown is appeared in the accompanying picture. For the most part, doubly connected rundown burns-through more space for each hub and in this way, causes more sweeping fundamental activities, for example, inclusion and erasure.

We can without much of a stretch control the components of the rundown since the rundown keeps up pointers in both the ways (forward and in reverse).

In this picture, the principal component of the rundown that is for example 13 put away at address 1. The head pointer focuses to the beginning location 1. Since this is the primary component being added to the rundown along these lines the prev of the rundown contains invalid.

The following hub of the rundown lives at address 4 accordingly the first hub contains 4 in quite a while next pointer. We can cross the rundown in this manner until we discover any hub containing invalid or - 1 in its next part.

Operations in Doubly Linked List

1. Traversal (Forward and Backward)

Traversal in a doubly linked list means visiting each node one by one to access or process its data, either from the beginning (head) or from the end (tail).

Since each node in a DLL contains both next and prev pointers, traversal can be done in two directions:

Forward Traversal

You begin from the head node and follow the next pointers until you reach the end (NULL). It display list elements from first to last.

Perform actions like summing values, searching, counting nodes, etc.

Example

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

• Start at HEAD.
• Visit 10 → next → 20 → next → 30 → next → 40 → next → NULL

Backward Traversal

You begin from the tail node and follow the prev pointers until you reach the start (NULL).

Useful for operations where reverse order matters (e.g., undo features). Helpful in applications like backtracking, playlists, navigation, etc.

Example

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

• Start at TAIL.
• Visit 40 → prev → 30 → prev → 20 → prev → 10 → prev → NULL

2. Insertion

Insertion in a DLL involves creating a new node and correctly adjusting the prev and next pointers so that the list maintains its structure.

Unlike singly linked lists, DLL allows insertion from both directions, making it more flexible.

Insert at Beginning (Head)

A new node is added before the current head, becoming the new head of the list.

• Create a new node and set its data.
• Set newNode->next = head.
• Set newNode->prev = NULL.
• If the list is not empty, set head->prev = newNode.
• Update head = newNode.

Example: Insert 5 into

HEAD → [10] ⇄ [20]

Result

HEAD → [5] ⇄ [10] ⇄ [20]

Insert at End (Tail)

The new node is added after the last node, becoming the new tail.

• Create a new node and set its data.
• Traverse to the last node (tail).
• Set lastNode->next = newNode.
• Set newNode->prev = lastNode and newNode->next = NULL.

Example: Insert 30 into

HEAD → [10] ⇄ [20]

Result

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

Insert at a Specific Position

Insert a node at a given index (1-based or 0-based depending on implementation).

• Traverse to the node just before the desired position.
• Create a new node and set its data.
• Set newNode->next = current->next
• Set newNode->prev = current
• Update the neighboring nodes:
  • current->next->prev = newNode
  • current->next = newNode

Example: Insert 15 at position 2

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

Result

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

3. Deletion

Deletion in a DLL involves removing a node and carefully updating the adjacent nodes' prev and next pointers to maintain the structure of the list.

There are three main types:

Delete at Beginning

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

• Check if list is empty (head is NULL).
• Store head in a temporary pointer.
• Move head to head->next.
• If head is not NULL, set head->prev = NULL.
• Free the original head node.

Example: Delete first node in

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

Result

HEAD → [20] ⇄ [30]

Delete at End

The last node is removed, and the second last node becomes the new tail.

• Traverse to the last node.
• Store it in a temporary pointer.
• Move to its previous node: temp->prev.
• Set temp->prev->next = NULL.
• Free the last node.

Example: Delete last node in

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

Result

HEAD → [10] ⇄ [20]

Delete at a Specific Position

A node at a given index (middle of the list) is removed.

• Traverse to the desired node (position pos).
• Set current->prev->next = current->next.
• Set current->next->prev = current->prev.
• Free the current node.

Must handle special cases:

• Position = 1 → delete head
• Position = last → delete tail

Example: Delete node 20

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

Result

HEAD → [10] ⇄ [30]

4. Search

The search operation in a Doubly Linked List (DLL) involves locating a node that contains a specific key or value.

Since a DLL is a sequential data structure, we typically search from either the head (beginning) or the tail (end) depending on the direction of traversal.

• Start from head.
• Compare node’s data with key.
• If match, return position.

Example: Search for 30 in

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

Result: Found at position 3.

Operations Table of Doubly Link List

Advantages of Doubly Linked Lists

Bidirectional Traversal

Facilitates moving back and forth, unlike singly linked lists.

Easier Deletion

A node can be deleted without needing to traverse from the head (as long as we have a pointer to it).

Flexible Insertions

Insertions and deletions can occur more efficiently compared to arrays (no shifting needed).

Useful in Complex Data Structures

Acts as a building block for advanced data structures like:

• Deques
• Browser history
• Undo-redo systems

Disadvantages of Doubly Linked Lists

More Memory Usage

Each node uses extra space for the prev pointer.

More Pointer Handling

Increases implementation complexity (must manage both next and prev).

Slower than Arrays for Index Access

Arrays provide direct access by index, DLLs require traversal.

Applications of Doubly Linked Lists

Navigation systems (e.g., forward/backward in browser history)

Undo/Redo functionality in text editors and IDEs

Multilevel menus

Playlist management in music/video players

Memory management in operating systems (free lists)

Time and Space Complexity of Doubly Linked List

Time Complexity

• Insertion and deletion at the head are always O(1).
• Insertion/deletion at the tail or a specific position requires traversal → O(n) unless a tail pointer is maintained.
• Search and traversal are O(n) as each node must be visited.
• DLL does not support random access, so no O(1) access like arrays.

Space Complexity

• Each node uses space for:
  • data (O(1))
  • prev pointer (O(1))
  • next pointer (O(1))
• So, for n nodes, total space = O(n)

Doubly Linked List Implementation in C Programming

Here's a complete C program that implements all basic operations on a Doubly Linked List (DLL), including:

• Insertion at beginning, end, and position
• Deletion from beginning, end, and position
• Forward and backward traversal
• Search operation

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

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

// Head pointer
struct Node* head = NULL;

// Function to create a new node
struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->prev = newNode->next = NULL;
    return newNode;
}

// Insertion at beginning
void insertAtBeginning(int data) {
    struct Node* newNode = createNode(data);
    if (head != NULL) {
        newNode->next = head;
        head->prev = newNode;
    }
    head = newNode;
    printf("Inserted %d at the beginning\n", data);
}

// Insertion at end
void insertAtEnd(int data) {
    struct Node* newNode = createNode(data);
    if (head == NULL) {
        head = newNode;
        printf("Inserted %d at the end\n", data);
        return;
    }
    struct Node* temp = head;
    while (temp->next != NULL)
        temp = temp->next;
    temp->next = newNode;
    newNode->prev = temp;
    printf("Inserted %d at the end\n", data);
}

// Insertion at specific position (1-based index)
void insertAtPosition(int data, int pos) {
    if (pos == 1) {
        insertAtBeginning(data);
        return;
    }
    struct Node* temp = head;
    for (int i = 1; temp != NULL && i < pos - 1; i++)
        temp = temp->next;
    if (temp == NULL) {
        printf("Position out of range\n");
        return;
    }
    struct Node* newNode = createNode(data);
    newNode->next = temp->next;
    newNode->prev = temp;
    if (temp->next != NULL)
        temp->next->prev = newNode;
    temp->next = newNode;
    printf("Inserted %d at position %d\n", data, pos);
}

// Delete from beginning
void deleteFromBeginning() {
    if (head == NULL) {
        printf("List is empty\n");
        return;
    }
    struct Node* temp = head;
    head = head->next;
    if (head != NULL)
        head->prev = NULL;
    printf("Deleted %d from beginning\n", temp->data);
    free(temp);
}

// Delete from end
void deleteFromEnd() {
    if (head == NULL) {
        printf("List is empty\n");
        return;
    }
    struct Node* temp = head;
    if (temp->next == NULL) {
        printf("Deleted %d from end\n", temp->data);
        free(temp);
        head = NULL;
        return;
    }
    while (temp->next != NULL)
        temp = temp->next;
    temp->prev->next = NULL;
    printf("Deleted %d from end\n", temp->data);
    free(temp);
}

// Delete from specific position (1-based index)
void deleteFromPosition(int pos) {
    if (head == NULL) {
        printf("List is empty\n");
        return;
    }
    struct Node* temp = head;
    if (pos == 1) {
        deleteFromBeginning();
        return;
    }
    for (int i = 1; temp != NULL && i < pos; i++)
        temp = temp->next;
    if (temp == NULL) {
        printf("Position out of range\n");
        return;
    }
    temp->prev->next = temp->next;
    if (temp->next != NULL)
        temp->next->prev = temp->prev;
    printf("Deleted %d from position %d\n", temp->data, pos);
    free(temp);
}

// Forward traversal
void traverseForward() {
    struct Node* temp = head;
    printf("Forward: ");
    while (temp != NULL) {
        printf("%d ", temp->data);
        if (temp->next == NULL) break; // Stop here to use in backward
        temp = temp->next;
    }
    printf("\n");
}

// Backward traversal
void traverseBackward() {
    struct Node* temp = head;
    if (temp == NULL) {
        printf("List is empty\n");
        return;
    }
    while (temp->next != NULL)
        temp = temp->next;
    printf("Backward: ");
    while (temp != NULL) {
        printf("%d ", temp->data);
        temp = temp->prev;
    }
    printf("\n");
}

// Search
void search(int key) {
    struct Node* temp = head;
    int pos = 1;
    while (temp != NULL) {
        if (temp->data == key) {
            printf("Found %d at position %d\n", key, pos);
            return;
        }
        pos++;
        temp = temp->next;
    }
    printf("%d not found in the list\n", key);
}

// Main function
int main() {
    insertAtBeginning(30);
    insertAtBeginning(20);
    insertAtBeginning(10);
    traverseForward();
    traverseBackward();

    insertAtEnd(40);
    insertAtEnd(50);
    traverseForward();

    insertAtPosition(25, 3);
    traverseForward();

    deleteFromBeginning();
    deleteFromEnd();
    deleteFromPosition(3);
    traverseForward();

    search(25);
    search(40);

    return 0;
}

Output

Inserted 30 at the beginning
Inserted 20 at the beginning
Inserted 10 at the beginning
Forward: 10 20 30 
Backward: 30 20 10 
Inserted 40 at the end
Inserted 50 at the end
Forward: 10 20 30 40 50 
Inserted 25 at position 3
Forward: 10 20 25 30 40 50 
Deleted 10 from beginning
Deleted 50 from end
Deleted 25 from position 3
Forward: 20 30 40 
25 not found in the list
Found 40 at position 3