Doubly and circular lists in Python

Why it matters

A singly linked list can only move forward. You cannot step back from a node, and you cannot remove a node you hold unless you walk again from the head to find the node before it. Two variants fix these limits. A doubly linked list adds a backward link. A circular linked list links the last node back to the first. Browsers need back and forward, music players repeat a playlist, and operating systems give each waiting task a turn in a circle. This lesson builds both variants and shows when each one is worth its extra cost.

The problem with one direction

Picture a train. A singly linked list is a train where each carriage has a hook on its front end only. You can pull the train from the engine toward the back, but you cannot walk from the last carriage back toward the engine, because nothing on a carriage points backward. If you want to remove a carriage in the middle, you must find the carriage just in front of it, and that means walking from the engine.

Now give each carriage a hook on both ends. A carriage knows the one in front and the one behind. You can walk either way, and you can unhook any carriage the moment you hold it, because you know its neighbours. That is the doubly linked list. It costs two references per node instead of one, and it gives you backward moves and fast removal.

The doubly linked node

A doubly linked node holds three things: a value, a reference to the previous node, and a reference to the next node. The attribute names are prev and next. The first node has prev set to None. The last node has next set to None.

The list usually keeps two references: head for the first node and tail for the last node. Keeping tail makes adding at the end O(1), which the singly list could not do without a walk.

Here is the node class:

class DNode:
    def __init__(self, val):
        self.val = val
        self.prev = None
        self.next = None

Each attribute starts as None, so a fresh node is an island until the list links it in. Each attribute gets its own line, so each line is easy to read.

A text picture of three nodes helps. The arrows point in both directions:

None <- [10] <-> [20] <-> [30] -> None
          ^ head           ^ tail

Adding at the end

Adding at the end of a doubly list changes three references, and the order matters for the same reason as before: save what you still need before you overwrite it. Suppose the list is 10 <-> 20 with tail pointing at node 20, and you want to add 30.

1. Create the new node n with prev and next both None.
2. Link it backward: n.prev = self.tail. Now node 30 knows that node 20 comes before it.
3. Link the old last node forward: self.tail.next = n. Now node 20 knows that node 30 comes after it. The order of steps 2 and 3 does not matter here, because neither overwrites a reference the other needs.
4. Move the tail: self.tail = n. Now tail points at the new last node.

If you forget step 3, the forward walk stops at 20 and the new node is reachable only from tail. If you forget step 2, the backward walk from tail does not reach 20 at all. Both bugs print a list that looks almost right, which is why the debugging section later in this lesson prints both directions.

Adding at the front follows the same shape, with head in place of tail. Set n.next = self.head, then self.head.prev = n, then self.head = n. The extra case is the empty list. If self.head is None, there is no old head to link. The method must set both head and tail to the new node. Python allows that in one line: self.head = self.tail = n. Python assigns from left to right, so self.head gets the node first and self.tail gets the same node second.

Removing a node you hold

This is the operation that makes doubly linked lists worth their extra memory. Suppose you have a reference n to a node somewhere in the middle, and you want to remove it. You never walk. You read n.prev and n.next, and you fix those two neighbours so that they point at each other.

The method has two checks, and each one handles one side:

def remove(self, n):
    if n.prev is not None:
        n.prev.next = n.next
    else:
        self.head = n.next
    if n.next is not None:
        n.next.prev = n.prev
    else:
        self.tail = n.prev

Read the first check. If the node has a predecessor, that predecessor's next should skip over n and point at n.next. If the node has no predecessor, it is the head, so the head moves to n.next. The second check does the mirror image for the node after n. If there is a successor, its prev skips back over n. If there is no successor, n was the tail, so the tail moves back to n.prev.

Work through three cases on the list 5 <-> 10 <-> 20 <-> 30.

