Demystifying Algorithms: Doubly Linked Lists

What is a Doubly Linked List?

A doubly linked list is a data structure where each node contains:

1. Data: The value stored in the node.
2. Next: A pointer (reference) to the next node in the sequence.
3. Prev: A pointer (reference) to the previous node in the sequence.

In a doubly linked list:

• The first node’s Prev pointer is null, as there’s no node before it.
• The last node’s Next pointer is null, indicating the end of the list.

This structure allows traversal in both directions (forward and backward), making some operations more efficient compared to singly linked lists.

---

The Technical View

• Time Complexity:

  • Access: (O(n)) (you must traverse the list).
  • Insertion/Deletion:
  • At the head or tail: (O(1)).
  • At a specific position: (O(n)).

• Space Complexity:

  • (O(n)), where (n) is the number of nodes.
  • Additional space is required for the Prev pointers.

---

A Fifth-Grader's Summary

Think of a doubly linked list as a two-way train where each carriage has:

1. A name tag (data).
2. A pointer to the next carriage.
3. A pointer to the previous carriage.

If you’re at one carriage, you can move forward to the next or backward to the previous without having to start from the engine (head).

---

Real-World Example

Imagine a browser’s history feature. You can navigate forward and backward through pages (nodes). The Next pointer helps you go forward, and the Prev pointer lets you go back.

---

Operations on a Doubly Linked List

---

1. Insert a Node at the Head

Problem: Add a new node with value 3 at the beginning of the list.

Code:

class DoublyLinkedListNode {
    public int Data;
    public DoublyLinkedListNode Next;
    public DoublyLinkedListNode Prev;

    public DoublyLinkedListNode(int data) {
        Data = data;
        Next = null;
        Prev = null;
    }
}

DoublyLinkedListNode InsertAtHead(DoublyLinkedListNode head, int data) {
    DoublyLinkedListNode newNode = new DoublyLinkedListNode(data);

    if (head != null) {
        head.Prev = newNode;
    }
    newNode.Next = head;
    return newNode;
}

Initial List: 5 <-> 10 <-> 15 <-> null

Steps:

1. Create a new node with data 3.
2. Set the new node’s Next to the current head (5).
3. Update the current head’s Prev pointer to the new node.
4. Update the head to the new node.

Updated List: 3 <-> 5 <-> 10 <-> 15 <-> null

---

2. Insert a Node at the Tail

Problem: Add a new node with value 20 at the end of the list.

Code:

DoublyLinkedListNode InsertAtTail(DoublyLinkedListNode head, int data) {
    DoublyLinkedListNode newNode = new DoublyLinkedListNode(data);

    if (head == null) return newNode;

    DoublyLinkedListNode current = head;
    while (current.Next != null) {
        current = current.Next;
    }

    current.Next = newNode;
    newNode.Prev = current;
    return head;
}

Initial List: 5 <-> 10 <-> 15 <-> null

Steps:

1. Create a new node with data 20.
2. Traverse to the last node (15).
3. Set the last node’s Next to the new node.
4. Set the new node’s Prev to the last node.

Updated List: 5 <-> 10 <-> 15 <-> 20 <-> null

---

3. Insert a Node at a Specific Position

Problem: Insert a node with value 12 at position 2 (0-based index).

Code:

DoublyLinkedListNode InsertAtPosition(DoublyLinkedListNode head, int data, int position) {
    DoublyLinkedListNode newNode = new DoublyLinkedListNode(data);

    if (position == 0) {
        newNode.Next = head;
        if (head != null) head.Prev = newNode;
        return newNode;
    }

    DoublyLinkedListNode current = head;
    while (position - 1 > 0) {
        current = current.Next;
        position--;
    }

    newNode.Next = current.Next;
    newNode.Prev = current;

    if (current.Next != null) current.Next.Prev = newNode;
    current.Next = newNode;

    return head;
}

Initial List: 5 <-> 10 <-> 15 <-> null

Steps:

1. Create a new node with data 12.
2. Traverse to the node at position 1 (10).
3. Update pointers:
   • Set the new node’s Next to the node at position 2 (15).
   • Set the new node’s Prev to the node at position 1 (10).
   • Update the Prev pointer of the node at position 2 to the new node.
   • Update the Next pointer of the node at position 1 to the new node.

Updated List: 5 <-> 10 <-> 12 <-> 15 <-> null

---

4. Delete a Node

Problem: Remove the node at position 1 (0-based index).

Code:

DoublyLinkedListNode DeleteNode(DoublyLinkedListNode head, int position) {
    if (head == null) return null;

    if (position == 0) {
        head = head.Next;
        if (head != null) head.Prev = null;
        return head;
    }

    DoublyLinkedListNode current = head;
    while (position - 1 > 0) {
        current = current.Next;
        position--;
    }

    current.Next = current.Next.Next;
    if (current.Next != null) current.Next.Prev = current;

    return head;
}

Initial List: 5 <-> 10 <-> 15 <-> 20 <-> null

Steps:

1. Traverse to the node at position 0 (5).
2. Skip the node at position 1 by updating:
   • The Next pointer of 5 to 15.
   • The Prev pointer of 15 to 5.

Updated List: 5 <-> 15 <-> 20 <-> null

---

5. Reverse a Doubly Linked List

Problem: Reverse the order of nodes in the list.

Code:

DoublyLinkedListNode Reverse(DoublyLinkedListNode head) {
    DoublyLinkedListNode current = head;
    DoublyLinkedListNode temp = null;

    while (current != null) {
        temp = current.Prev;
        current.Prev = current.Next;
        current.Next = temp;
        current = current.Prev;
    }

    return temp?.Prev;
}

Initial List: 5 <-> 10 <-> 15 <-> 20 <-> null

Steps:

1. Start with the first node (5).
2. Swap the Next and Prev pointers for each node.
3. Continue until the end of the list.
4. The new head is the last node (20).

Updated List: 20 <-> 15 <-> 10 <-> 5 <-> null

---

Conclusion

Doubly linked lists are versatile and allow efficient traversal in both directions. They are particularly useful in scenarios where you frequently need to navigate forward and backward, like undo/redo operations in text editors or navigation in browsers.

Stay tuned for the next post in this series, where we’ll demystify circular linked lists!