Doubly and circular linked lists

Why it matters

A singly linked list gives you one direction. From any node you can reach the nodes after it, but never the nodes before it. That single limit causes three problems. You cannot remove a node you already hold without first walking from the head to find its predecessor. You cannot walk backwards at all. And if you need to reach the last node quickly, you must keep a tail pointer and update it with care.

A doubly linked list fixes the first two problems by adding a second pointer to each node. A circular linked list fixes the third by making the last node point back to the first, so there is no end to find. Both ideas are used in real software: browsers use them for history, caches use them to track the least recently used item, and operating systems use circular lists to schedule tasks. In C++ the standard library provides std::list, which is a doubly linked list, so you should know what it does for you and what it costs.

This is the last lesson of the module, so it also puts the earlier pointer habits to work. Save before you change. Check for nullptr before you follow a pointer. Keep a single owner for each node, and free it once.

The idea of a second pointer

Think about a train. Each carriage is joined to the one in front and the one behind. If you are standing in the middle of the train and want to uncouple your carriage, you can reach both neighbours directly. You do not need to walk from the engine to find the carriage before yours. A singly linked list is like a train where each carriage can only see the one in front. To uncouple a carriage you must first walk from the engine to find the one before it.

A doubly linked node has two link fields. next points to the node after it, as before. prev points to the node before it. The head has prev equal to nullptr. The tail has next equal to nullptr. Every other node has both pointers set.

Here is the node definition, with the constructor that sets both pointers to nullptr.

struct DNode {
    int data;
    DNode* prev;   // the node before this one, or nullptr for the head
    DNode* next;   // the node after this one, or nullptr for the tail
    DNode(int d) : data(d), prev(nullptr), next(nullptr) {}
};

The cost of this extra pointer is memory. Each node now takes two pointers instead of one. On a 64-bit machine that is 8 more bytes per node. The benefit is that some operations become faster. The tradeoff is that every insert and delete must now change up to four pointers, not two, and a mistake in any one leaves the list broken in a way that only shows when you walk it backwards.

The picture below shows three doubly linked nodes. Each arrow pair joins two neighbours, one arrow for each direction.

Three doubly linked nodes, each with a left prev cell and a right next cell, and arrows in both directions between neighbours

The visualizer below uses the linked list animation. Watch the cursor move forwards along the next arrows. Then think about how the same node could be reached from its successor by following prev.

A doubly linked list with head and tail

A doubly linked list usually keeps both a head and a tail. With both ends known, you can add at either end in O(1), and you can walk in either direction. Here is a small class that does the two adds and a backward walk. Read the pushFront function carefully, because it is the mirror image of pushBack, and most bugs come from changing one and forgetting the other.

struct DList {
    DNode* head = nullptr;
    DNode* tail = nullptr;
    int size = 0;
 
    void pushBack(int v) {
        DNode* n = new DNode(v);
        n->prev = tail;              // the new node's predecessor is the old tail
        if (tail != nullptr) tail->next = n;
        else head = n;               // empty list: the new node is also the head
        tail = n;
        size++;
    }
 
    void pushFront(int v) {
        DNode* n = new DNode(v);
        n->next = head;              // the new node's successor is the old head
        if (head != nullptr) head->prev = n;
        else tail = n;               // empty list: the new node is also the tail
        head = n;
        size++;
    }
};

Trace pushBack on an empty list with value 1. tail is nullptr, so n->prev is nullptr. The if is false, so head becomes n. Then tail becomes n. Both ends point at the one node, and both its prev and next are nullptr.

Trace pushBack(2) on that list. n->prev is node 1, which is the old tail. tail is not null, so tail->next becomes node 2. Then tail moves to node 2. Node 1's next is node 2, and node 2's prev is node 1. The links now agree in both directions.

Trace pushFront(0) on the list 1, 2. n->next is node 1, the old head. head is not null, so head->prev is set to node 0. Then head moves to node 0. The list is 0, 1, 2 in both directions.

Each function changes four pointers, counting the two in the new node. The rule that keeps them consistent is simple: after an operation, for every pair of neighbours A and B, A's next is B and B's prev is A.