• Remove 20 (a middle node). n.prev is node 10, so 10.next becomes node 30. n.next is node 30, so 30.prev becomes node 10. Node 20 has no references left. The list is 5 <-> 10 <-> 30.
• Remove 5 (the head). n.prev is None, so head moves to node 10. n.next is node 10, so 10.prev becomes None. The list is 10 <-> 20 <-> 30.
• Remove 30 (the tail). n.next is None, so tail moves to node 20. n.prev is node 20, so 20.next becomes None. The list is 5 <-> 10 <-> 20.

The two checks handle the head and tail cases with no extra code. Compare this with the singly list, where removing the head needed its own method and removing a middle node needed a walk. The doubly list costs one more reference per node, and it removes a known node in O(1) time.

Inserting in the middle, step by step

Inserting in the middle of a doubly list is the operation that most often goes wrong, because four references must change and the order matters. Suppose the list is 10 <-> 30, and you hold a reference node to the node holding 10. You want to insert a new node holding 20 right after node. The new node is n.

Here are the four links, with the order you must use.

1. n.prev = node. The new node learns its predecessor, which is 10. Nothing else is touched.
2. n.next = node.next. The new node learns its successor, which is 30. This reads node.next while it still holds 30.
3. node.next.prev = n. The node 30 is told that its predecessor is now the new node. This line reads node.next again, so it must run before step 4 changes node.next.
4. node.next = n. The node 10 is told that its successor is the new node. This is the last step, because it removes the only path to 30 from node.

Trace the state of the four affected references, starting with node.next equal to 30.

Two things stand out. The chain forward is correct only after step 4, because the first three steps make the new node reachable backward but not forward. And the order of steps 3 and 4 matters. If step 4 ran first, node.next would already be the new node, and step 3 would set the new node's own prev to itself, which breaks the list. The rule is the same as before: fill in the new node's links first, then the neighbours, and change the link from the old node last.

If node is the tail, there is no node 30. Step 2 then sets n.next to None, and step 3 must be skipped, because node.next is None and it has no prev attribute to set. The new node also becomes the tail. A method that handles only the middle case fails on the tail, which is one more reason to test the last node by hand.

A program that runs the doubly list

The program below builds the list, prints it forward and backward, removes a middle node, the head and the tail, and prints after each change. It needs no input.

Output:

5 10 20 30
30 20 10 5
5 10 30
30 10 5
10 30
10

Trace the middle removal. lst.head.next.next is node 20, because the head is 5, its next is 10, and that node's next is 20. The call remove sets 10.next to 30 and 30.prev to 10. Forward printing follows next and gives 5 10 30. Backward printing starts at tail, which still holds 30, and follows prev, giving 30 10 5. Both directions agree, which is the check you want after every change.

The program never writes head.prev or tail.next directly. Those attributes are fixed by the two checks in remove, which is why one method serves the head, the middle and the tail.

Cost, memory and trade-offs

The doubly linked list changes the costs of several operations. Here they are side by side with the singly list from the previous lesson, using n for the number of nodes.

The trade-off is memory and bookkeeping. Each node holds one more reference, and every change must update up to four references instead of two. A code review often finds a bug where only one side of a link was updated. The reward is that removal and backward walks become simple. If your program never removes nodes in the middle and never walks backward, a singly list is smaller and easier to keep correct.

The O(1) removal has a condition you must not forget. You must already hold the node. Finding it by value still costs a walk, because the list has no index. The doubly list is fast at "remove this node", not at "remove the node holding 20".

Circular linked lists

A circular linked list has no None at its end. The last node's next points back at the first node, so following next forever brings you around the circle. Think of a merry-go-round. The horses form a loop with no first or last horse, and the ride keeps going until someone stops it. A music player on repeat works the same way: after the last song, the first song plays again.

A circular list usually keeps a tail reference, because adding at the end is then O(1) and the tail's next is the head. The code is nearly the same as the singly list, with one extra link:

class CNode:
    def __init__(self, val):
        self.val = val
        self.next = None
 
 
class CircularList:
    def __init__(self):
        self.head = None
        self.tail = None
 
    def add(self, v):
        n = CNode(v)
        if self.head is None:
            self.head = self.tail = n
            n.next = n              # one node points at itself
            return
        self.tail.next = n
        n.next = self.head          # close the circle
        self.tail = n

