Unlocking the Power of Doubly Linked Lists in C

Welcome back to our C-Language Series! In this installment, we're diving deep into a fascinating and incredibly useful data structure: the Doubly Linked List (DLL). Building upon our understanding of singly linked lists, DLLs introduce a powerful new dimension: bi-directional traversal. This feature opens up a world of possibilities for more efficient data manipulation.

A Doubly Linked List is a linear data structure where each node contains not only the data and a pointer to the next node (next), but also a pointer to the previous node (prev). This extra pointer is what enables traversal in both forward and backward directions, making certain operations significantly more straightforward than in a singly linked list.

Understanding the Doubly Linked List Node Structure

The fundamental building block of a Doubly Linked List is its node. Each node typically consists of three parts:

• data: The actual information stored in the node (can be any data type).
• next: A pointer to the subsequent node in the list.
• prev: A pointer to the preceding node in the list.

Graphically, a DLL node looks like this:

       +------+------+------+
       | prev | data | next |
       +------+------+------+
    

And here's how we define this structure in C:

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

// Define the structure for a node in the Doubly Linked List
typedef struct Node {
    int data;          // Data part
    struct Node* prev; // Pointer to the previous node
    struct Node* next; // Pointer to the next node
} Node;

// Global head pointer for the list (or pass as parameter)
Node* head = NULL;
Node* tail = NULL; // Often useful to maintain a tail pointer for O(1) insertion at end

Core Operations on a Doubly Linked List

Let's explore the essential operations you can perform on a Doubly Linked List, complete with C code implementations.

1. Creating a New Node (Helper Function)

A utility function to allocate memory for a new node and initialize its values.

Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("Memory allocation failed!\n");
        exit(EXIT_FAILURE);
    }
    newNode->data = data;
    newNode->prev = NULL;
    newNode->next = NULL;
    return newNode;
}

2. Insertion Operations

a) Inserting at the Beginning

To add a new node to the front of the list, we need to update the head pointer and adjust the prev and next pointers of the new node and the original head (if it exists).

void insertAtBeginning(int data) {
    Node* newNode = createNode(data);
    if (head == NULL) { // If the list is empty
        head = newNode;
        tail = newNode;
    } else {
        newNode->next = head; // New node points to current head
        head->prev = newNode; // Current head's prev points to new node
        head = newNode;       // New node becomes the head
    }
    printf("Inserted %d at the beginning.\n", data);
}

b) Inserting at the End

Adding a node to the end is efficient if we maintain a tail pointer. Otherwise, we would need to traverse the entire list.

void insertAtEnd(int data) {
    Node* newNode = createNode(data);
    if (head == NULL) { // If the list is empty
        head = newNode;
        tail = newNode;
    } else {
        tail->next = newNode; // Current tail points to new node
        newNode->prev = tail; // New node's prev points to current tail
        tail = newNode;       // New node becomes the tail
    }
    printf("Inserted %d at the end.\n", data);
}

c) Inserting After a Specific Node

This operation requires finding the node after which the new node is to be inserted, and then carefully adjusting four pointers.

void insertAfter(int key, int data) {
    Node* current = head;
    while (current != NULL && current->data != key) {
        current = current->next;
    }

    if (current == NULL) {
        printf("Node with key %d not found. Cannot insert.\n", key);
        return;
    }

    Node* newNode = createNode(data);

    if (current == tail) { // Inserting after the tail
        insertAtEnd(data); // Can reuse insertAtEnd logic
        free(newNode); // Free the node allocated by createNode, as insertAtEnd creates one
        return;
    }

    newNode->next = current->next;  // New node points to current's next
    newNode->prev = current;        // New node's prev points to current
    current->next->prev = newNode;  // Current's next node's prev points to new node
    current->next = newNode;        // Current points to new node

    printf("Inserted %d after node with key %d.\n", data, key);
}
```

void deleteFromBeginning() {
    if (head == NULL) {
        printf("List is empty. Nothing to delete.\n");
        return;
    }

    Node* temp = head;
    int deletedData = temp->data;

    if (head->next == NULL) { // Only one node in the list
        head = NULL;
        tail = NULL;
    } else {
        head = head->next; // Move head to the next node
        head->prev = NULL; // New head's prev becomes NULL
    }
    free(temp); // Free the old head node
    printf("Deleted %d from the beginning.\n", deletedData);
}
```