Removing a node you already hold

The main gain from a doubly linked list is removal. Suppose you have a pointer to a node, perhaps saved from an earlier search. In a singly linked list you must walk from the head to find its predecessor. In a doubly linked list you do not need to walk, because prev gives you the predecessor directly. Removal then takes O(1) time.

void removeNode(DNode* node) {
    if (node->prev != nullptr) node->prev->next = node->next;
    else head = node->next;                  // node was the head
    if (node->next != nullptr) node->next->prev = node->prev;
    else tail = node->prev;                  // node was the tail
    delete node;
    size--;
}

This is a method of DList, so it can change head and tail directly. The two if pairs cover the four cases that matter: a middle node, the head, the tail, and the only node. For the only node, both prev and next are nullptr, so the first if sets head to nullptr, and the second sets tail to nullptr. The list is empty and both ends are correct.

Notice the order. Each neighbour's pointer is changed to skip the node, and then the node is deleted. The node's own prev and next are read before the delete, so nothing reads freed memory. The rule from lesson 2 still applies: save before you break, and free last.

Here is a complete program. It builds a list, prints it forwards and backwards, removes a node in the middle, and prints again.

0 1 2 3
3 2 1 0
0 1 3
3 1 0
size 3

Look at the backward print. It starts at tail and follows prev. This is the walk that a singly linked list cannot do. After removing 2, the forward walk shows 0, 1, 3 and the backward walk shows 3, 1, 0. The two walks agree, which is the check that the links are right in both directions.

The DList struct in this program does not free its nodes when it is destroyed. Add a destructor that walks forward, saves next, and deletes each node, as in lesson 2. Without it the nodes leak when the list goes out of scope.

Why the extra pointer helps, and what it costs

Two costs matter in practice. A doubly linked list uses more memory, because every node holds two pointers. It also has more places where a pointer can be wrong. In a singly linked list, a broken next affects one direction. In a doubly linked list, a broken prev makes backward walks wrong while forward walks still look fine, so bugs can hide for a long time.

The gain is the O(1) removal of a known node. This matters for caches. An LRU cache is a structure that keeps the most recently used items and throws out the least recently used one when it is full. A common design uses a hash table to find an item in O(1) and a doubly linked list to move that item to the front in O(1). Moving to the front means removing the node from its place and pushing it to the front. Without prev, the move would need a walk, and the cache would be O(n) per access.

The LRU design shows the point of the extra pointer. The hash table holds the address of each node. The node already knows its neighbours, so the cache never walks. You will meet this combination in the hash table module. For now, remember the rule: a doubly linked list pays memory to make removal of a known node cheap.

Walking a doubly linked list both ways, traced

Take the list 1, 2, 3 with a head on node 1 and a tail on node 3. Node 2 has prev pointing at node 1 and next pointing at node 3. Node 3 has prev pointing at node 2 and next equal to nullptr. Node 1 has prev equal to nullptr and next pointing at node 2.

A backward walk starts at the tail and follows prev. It visits node 3, then node 2 by following node 3's prev, then node 1 by following node 2's prev. Then prev of node 1 is nullptr, so the walk stops. The output is 3, 2, 1. A forward walk starts at the head and gives 1, 2, 3. Both walks use the same nodes, and they agree because each pair of neighbours points at each other in both directions.

Now remove node 2 with the removeNode logic. The steps, in order, are these. Node 2's prev is node 1, so node 1's next becomes node 2's next, which is node 3. Node 2's next is node 3, so node 3's prev becomes node 2's prev, which is node 1. Node 2 is no longer linked from either side, so it is deleted. The forward walk gives 1, 3 and the backward walk gives 3, 1.

Remove node 1 next. Its prev is nullptr, so the code sets head to node 1's next, which is node 3. Node 3's prev is node 1 and must become node 1's prev, which is nullptr. Node 1 is deleted, and the list is only node 3, with head and tail both on it. Notice that the code changes the head pointer only when the removed node has no predecessor. Forgetting this branch is the most common doubly linked bug.