The empty-list case is the one that surprises people. A single node must point at itself, because the circle has only one node and its next must be a node. If you skip n.next = n, the list has one node whose next is None, and every walk that follows next once more fails. The line is required.

A circle has a useful property: every node has a real next, so the code that moves forward never has to check for the end. The price is that the walk needs its own stop condition. A walk on a line stops at None. A walk on a circle stops when it returns to a node you started from. This is why the stop test in a circle compares against the head. Keep that trade in mind when you choose between a line and a circle: the circle removes the end check and adds a start check.

Walking a circular list needs care. The loop condition cur is not None never becomes false, because no node has a None next. Python has no do ... while statement. The usual pattern is while True with a break at the end of the body, which runs the body once before the check:

def print_circle(self):
    if self.head is None:
        return
    cur = self.head
    while True:
        print(cur.val, end=" ")
        cur = cur.next
        if cur is self.head:
            break
    print()

The body prints the current value and moves on. Then the check asks whether cur is back at the head. The head is printed first, and the loop ends after the last node, because the node after the last one is the head again.

Here is the danger in plain words. If you write while cur is not None on a circular list, the loop never stops. The program keeps printing values until you press Ctrl+C or the time limit runs out. This is not an error message. It is output that never ends, which is harder to diagnose. Before you write a loop, ask "what makes this loop end?" and make sure the answer exists for the shape of list you have.

A round-robin turn order

Round-robin means each participant takes a turn in a fixed order, then the order starts again. A group game where players take turns is round-robin. So is a scheduler that gives each task a short slice of processor time in turn. A circular list is a natural fit, because after the last player the next turn belongs to the first.

The program below builds the circle from a range of player numbers, then prints seven turns for three players. It needs no input.

Output:

turn 1: player 1
turn 2: player 2
turn 3: player 3
turn 4: player 1
turn 5: player 2
turn 6: player 3
turn 7: player 1

The loop never checks whether cur is None, because it cannot be. The number of turns is independent of the number of players, and the circle makes the order repeat for any count. You could call round_robin(3, 100) and the same code would work. This is the value of a circle: it removes the special case of "back to the start".

The Josephus problem: removing from a circle

A famous puzzle makes the circular list useful for removal. Imagine n people stand in a circle, numbered from 1. Starting with person 1, count k people around the circle, and the k-th person is removed. Counting then continues from the next person still in the circle, and the process repeats. The last person left is the survivor. This is called the Josephus problem, after the first-century historian Flavius Josephus, who wrote about a similar story. Interviewers like it because a circular list makes the removal step simple, while an array needs careful index arithmetic. The code below needs k of 2 or more.

Here is the method for one removal with k = 3 on the circle 1 to 7. Counting starts at person 1, who is the first person. People 1 and 2 are counted, and person 3 is the third. To remove person 3 you need the node just before it, which is person 2. In general, you need the node before the k-th person, and that node is reached by moving k - 2 steps from the current person. For k = 3, that is one step.

The program below uses that rule in a loop. It removes people one at a time, collects their numbers and prints the survivor.

Output:

eliminated: 3 6 2 7 5 1
survivor: 4
k=2 eliminated: 2 4 6 1 5 3
k=2 survivor: 7

Trace the first two removals. Person 1 counts as 1 and person 2 as 2. The loop runs k - 2 = 1 time, so prev moves from 1 to 2. Person 3 is prev.next, so person 3 is removed and the link from 2 jumps to 4. Counting restarts at 4, so 4 is 1, 5 is 2 and 6 is 3. Person 6 goes next, and the output starts 3 6. Keep going and you reach the survivor 4 with the list reduced to one person.

The loop condition size > 1 is what ends the process. When one person is left, cur holds that person, and the loop has no more removals to do. The code never checks for None. The circle makes sure every node has a next, even when only one remains. The final cur.val is the survivor, because cur was set to out.next in the last removal, and with one person left that node is the survivor.