void deleteFromEnd() {
    if (head == NULL) {
        printf("List is empty. Nothing to delete.\n");
        return;
    }

    Node* temp = tail;
    int deletedData = temp->data;

    if (head->next == NULL) { // Only one node in the list
        head = NULL;
        tail = NULL;
    } else {
        tail = tail->prev; // Move tail to the previous node
        tail->next = NULL; // New tail's next becomes NULL
    }
    free(temp); // Free the old tail node
    printf("Deleted %d from the end.\n", deletedData);
}
```

void deleteNode(int key) {
    if (head == NULL) {
        printf("List is empty. Nothing to delete.\n");
        return;
    }

    Node* current = head;
    while (current != NULL && current->data != key) {
        current = current->next;
    }

    if (current == NULL) {
        printf("Node with key %d not found.\n", key);
        return;
    }

    if (current == head) { // Deleting the head node
        deleteFromBeginning();
        return; // deleteFromBeginning already freed the node
    }
    if (current == tail) { // Deleting the tail node
        deleteFromEnd();
        return; // deleteFromEnd already freed the node
    }

    // Deleting a node in the middle
    current->prev->next = current->next; // Previous node's next points to current's next
    current->next->prev = current->prev; // Current's next node's prev points to current's prev

    printf("Deleted %d from the list.\n", key);
    free(current); // Free the deleted node
}
```

void traverseForward() {
    if (head == NULL) {
        printf("List is empty.\n");
        return;
    }
    Node* current = head;
    printf("List (forward): ");
    while (current != NULL) {
        printf("%d <-> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}

void traverseBackward() {
    if (tail == NULL) { // Can also check head == NULL
        printf("List is empty.\n");
        return;
    }
    Node* current = tail;
    printf("List (backward): ");
    while (current != NULL) {
        printf("%d <-> ", current->data);
        current = current->prev;
    }
    printf("NULL\n");
}

Node* searchNode(int key) {
    Node* current = head;
    while (current != NULL && current->data != key) {
        current = current->next;
    }
    return current; // Returns NULL if not found, or the node pointer if found
}
```

void freeList() {
    Node* current = head;
    Node* nextNode;
    while (current != NULL) {
        nextNode = current->next;
        free(current);
        current = nextNode;
    }
    head = NULL; // Reset head and tail
    tail = NULL;
    printf("List freed from memory.\n");
}
```

int main() {
    // Initial state
    traverseForward();
    traverseBackward();

    // Insertion
    insertAtBeginning(10); // List: 10
    insertAtEnd(30);       // List: 10 <-> 30
    insertAtBeginning(5);  // List: 5 <-> 10 <-> 30
    insertAtEnd(40);       // List: 5 <-> 10 <-> 30 <-> 40
    insertAfter(10, 20);   // List: 5 <-> 10 <-> 20 <-> 30 <-> 40
    insertAfter(40, 50);   // List: 5 <-> 10 <-> 20 <-> 30 <-> 40 <-> 50

    traverseForward();   // Expected: 5 <-> 10 <-> 20 <-> 30 <-> 40 <-> 50 <-> NULL
    traverseBackward();  // Expected: 50 <-> 40 <-> 30 <-> 20 <-> 10 <-> 5 <-> NULL

    // Search
    Node* found = searchNode(20);
    if (found) {
        printf("Node with data 20 found.\n");
    } else {
        printf("Node with data 20 not found.\n");
    }

    found = searchNode(99);
    if (found) {
        printf("Node with data 99 found.\n");
    } else {
        printf("Node with data 99 not found.\n");
    }

    // Deletion
    deleteFromBeginning(); // Deletes 5. List: 10 <-> 20 <-> 30 <-> 40 <-> 50
    traverseForward();

    deleteFromEnd();       // Deletes 50. List: 10 <-> 20 <-> 30 <-> 40
    traverseForward();

    deleteNode(20);        // Deletes 20. List: 10 <-> 30 <-> 40
    traverseForward();
    traverseBackward();

    deleteNode(10);        // Deletes 10 (new head). List: 30 <-> 40
    traverseForward();

    deleteNode(40);        // Deletes 40 (new tail). List: 30
    traverseForward();

    deleteNode(30);        // Deletes 30 (last node). List: empty
    traverseForward();

    // Try deleting from an empty list
    deleteFromBeginning();
    deleteNode(100);

    // Free all remaining memory (if any nodes were left, though we deleted all)
    freeList();

    return 0;
}
```