Walks in both directions are a good test. After every change, print forwards and backwards and check that the two outputs are reverses of each other. A mismatch tells you exactly which pointer is wrong.

An LRU cache, traced

An LRU cache keeps the most recently used items. When it is full and a new item arrives, it throws out the least recently used one. This is a common design question, and it uses the doubly linked list from this lesson.

The cache in this trace holds two items. Keep the list in order from most recently used at the front to least recently used at the back. A hash table, which you will meet in its own module, finds any item's node in O(1). The list moves a node to the front in O(1), because removeNode needs only the node, and the new front is one push away.

Run the operations put 1, put 2, get 1, put 3. After put 1 the order is 1. After put 2 the order is 2, 1, because 2 is the newest. get 1 returns 1 and moves it to the front, so the order is 1, 2. Now put 3 arrives, and the cache is full. The least recently used item is at the back, which is 2. The cache removes node 2 and adds 3 at the front. The order is 3, 1. A later get 2 misses, because 2 was evicted.

Each step is O(1). With an array, moving an item to the front shifts every item after it, and that is O(n) per access. With a singly linked list, removing the node from the middle needs its predecessor, which needs a walk. The doubly linked list is the piece that makes the whole cache O(1) per operation.

Circular linked lists

A circular linked list has no nullptr at the end. The last node's next points back to the first node. The list goes around forever, so you cannot search it with the usual loop, which stops at nullptr. You need to know where you started and stop when you return to it.

The circle is common in problems that repeat, such as a round-robin scheduler that gives each task a turn, or a game where players sit in a ring. The list does not need a nullptr because nothing ends. It needs a rule for when to stop.

A circular list is usually built with a tail pointer, because the tail is the node whose next must point back to the head. Keep the tail. The head is tail->next. That makes insertion at the front or back O(1), because both ends are reachable from the tail.

Here is a circular list that stores a tail. The append keeps the circle closed, and the print goes around exactly once.

struct CList {
    Node* tail = nullptr;                  // tail->next is the head
    void append(int v) {
        Node* n = new Node(v);
        if (tail == nullptr) {
            n->next = n;                   // one node pointing at itself
        } else {
            n->next = tail->next;          // the new node points at the head
            tail->next = n;                // the old tail points at the new node
        }
        tail = n;                          // the new node is the tail
    }
};

The first branch makes a circle of one node, whose next is itself. In the second branch, the new node takes the head's place in the circle: it points at the head, and the old tail points at it. Then the new node becomes the tail. Trace append(1), then append(2), then append(3) and you get the circle 1, 2, 3, 1, with the tail on 3.

Printing a circular list needs a do while loop instead of a while loop. The reason is that the list is never empty when you have a tail, and the loop must run at least once. The stopping test compares with the start node, not with nullptr.

void printCircle(Node* tail) {
    if (tail == nullptr) return;           // the empty list has nothing to print
    Node* start = tail->next;              // the head
    Node* cur = start;
    do {
        cout << cur->data << (cur->next != start ? " " : "");
        cur = cur->next;
    } while (cur != start);                // stop when we are back at the start
}

The do while form is a way to say "do the body once, then check". With a while (cur != start) loop, the body would never run, because cur already equals start at the beginning. That is why the do form is used.

The next program builds a three node circle, prints it, and checks the empty case. It uses the two functions above, with the Node struct from lesson 1.

empty circle: (nothing)
circle: 1 2 3
tail 3, head 1
the head's next is 2

Trace the three appends. The first call makes node 1 point at itself, and tail is node 1. The second call gives node 2 the next of node 1, which is node 1, so node 2 points at node 1. Then node 1 points at node 2, and tail moves to node 2. The third call gives node 3 the next of the head, node 1, then points node 2 at node 3, and moves tail to node 3. The circle is 1, 2, 3, back to 1. The head is tail->next, which is node 1, so the output says head 1. The line tail->next->next->data walks two steps from the tail, to node 2, which is the node after the head.