The same code with k = 2 gives the survivor 7 for n = 7. You can check that by hand, and the output above shows the same result.

Real use: a browser history

Browsers are the textbook use of the doubly linked list. Each page you open is a node. The Back button moves to the previous page, and the Forward button moves to the next page. A new visit after pressing Back throws away the forward pages, because they no longer lead anywhere useful. The doubly list makes each of these actions a single reference change.

The program below models that history. The first page is home. The commands are in a list at the bottom of the program, so the program needs no input. Read the rule in visit carefully, because it is the one that makes this a real browser model. Setting self.current.next to the new page cuts the old forward chain. Nothing points at the old forward pages anymore, and Python frees them.

Output:

now at news
now at sport
now at news
now at home
already at the first page
now at news
now at blog
no forward page

The last two forward lines show the cut. After visit blog, the page sport is gone from the history, because news.next now points at blog. A forward from blog finds blog.next set to None and reports that there is no forward page. This is the behaviour a real browser shows.

The LRU cache idea

A cache keeps recently used items so that repeated lookups are fast. When it is full, it must throw away something, and the common rule is to throw away the least recently used item, which is called LRU. A cache with a capacity of three might hold A, B and C, inserted in that order. Using A again moves it to the front of the recency order, so the item that goes next is B.

The standard design combines two structures. A hash table, which Python's dict is, finds any item by key in O(1) average time. A doubly linked list keeps the order of use. Each access moves the node to the front, and eviction removes the node at the back. Moving a node is O(1), because the table gives you the node directly and the doubly list lets you unlink it without a walk. A singly list would need a walk to find the node before it, which would make every access O(n).

Python already has this combination in two forms. collections.OrderedDict keeps keys in order and has a move_to_end method. functools.lru_cache is a decorator that caches the results of a function and drops the least recently used result when it is full. You will use these in real code. The doubly list is still the structure to understand, because it is what makes the move cheap.

Common mistakes and the messages you will see

Updating only one side of a link. In add_last, forgetting self.tail.next = n gives a list that prints forward as 10 20, while backward printing shows 30 20 10. The fix is to check both directions after every change. The debugging section below walks through this.

Forgetting the head or tail when the list changes size. When you remove the only node, both head and tail must become None. If tail still refers to the removed node, the next add_last links a new node to a node no longer in the list, and the list silently loses it.

Calling remove on None. Removing a node that does not exist is the most common crash. Suppose the list is empty and you call lst.remove(lst.tail). The argument is None, so n.prev inside remove fails. Python reports:

AttributeError: 'NoneType' object has no attribute 'prev'

The attribute prev was read, and the object that has no such attribute is None. The traceback above this line shows the call from your code and the line in remove that failed. Fix it by checking if n is None: return at the top of remove, or by never calling remove on an empty list.

Looping forever on a circle. A while cur is not None loop on a circular list does not raise an error. It prints values forever. If your program seems frozen with output still scrolling, you are on a circle with the wrong loop condition. Switch to while True with a check against the head, as the print_circle method above does.

Stopping the circle loop too early. A loop that checks cur.next is self.head and breaks before it prints cur misses the last node. Compare cur is self.head after moving cur forward, as the print_circle method above does.

Debugging walkthrough

Suppose you wrote add_first like this, and you see the output below.

def add_first(self, v):
    n = DNode(v)
    if self.head is None:
        self.head = self.tail = n
        return
    n.next = self.head
    self.head = n              # the old head never gets its prev set

You add 5 to the list 10 <-> 20, print forward and get 5 10 20, which looks right. Then you print backward starting at tail, and you get 20 10. The 5 is missing from the backward walk. This tells you that one direction is correct and the other is not.

The bug is that self.head.prev is never set to n. Node 10 still has prev set to None, so the backward walk stops at 10 and never reaches 5. The forward walk follows next from the head, so it works. The fix is the line self.head.prev = n between the two existing lines, and you should keep it before self.head = n, so that self.head still points at the old node when you set its prev.

