C++UCS301
Linear Data StructuresC++17

Doubly Linked List

Doubly linked nodes keep both next and previous links, allowing bidirectional traversal and constant-time removal of a known node.

What to understand

  • Previous and next links
  • Bidirectional traversal
  • Boundary updates
  • Memory overhead

Remember this

  1. 1Every mutation may update four links
  2. 2Known-node deletion is O(1)
  3. 3More flexibility costs an extra pointer per node

Detailed notes

A doubly linked node contains previous and next links. The extra direction enables reverse traversal and removal of a known node without searching for its predecessor.

Sentinel head and tail nodes can eliminate most boundary branches: every real node then always has neighbours, and insertion becomes the same four-link operation at every position.

How it works

  1. 1Connect the new node to both neighbours.
  2. 2Redirect both neighbours back to the new node.
  3. 3For deletion, join the two neighbours before freeing the node.
  4. 4Keep head and tail consistent when sentinels are not used.

Where it is used

  • Browser history and undo/redo
  • LRU cache ordering
  • Deques and intrusive lists

Common mistakes

  • Updating next but forgetting previous
  • Using a removed node after deletion
  • Paying extra memory when reverse traversal is never needed

Complexity analysis

OperationBestAverageWorstExtra space
SearchO(n)O(n)O(n)O(1)
Insert at either endO(1)O(1)O(1)O(1)
Delete known nodeO(1)O(1)O(1)O(1)
Indexed accessO(n)O(n)O(n)O(1)

C++ implementation

C++17 reference
main.cpp

Doubly linked insertion and removal

A sentinel-free implementation must update both ends and both directions carefully.

struct Node {
    int value;
    Node* previous;
    Node* next;
};

void insertAfter(Node*& tail, Node* position, int value) {
    Node* node = new Node{value, position, position->next};
    if (position->next) position->next->previous = node;
    else tail = node;
    position->next = node;
}

void erase(Node*& head, Node*& tail, Node* node) {
    if (node->previous) node->previous->next = node->next;
    else head = node->next;
    if (node->next) node->next->previous = node->previous;
    else tail = node->previous;
    delete node;
}
20 linesUTF-8 · C++ study reference

Exam & viva

Open a prompt when you are ready to check your answer.