Now the circular list can solve a problem that a plain list would make awkward. The Josephus problem is a classic. People stand in a circle, numbered from 1 to n. Starting at person 1, count k people around the circle. The k-th person is removed. The count restarts at the next person, and the process repeats until one person remains. The question is who survives. The circle makes this easy to simulate, because removing a person joins the two neighbours and the circle stays closed.

Here is the simulation. It keeps prev, the node just before the current count position, so each removal is a single pointer change.

removal order: 3 6 2 7 5 1
survivor: 4

Trace the first two removals to see how the circle behaves. The circle is 1 through 7 with the tail on 7. prev starts at 7 and cur at 1. Counting three people means moving two steps: first prev becomes 1 and cur becomes 2, then prev becomes 2 and cur becomes 3. Person 3 is removed by setting prev->next to cur->next, which is 4. Now cur becomes prev->next, which is 4. The circle is 1, 2, 4, 5, 6, 7.

The second removal starts counting at 4. Two steps move prev to 5 and cur to 6, so person 6 is removed. The circle is 1, 2, 4, 5, 7. Continuing this way gives the order 3, 6, 2, 7, 5, 1, and the survivor is 4. You can check the full answer by hand, but you should check at least the first two removals, to be sure you understand the moves.

The loop stops when one node remains, because left drops to 1. At that point cur is the survivor. The line delete cur; frees it, so the list is empty when the function returns, and the program leaks nothing.

std::list in C++

The standard library has a doubly linked list called std::list. It is in the header <list>. You should use it in real code when you need a list, because it is tested and its behaviour is well defined. You should still write your own list in this module, because interviews often ask you to build one.

Here is a short program. It makes a list, adds at both ends, finds a value, removes it through an iterator, and prints the result.

0 1 2 4 5 6
size 6

The program uses find from <algorithm> to get an iterator to the value 3. An iterator is an object that points at an element and moves through the container, and list::end() is a sentinel iterator that marks the position after the last element. Removing through the iterator with erase is O(1), because the list does not have to shift items. Only the iterator you erased becomes invalid. Other iterators stay valid, which is a useful property that an array does not have.

The cost of std::list is the same as your own version. Random access is absent: you cannot write xs[2], because the list does not support it. Walking to the third element is O(n). Each element also carries two pointers and a separate heap allocation, so a list is slower than a std::vector for most jobs, even where the operation count looks better. Use std::vector by default, and reach for std::list when you need stable iterators or O(1) removal at known positions.

There is also std::forward_list, which is singly linked, with less memory per element and no size() method in its usual form. You do not need it for this module, but knowing it exists answers the question "what is the singly linked list in the standard library" in an interview.

A sentinel node

The sentinel is the doubly linked version of the dummy head from lesson 4. It is a node that holds no data and sits between the tail and the head, so the list forms a circle that includes the sentinel. The sentinel's next is the first real node, and its prev is the last real node. An empty list is a sentinel that points at itself.

This removes the special cases. A node always has a prev and a next, because the sentinel supplies them at both ends. Inserting at the front and at the back is the same code, and removing the first or last node needs no if. The cost is one extra node and a little care when you walk, because a walk must stop when it returns to the sentinel, not at nullptr.

Here is the core of a sentinel list. It is a fragment, so it is not runnable on its own.

struct SList {
    DNode sentinel{0};                    // holds no real value
 
    SList() {
        sentinel.next = &sentinel;        // empty: the sentinel points at itself
        sentinel.prev = &sentinel;
    }
 
    void pushBack(int v) {
        DNode* n = new DNode(v);
        n->prev = sentinel.prev;          // the old last node
        n->next = &sentinel;              // the new node is followed by the sentinel
        sentinel.prev->next = n;          // the old last node points at the new one
        sentinel.prev = n;                // the sentinel's prev is the new last node
    }
};

Trace pushBack(7) on an empty sentinel list. sentinel.prev is the sentinel itself, so n->prev is the sentinel. n->next is the sentinel. The sentinel's next is n, so the first real node is linked in front of the sentinel. Then sentinel.prev is n. The list is one node, which is linked on both sides to the sentinel. Nothing was checked against nullptr, and the code path is the same as for a non-empty list.