The general routine is the same as in the previous lesson. Print before and after the change. Draw the list with both arrows. Step through the code and list which references change. Then check both directions of the list after every operation, because a doubly list can look correct in one direction and be broken in the other.

Variations and edge cases

Test your doubly list on these cases before you trust it.

• Empty list. head and tail are both None. Printing forward and backward should print nothing.
• One node. The head and the tail are the same node, and its prev and next are both None. Removing it must leave both head and tail as None.
• Two nodes. Removing either one must leave a list whose single node has both prev and next set correctly.
• Removing a node twice. After remove(n), the node n still holds its old prev and next attributes. If the neighbours change in between, a second remove(n) links old nodes back in, and the forward and backward walks disagree. Exercise 6 below clears the two attributes, which makes a second call empty the whole list. Either way, never remove the same node twice.

For circular lists, test the single node, where the node must point at itself, and the two-node case, where each node points at the other. Print the circle with print_circle and check that it prints each value once.

Interview patterns

Doubly list design questions. You may be asked to design a list that supports insert, delete and reverse. Say that the doubly list gives O(1) deletion when you hold the node, and that the price is two references per node.

Cycle detection. A list can contain an accidental loop, so a walk that follows next never ends. The previous lesson's middle-finding idea, with two pointers at different speeds, also detects a loop. A circular list is the case where the loop is intended.

Josephus and round-robin. Many problems are a circle with removals. The pattern is to keep a reference to the node before the target, unhook the target, and move on. The Josephus program above is the template.

How to structure the answer. A good answer to a doubly list question follows three beats. First, say which node you hold and which references point at it. Second, list the links that change, in order, and say why that order is safe. Third, say which edge cases you handle: the empty list, the head, the tail and the one-node list. Interviewers mostly listen for the second beat, because it shows whether you understand the structure or only remember a method.

The one-node check. Interviewers often look for whether you handle the single-node circle, where the node points at itself. Mention it before they ask.

Real-world uses

The browser history is the clearest example, and the LRU cache is a common production use. Music players use the same idea for previous and next track. Operating systems use circular lists for round-robin scheduling, where each task gets a turn and the scheduler returns to the first task after the last. Some text editors use doubly linked structures for undo and redo, because each change is a node that can be stepped in either direction.

Practice

Try these before you open the solutions. Trace each method on a small list. Each exercise adds a method to the class named in it, using the classes from this lesson.

Exercise 1 (easy). Write add_first(self, v) for DoublyList. Count how many references change, and check that the empty-list case sets both head and tail.

Show the answer

def add_first(self, v):
    n = DNode(v)
    if self.head is None:
        self.head = self.tail = n
        return
    n.next = self.head
    self.head.prev = n
    self.head = n

Three references change in the general case: n.next, self.head.prev, and self.head. The n.prev attribute is already None, which is correct for the new first node. The empty case sets head and tail together.

Exercise 2 (easy). Explain why the singly linked list needs a walk to remove a node you hold, but the doubly list does not.

Show the answer

The singly node knows only its next. To unhook it, you must change the next attribute of the node before it, and the list gives you no way to reach that node except by walking from the head. The doubly node knows its prev, so the node before it is available in one step. The removal then changes prev.next and next.prev, both of which are reachable directly. The cost is O(1) instead of O(n).

Exercise 3 (easy). Write size(self) for CircularList. The list stores one head reference. An empty list returns 0.

Show the answer

def size(self):
    if self.head is None:
        return 0
    count = 0
    cur = self.head
    while True:
        count += 1
        cur = cur.next
        if cur is self.head:
            break
    return count

The loop counts the head first, then moves forward until the walk returns to the head. A single node points at itself, so cur becomes the head again after one step and the count is 1.

Exercise 4 (medium). Write remove_first(self) and remove_last(self) for DoublyList. Both must handle a list with one node.

Show the answer

def remove_first(self):
    if self.head is None:
        return
    self.head = self.head.next
    if self.head is not None:
        self.head.prev = None
    else:
        self.tail = None
 
