Doubly Linked List

What is a Doubly Linked List?

Unlike singly linked lists, a doubly linked list (DLL) contains nodes with two pointers:

1. Next Pointer: Points to the next node.
2. Previous Pointer: Points to the previous node.

This bidirectional structure allows for more flexible operations, like traversing in both directions and efficiently deleting nodes from the middle of the list.

Advantages of Doubly Linked Lists

• Bidirectional traversal: You can move forward or backward through the list.
• Easier deletion: Since nodes have a pointer to their predecessor, deleting nodes in the middle is more straightforward.

However, DLLs require more memory due to the additional pointer.

Common Operations

• Insertion: Add nodes at the beginning O(1), end O(1), or a specific position O(n).
• Deletion: Remove nodes using both next and previous pointers.
• Traversal: Move forward or backward through the list. O(n)

Code Examples

#include <iostream>
using namespace std;

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

void insertAtHead(Node*& head, int value) {
    Node* newNode = new Node();
    newNode->data = value;
    newNode->next = head;
    newNode->prev = NULL;
    if (head) head->prev = newNode;
    head = newNode;
}

void printList(Node* head) {
    while (head) {
        cout << head->data << " -> ";
        head = head->next;
    }
    cout << "NULL" << endl;
}

int main() {
    Node* head = NULL;
    insertAtHead(head, 10);
    insertAtHead(head, 20);
    insertAtHead(head, 30);
    printList(head);
    return 0;
}

Problems to Solve

Important Problems on Linked Lists

Resources

• Doubly Linked Lists (Grokking Data Structures)