Some teams prefer this design for its simplicity, and the standard library's std::list uses a node that works in the same way. The trade-off is that every walk must stop at the sentinel. A walk that stops at nullptr, as in the earlier lessons, loops forever on a sentinel list.

Choosing a list type

Choosing a structure is a skill that interviewers test. The table below compares the options in this module with std::vector, which is usually the best default in C++.

A good answer names the operations the problem needs most, then picks the row that makes them cheap. If the main work is reading by index, choose the vector, even when the operation count seems to favour a list. Memory layout and cache use often decide the speed in practice, and a vector is usually faster. Choose a list when you must remove or insert at places you already hold, and when the pointers stay valid while the rest of the list changes.

Common mistakes and the messages you will see

The first doubly linked mistake is to update only one direction. Writing node->prev->next = node->next; without node->next->prev = node->prev; leaves a prev pointer that points at a deleted node. Forward walks still work, so the bug can hide. A backward walk then reads freed memory, which the sanitizer reports as heap-use-after-free on the line that follows prev.

The second mistake is to forget the head or tail update. Removing the head with node->prev->next written without an if reads through nullptr when prev is null. The sanitizer reports SEGV with a small address, the same signature as before. The fix is the if pair from removeNode.

The third mistake is to build a circle without closing it. If tail->next stays nullptr, a do while print around the circle stops at the end and prints the list once, which looks correct for a list that you forgot to close. The bug shows when a circular algorithm runs for the wrong number of steps. Check the closing link right after you build the circle.

The fourth mistake is to use while (cur != nullptr) on a circular list. The loop never ends, because no node has next equal to nullptr. The program prints the same values forever, or it runs until a time limit stops it. If a program prints a repeating pattern of numbers, you have a circle where you expected a line.

The fifth mistake is a do while on an empty circle. Without the check if (tail == nullptr) return;, the code reads tail->next from a null pointer and crashes. Test the empty case first.

The sixth mistake is an iterator used after its element is erased. Calling ++it on an erased iterator is undefined behaviour. Save the next iterator before the erase, or use the return value of erase, which gives the iterator after the removed element in modern C++.

A debugging walkthrough

Suppose your Josephus program prints removal order: 3 6 2 7 5 1 for n equal to 7 and k equal to 3, but for n equal to 5 and k equal to 2 it prints an order and then crashes. Here is a way to find the bug.

First, write the expected answer for the small case. For n equal to 5 and k equal to 2, the order is 2, 4, 1, 5, and the survivor is 3. Write it down before you run anything.

Second, trace the first step. The circle is 1 through 5 with the tail on 5. prev is 5, cur is 1. With k equal to 2, the inner loop runs once: prev becomes 1 and cur becomes 2. Person 2 is removed. prev->next becomes 3. The circle is 1, 3, 4, 5. cur becomes 3.

Third, trace the second step. With cur at 3 and prev at 1, the inner loop runs once: prev becomes 3 and cur becomes 4. Person 4 is removed, and prev->next becomes 5. The circle is 1, 3, 5, and cur is 5.

Fourth, trace the third step. With cur at 5 and prev at 3, the inner loop runs once: prev becomes 5 and cur becomes 1. Person 1 is removed, and prev->next becomes 3. The circle is 3, 5 and cur is 3. Now left is 2, so the loop runs again.

Fifth, trace the fourth step. The inner loop runs once: prev becomes 3 and cur becomes 5. Person 5 is removed. Now left is 1, the loop ends, and the survivor is cur, which is 3. The trace gives order 2, 4, 1, 5 and survivor 3, which matches the expected answer. So the algorithm is right for this case.

The crash then must come from a different place. Look for a delete that runs on a node still in the circle, or a read of cur after the delete. In the code above, gone is deleted and cur is reset to prev->next before the next step, so the read is safe. If your version reads cur->data after delete cur, that is the bug. The lesson the walkthrough teaches is to trace the state at each step on paper, then check the lines that touch freed memory.