def remove_last(self):
    if self.tail is None:
        return
    self.tail = self.tail.prev
    if self.tail is not None:
        self.tail.next = None
    else:
        self.head = None

With one node, removing the first node makes head None, and the else branch clears tail too. Without that branch, tail would still refer to the removed node.

Exercise 5 (medium). Write insert_after(self, node, v) for DoublyList. The new node goes directly after node. If node is the tail, update the tail.

Show the answer

def insert_after(self, node, v):
    n = DNode(v)
    n.prev = node
    n.next = node.next
    if node.next is not None:
        node.next.prev = n
    else:
        self.tail = n
    node.next = n

Set the new node's two links first, because they read node.next, which is about to change. Then fix the old successor's prev, or move the tail if there was no successor. Finally, link node forward to the new node.

Exercise 6 (medium). Write remove(self, n) for DoublyList so that it does nothing when n is None, and clears n.prev and n.next after unhooking the node.

Show the answer

def remove(self, n):
    if n is None:
        return
    if n.prev is not None:
        n.prev.next = n.next
    else:
        self.head = n.next
    if n.next is not None:
        n.next.prev = n.prev
    else:
        self.tail = n.prev
    n.prev = None
    n.next = None

The None check prevents the error from the common mistakes section. Clearing the two attributes last means the lines above still see the neighbours they need. Clearing them does not make a second remove safe. After the clear, the node has no neighbours, so the two else branches set head and tail to None and wipe the whole list, even though other nodes remain. The real rule is never to remove the same node twice.

Exercise 7 (medium). Write node_at(self, index) for DoublyList. It returns the node at index, counting from 0 at the head, or None if the index is out of range. Walk from the nearer end, so the walk takes at most about n / 2 steps.

Show the answer

def node_at(self, index):
    if index < 0:
        return None
    size = 0
    c = self.head
    while c is not None:
        size += 1
        c = c.next
    if index >= size:
        return None
    if index < size // 2:
        cur = self.head
        for _ in range(index):
            cur = cur.next
        return cur
    cur = self.tail
    for _ in range(size - 1 - index):
        cur = cur.prev
    return cur

The first loop counts the size, which costs O(n). The walk then starts from the nearer end, so the walk itself is at most about n / 2 steps. The total time stays O(n), but the walk is half as long. The prev attributes are what make the backward walk possible at all.

Exercise 8 (hard). Write move_to_front(self, n) for DoublyList. The node moves to the head in O(1) time, without a walk. This is the core of an LRU cache.

Show the answer

def move_to_front(self, n):
    if n is self.head:
        return                          # already at the front
    self.remove(n)                      # unhook it, using the method above
    n.prev = None
    n.next = self.head
    self.head.prev = n
    self.head = n

The remove call fixes both neighbours and updates the tail if needed. A list with one node never reaches the last four lines, because the first check returns early when n is already the head. Then the node goes in at the front, using the same steps as add_first. Every step is a constant number of reference changes, so the whole move is O(1) when you already hold n.

Exercise 9 (hard). In plain words, explain what would go wrong in the browser model if visit set p.next = self.current.next instead of self.current.next = p, and kept the pages after the current one.

Show the answer

The new page would not be linked from the current page at all, because self.current.next would still refer to the old forward page. A forward press would show the old page again, not the new one. In a real browser, a new visit replaces the forward history, so the code must set self.current.next to the new page. The old forward pages then lose their last reference and Python frees them.

What you now know

• A doubly linked node has prev and next, so you can walk both ways and unhook a node you hold in O(1) time.
• Removing a node means fixing its two neighbours, and the head and tail are the two cases where one side is None.
• A circular list links the last node back to the first. Walk it with while True and a check against the head, never with while cur is not None.
• Round-robin turns and the Josephus problem are natural uses of a circle, because the last node's successor is the first node.
• A browser history is a doubly list where a new visit cuts the forward chain. The LRU cache combines a doubly list with a hash table.
• Check both directions of a doubly list after every change, because a one-sided link bug can look correct when you print only one direction.