Interview patterns for this lesson

Three patterns come up around doubly and circular lists.

The first is O(1) removal with a known node. When an interviewer gives you a pointer to a node and asks you to delete it, a doubly linked list gives you the answer in O(1). For a singly linked list, the trick is to copy the next node's data into this node and delete the next node, which works except at the tail and when others hold the next node's address.

The second is two pointers around a circle. The Josephus pattern is a version of the fast and slow idea: one pointer marks the position before the current count, and the other moves ahead. Many circle problems reduce to this.

The third is the sentinel node. A doubly linked list is often built with a dummy node that sits between the tail and the head, so the list is a circle that contains the sentinel. Then the head and tail are never nullptr, and every insert and delete has the same shape. This removes the if pairs from removeNode. Interviewers like it when you name the pattern and explain why it removes special cases, because it is the same idea as the dummy head from lesson 4, extended to both ends.

A question that often follows is "What is the difference between a list and an array for an LRU cache?" The answer is that an array would make moving an item to the front O(n), because the items must shift. A doubly linked list with a hash table makes every access O(1). Be ready to draw the two pointers and the table lookup on a whiteboard.

Practice

Try each exercise on paper first. For the circular exercises, draw the circle and mark the pointers before you write code.

1. Write void printBackward(DNode* tail) that prints a doubly linked list from its tail to its head, separated by spaces, with a newline at the end. Handle the empty list.

void printBackward(DNode* tail) {
    for (DNode* cur = tail; cur != nullptr; cur = cur->prev) {
        cout << cur->data << (cur->prev ? " " : "");
    }
    cout << "\n";
}

2. Write int countNodesCircle(Node* tail) for a circular singly linked list. Return 0 for an empty circle.

int countNodesCircle(Node* tail) {
    if (tail == nullptr) return 0;
    int n = 0;
    Node* start = tail->next;
    Node* cur = start;
    do {
        n++;
        cur = cur->next;
    } while (cur != start);
    return n;
}

3. Explain why while (cur != start) with cur = start initially would be wrong for printing a circle, and show the fix.

4. Write void appendToCircle(Node*& tail, int v) for a circular list, so the new node is the tail and the circle stays closed. Use the rule from this lesson.

void appendToCircle(Node*& tail, int v) {
    Node* n = new Node(v);
    if (tail == nullptr) {
        n->next = n;
    } else {
        n->next = tail->next;
        tail->next = n;
    }
    tail = n;
}

5. Write void removeHeadOfDoubly(DList& list) that removes the head using the removeNode logic, and does nothing on an empty list.

void removeHeadOfDoubly(DList& list) {
    if (list.head == nullptr) return;
    list.removeNode(list.head);
}

6. A doubly linked list has n nodes. Count the pointer changes needed to insert a new node in the middle, and to remove a node in the middle. Give the numbers.

7. Explain why an LRU cache needs both a hash table and a doubly linked list, and what would go wrong with only a singly linked list.

8. Trace the Josephus simulation for n equal to 4 and k equal to 2 by hand, and write the removal order and the survivor.

9. In josephus, the code sets cur = prev->next after the removal. Explain why that is correct, and what would happen if it were cur = cur->next instead.

10. Explain in two sentences why std::list::erase is O(1) for a known position, while std::vector::erase is O(n) in the worst case.

What you now know

• A doubly linked node has prev and next. Removing a node you already hold takes O(1), because the neighbours are reachable directly.
• A doubly linked list usually keeps a head and a tail. Every insert and delete must update both directions and the two ends, including the empty case.
• The LRU cache combines a hash table with a doubly linked list. That is the common real use of the extra pointer.
• A circular list has no nullptr at the end. Walk it with a do while loop that stops when it returns to the start, and check for the empty circle first.
• The Josephus problem shows the circle in use: keep the node before the current position, unlink the k-th node, and restart the count after it.
• std::list is the standard doubly linked list. It gives O(1) erase through an iterator, but no random access, and it is slower than std::vector for most work.

The module assignment that follows uses everything in this module in one project.