Data Structures & Algorithms (DSA) Module 7 – Linked lists
Doubly linked and circular lists
Doubly linked lists with sentinels remove a node you hold in O(1), and circular lists drive round-robin turns: Python code, library types and Josephus.
What you will learn
- Implement a doubly linked list with sentinel nodes
- Use circular lists for round-robin processing
- Choose the standard-library list types appropriately
- Prove that insertion and removal keep every next and prev link paired
Before you start
What you’ll learn · Before you start
What you will learn
- Implement a doubly linked list with sentinel nodes
- Use circular lists for round-robin processing
- Choose the standard-library list types appropriately
- Prove that insertion and removal keep every next and prev link paired
Before you start
On this page
A doubly linked list gives every node two references: next to the node after it and prev to the node before it.
A circular list joins the ends, so that the last node’s next leads back to the first. The extra reference of a
doubly linked list buys what a singly linked list cannot do cheaply: walking backwards, and removing a node you
already hold in O(1), because the node knows both of its neighbours. Circular lists suit anything that takes turns,
such as round-robin scheduling, because a walk never falls off the end. The price is memory and care: one more
pointer per node, four link updates per insertion, and loops over circular lists that need a stopping rule of their
own. This lesson builds both kinds in Python, compares the list types the standard libraries ship, and practises the
circle on the Josephus problem.
Two links per node, and a sentinel at each end
Removing a node from a doubly linked list takes two assignments: the node before it skips forward with
node.prev.next = node.next, and the node after it skips back with node.next.prev = node.prev. Inserting takes
four, two for the new node’s own links and one for each neighbour. Written plainly, each of these needs checks for an
empty reference at the first and the last node. Two sentinel nodes remove those checks: a head sentinel before
the first real node and a tail sentinel after the last, created with the list and never removed. Every real node then
has a node on both sides, and an empty list is just the two sentinels pointing at each other.
Two sentinels, and remove(node) in two link changes
Text description of the diagram
The list holds three tabs, docs, mail and maps, between two sentinel nodes, the head sentinel and the tail sentinel, which hold no tab and are never removed. Every link goes both ways: each node's next points at the node after it and its prev at the node before it.
The drawing shows remove on the mail node. Before the removal, docs and maps both point at mail; those links are dashed. The removal makes two changes: the next of docs now points at maps, and the prev of maps now points at docs. Mail can no longer be reached in either direction.
Because the sentinels are always there, every real node has a node on both sides, so the same two assignments remove the first tab, the last tab or the only tab, and no step checks for an empty reference.
| Operation | Time | Extra space | Note |
|---|---|---|---|
| push_front(v), push_back(v) | O(1) | O(1) | insert after a sentinel |
| insert_after(node, v) | O(1) | O(1) | four link updates |
| remove(node) for a node you hold | O(1) | O(1) | O(n) in a singly linked list |
| find(v) | O(n) | O(1) | from either end |
| walk backwards | O(n) | O(1) | follow prev from the tail sentinel |
The module below implements the list with sentinels, and the program beside it keeps browser tabs in it. A dict maps each tab’s name to its node, so closing a tab needs no search at all, the idea behind the LRU cache at the end of this module.
dlist/tabs.py
"""Browser tabs in a doubly linked list: a dict hands over the node of any tab, so closing it needs no search."""
from dlist import DoublyLinkedList
bar = DoublyLinkedList()
tab = {}
for name in ["docs", "mail", "maps", "music"]:
tab[name] = bar.push_back(name)
print("left to right:", " <-> ".join(bar.forwards()))
print("right to left:", " <-> ".join(bar.backwards()))
bar.remove(tab.pop("maps"))
print("close maps: ", " <-> ".join(bar.forwards()))
tab["news"] = bar.insert_after(tab["docs"], "news")
print("open news after docs:", " <-> ".join(bar.forwards()))
current = tab["news"]
print("from news, the tab on the left is", current.prev.value, "and on the right", current.next.value)
bar.remove(tab.pop("docs"))
print("close docs: ", " <-> ".join(bar.forwards()), "| backwards:", " <-> ".join(bar.backwards()))
print("tabs open:", bar.size)Output
left to right: docs <-> mail <-> maps <-> music right to left: music <-> maps <-> mail <-> docs close maps: docs <-> mail <-> music open news after docs: docs <-> news <-> mail <-> music from news, the tab on the left is docs and on the right mail close docs: news <-> mail <-> music | backwards: music <-> mail <-> news tabs open: 3
Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 tabs.py
dlist/dlist.py
"""A doubly linked list with two sentinel nodes (lesson dsa/doubly-and-circular-lists)."""
class Node:
__slots__ = ("value", "prev", "next")
def __init__(self, value=None):
self.value = value
self.prev = None
self.next = None
class DoublyLinkedList:
def __init__(self):
# Two sentinels that are never removed, so every real node always has a node on both sides.
self.head = Node()
self.tail = Node()
self.head.next = self.tail
self.tail.prev = self.head
self.size = 0
def insert_after(self, node, value):
"""O(1): link a new node between node and node.next, and return it."""
new = Node(value)
new.prev = node
new.next = node.next
node.next.prev = new
node.next = new
self.size += 1
return new
def push_front(self, value):
return self.insert_after(self.head, value)
def push_back(self, value):
return self.insert_after(self.tail.prev, value)
def remove(self, node):
"""O(1): unlink a node you hold; its two neighbours now point at each other."""
node.prev.next = node.next
node.next.prev = node.prev
node.prev = node.next = None
self.size -= 1
return node.value
def forwards(self):
node = self.head.next
while node is not self.tail:
yield node.value
node = node.next
def backwards(self):
node = self.tail.prev
while node is not self.head:
yield node.value
node = node.prevRuns on this device, in your browser. The first run downloads Python (about 13.5 MB), which is kept for the next runs.
Your run, in this browser
Closing “maps” and then “docs” took constant time each, whatever the number of tabs, and the walk from the right shows
that the prev links were kept as carefully as the next links. The memory price is one more reference per node,
8 bytes on a 64-bit computer, before the value itself.
Circular lists and round-robin turns
In a circular singly linked list one reference is enough: keep tail, the last node, and tail.next is the first,
so both ends are one step away. Giving the next job its turn is one pointer move, tail = tail.next, and removing the
job after tail is one link change. A walk stops when it comes back to its starting node, because no next is ever
empty. The scheduler below gives each job at most 3 units of time per turn and drops a job from the circle once it
finishes.
"""Round-robin turns over a circular singly linked list: each job runs for at most one time slice, a finished job
leaves the circle, and the next turn is always tail.next."""
class Job:
__slots__ = ("name", "left", "next")
def __init__(self, name, left):
self.name = name
self.left = left
self.next = None
def run_round_robin(jobs, time_slice):
tail = None # the job that ran last; tail.next is the job whose turn is next
for name, work in jobs:
job = Job(name, work)
if tail is None:
job.next = job # a circle of one points at itself
else:
job.next = tail.next
tail.next = job
tail = job
clock, finished = 0, []
while tail is not None:
job = tail.next
ran = min(time_slice, job.left)
clock += ran
job.left -= ran
if job.left > 0:
print(f"t={clock:2} {job.name} ran {ran}, {job.left} left")
tail = job # rotate: one pointer moves, nothing is copied
else:
print(f"t={clock:2} {job.name} ran {ran}, finished")
finished.append(job.name)
if job is tail:
tail = None # it was the last job in the circle
else:
tail.next = job.next # unlink the finished job
return finished
order = run_round_robin([("A", 5), ("B", 2), ("C", 7), ("D", 3)], time_slice=3)
print("finishing order:", order)Output
t= 3 A ran 3, 2 left t= 5 B ran 2, finished t= 8 C ran 3, 4 left t=11 D ran 3, finished t=13 A ran 2, finished t=16 C ran 3, 1 left t=17 C ran 1, finished finishing order: ['B', 'D', 'A', 'C']
Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 round_robin.py
Runs on this device, in your browser. The first run downloads Python (about 13.5 MB), which is kept for the next runs.
Your run, in this browser
Trace it once by hand. After B and D finish, only A and C are left, and A, which arrived first, gets its turn first.
A circle of one job points at itself, which is why the code checks whether the finished job is tail before it
unlinks anything. Counting round a circle and removing every k-th member is the Josephus problem, which the exercise
below asks you to simulate.
Which list type to use in each language
| Criterion | Python | Java | C++ | Go |
|---|---|---|---|---|
| Doubly linked list | None in the library | LinkedList | std::list | container/list |
| Singly linked list | None in the library | None in the library | std::forward_list | None in the library |
| Circular list | None in the library | None in the library | None in the library | container/ring |
| Queue or stack | collections.deque | ArrayDeque | std::deque | A slice |
| When to choose | deque for both ends; write nodes when you must hold positions | ArrayDeque unless you remove through an iterator | std::list when iterators must stay valid | container/list or container/ring for held positions |
Java’s LinkedList is documented as a doubly linked list, yet the ArrayDeque documentation says that it is likely
to be faster than LinkedList when used as a queue. Python ships no general linked list: collections.deque appends
and pops at either end in O(1), and its documentation warns that indexing slows to O(n) in the middle. C++ has
std::list, doubly linked, and std::forward_list, singly linked. Go’s container/list is a doubly linked list,
and container/ring implements circular lists directly. The rule of thumb follows: use an array-based deque for
queues and stacks, and a real linked list only when you insert or remove at positions you already hold.
Practise: the Josephus circle
Simulate the circle with a circular list and return the order in which people leave. The sample tests compare your answer with a slow model on every circle of up to 40 people and every count from 1 to 12.
Exercise · Easy · Python, JavaScript
Print the order in which a circle of people leaves
People numbered 1 to n stand in a circle. Counting starts at person 1 and goes round the circle; every k-th person counted leaves, and counting goes on from the next person still in the circle, until nobody is left. Write elimination_order(n, k) (in JavaScript eliminationOrder(n, k)), which returns the numbers in the order the people leave. The last number is the survivor.
elimination_order(7, 3)is[3, 6, 2, 7, 5, 1, 4]: 3 leaves first, then counting starts again at 4.elimination_order(3, 5)is[2, 3, 1]: a count longer than the circle simply goes round again.elimination_order(1, 4)is[1], andelimination_order(0, 2)is[].
Use a circular linked list: keep a reference to the person before the one being counted, so that removing someone is one link change. The sample tests compare your answer with a slow model on every circle of up to 40 people.
Python · Starter code · josephus.py
def elimination_order(n, k):
"""The numbers 1..n in the order people leave the circle when every k-th person counted leaves (k >= 1)."""
return []The sample tests · test_josephus.py
from josephus import elimination_order
def model(n, k):
"""Plainly right and slow: the circle as a Python list."""
people, i, out = list(range(1, n + 1)), 0, []
while people:
i = (i + k - 1) % len(people)
out.append(people.pop(i))
return out
def test_seven_people_every_third():
"""the example: n = 7, k = 3"""
assert elimination_order(7, 3) == [3, 6, 2, 7, 5, 1, 4]
def test_count_longer_than_the_circle():
"""a count longer than the circle goes round again"""
assert elimination_order(3, 5) == [2, 3, 1]
def test_every_person_in_turn():
"""with k = 1 people leave in their own order"""
assert elimination_order(6, 1) == [1, 2, 3, 4, 5, 6]
def test_one_person_and_nobody():
"""a circle of one, and an empty circle"""
assert elimination_order(1, 4) == [1]
assert elimination_order(0, 2) == []
def test_every_pair_against_the_model():
"""every n from 1 to 40 and every k from 1 to 12 agree with the model"""
for n in range(1, 41):
for k in range(1, 13):
assert elimination_order(n, k) == model(n, k), (n, k)
def test_the_result_is_a_permutation():
"""everyone leaves exactly once"""
assert sorted(elimination_order(97, 7)) == list(range(1, 98))JavaScript · Starter code · josephus.mjs
/** The numbers 1..n in the order people leave the circle when every k-th person counted leaves (k >= 1). */
export function eliminationOrder(n, k) {
return [];
}The sample tests · josephus.test.mjs
import { test, assert } from 'mysmartcopilot:test';
import { eliminationOrder } from './josephus.mjs';
/** Plainly right and slow: the circle as an array. */
function model(n, k) {
const people = Array.from({ length: n }, (_, i) => i + 1);
const out = [];
let i = 0;
while (people.length) {
i = (i + k - 1) % people.length;
out.push(people.splice(i, 1)[0]);
}
return out;
}
test('the example: n = 7, k = 3', () => {
assert.deepEqual(eliminationOrder(7, 3), [3, 6, 2, 7, 5, 1, 4]);
});
test('a count longer than the circle goes round again', () => {
assert.deepEqual(eliminationOrder(3, 5), [2, 3, 1]);
});
test('with k = 1 people leave in their own order', () => {
assert.deepEqual(eliminationOrder(6, 1), [1, 2, 3, 4, 5, 6]);
});
test('a circle of one, and an empty circle', () => {
assert.deepEqual(eliminationOrder(1, 4), [1]);
assert.deepEqual(eliminationOrder(0, 2), []);
});
test('every n from 1 to 40 and every k from 1 to 12 agree with the model', () => {
for (let n = 1; n <= 40; n++) {
for (let k = 1; k <= 12; k++) assert.deepEqual(eliminationOrder(n, k), model(n, k), `n = ${n}, k = ${k}`);
}
});
test('everyone leaves exactly once', () => {
const order = eliminationOrder(97, 7);
assert.deepEqual([...order].sort((a, b) => a - b), Array.from({ length: 97 }, (_, i) => i + 1));
});A hint
Build the circle as nodes whose next points at the next person and whose last node points back at person 1, and keep prev on person n, the node before person 1. To remove the k-th person, move prev forward k - 1 times; the node after prev is the one who leaves, and prev.next = prev.next.next closes the circle behind them.
Results of the sample tests
| Test | Result | Details |
|---|
What your code printed
The sample tests run on this device, in your browser (Pyodide, QuickJS): nothing is sent to mysmartcopilot.com. The first run of each language downloads it: Python (about 13.5 MB) or JavaScript (about 0.6 MB), which is kept for the next runs. A check in your browser is feedback for you, not proof that the code is right for every input.
Check yourself
5 questions about this lesson. Every answer and why it is right is on the page, behind “Show the answer”. Your score stays in this browser.
The link invariant, proved, and the list in four more languages Pro: opens with a Pro, Premium or Ultimate pass
Every change to a doubly linked list rewrites up to four links, and a slip in one of them leaves a list that reads correctly in one direction only. This part states the invariant every operation must keep, proves that insertion and removal keep it, reproduces the classic one-link slip, and runs the same list in JavaScript, Java, C++ and Go.
In this part:
- The invariant: every link has a partner pointing back
- Why insertion and removal keep it: the proof
- A remove that forgets one link, reproduced
- The same list in JavaScript, Java, C++ and Go
4 runnable examples (C++, Go, Java, JavaScript, dlist.py, dlist_session.py, one_link_short.py, session.py) · about 3 minutes
Opening this part with your pass…
This part opens with any MySmartCoPilot pass.
- Pro pass · 1 week₹79$2.99
- 30 days₹179$5.99
- 1 year₹1,699$45
One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.
Passes can’t be bought right now, so this part can’t be opened at the moment. The free part above stands on its own. If you have a pass, enter your licence key.
It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).
Circular lists at scale: the Josephus count, checked and measured Pro: opens with a Pro, Premium or Ultimate pass
A circle that loses one member at a time is the Josephus problem, and it shows both when a circular list is the right
tool and when arithmetic beats it. This part derives the recurrence for the survivor, checks it against the
simulation for twenty circles, and times the circular list against a Python list with pop(i).
In this part:
- The survivor without a simulation: the recurrence and its proof
- Twenty circles, simulated and checked
- Measured: the circle against list.pop(i)
2 runnable examples (Python) · about 2 minutes
Opening this part with your pass…
This part opens with any MySmartCoPilot pass.
- Pro pass · 1 week₹79$2.99
- 30 days₹179$5.99
- 1 year₹1,699$45
One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.
Passes can’t be bought right now, so this part can’t be opened at the moment. The free part above stands on its own. If you have a pass, enter your licence key.
It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).
Library lists in practice: iterators, rings and queues, measured Pro: opens with a Pro, Premium or Ultimate pass
The library types save you from writing nodes, but each comes with rules about which references survive a change and with a point where an array-based structure beats it. Each rule is run here in C++, Go or Java, and the part closes with the boundary cases worth a test and a handful of questions with their answers.
In this part:
- Which references survive a change: std::list against std::vector
- Go’s container/ring for turns
- Java’s LinkedList against ArrayDeque as a queue, measured
- Edge cases to test before you trust a list
- A practice set with answers
4 runnable examples (C++, Go, Java, library_session.py, queue_session.py, session.py) · about 3 minutes
Opening this part with your pass…
This part opens with any MySmartCoPilot pass.
- Pro pass · 1 week₹79$2.99
- 30 days₹179$5.99
- 1 year₹1,699$45
One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.
Passes can’t be bought right now, so this part can’t be opened at the moment. The free part above stands on its own. If you have a pass, enter your licence key.
It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).
Interview questions
-
Fresher · Warm-up
What does a circular linked list give you that a list with head and tail references does not?
Mostly convenience for code that goes round. In a circular singly linked list one reference to the last node reaches both ends, because its next is the first node, so adding at either end and passing the turn to the next node are O(1), and a rotation is a single pointer move with nothing copied. There is no end to fall off, which suits round-robin turns and any walk that wraps around. The costs are traps rather than time: a loop cannot stop at an empty reference and must stop when it returns to its start, a list of one node points at itself, and the empty list needs a case of its own. A list with head and tail references can do the same jobs with one more reference to keep right.
-
Fresher to mid
After a deletion, your doubly linked list prints correctly from front to back, but walking from the back still shows the deleted item. What went wrong, how do you find every bug of this kind before release, and how do sentinel nodes change the code?
-
Mid to senior
A Java service buffers 20 million small integers in a LinkedList<Integer> used as a first-in, first-out queue, and the heap is far larger than the data suggests. Estimate the memory per element, compare ArrayDeque<Integer> and a ring buffer of int, and choose one.
-
Mid to senior
Design the run queue of a round-robin scheduler: jobs arrive at any time, finish at any time, and the next job must get its turn in O(1). Which list do you use, where does a new job go, and what goes wrong when a job finishes while it holds the turn?
Key takeaways
- A doubly linked list stores
prevandnextin every node, so it walks both ways and removes a node you hold in O(1), at the cost of one more pointer per node and four link updates per insertion. - Two sentinels give every real node a neighbour on both sides, so the same few assignments work at every position.
- Circular lists make turn-taking a single pointer move; every loop over one stops when it returns to its start.
- Standard libraries ship these lists, but an array-based deque is the better queue in Java and Python.
References
- doubly linked list (Dictionary of Algorithms and Data Structures) (National Institute of Standards and Technology (NIST))
- collections.deque (The Python Standard Library) (Python Software Foundation)
- LinkedList (Java SE 25 API) (Oracle)
- ArrayDeque (Java SE 25 API) (Oracle)
- std::list (cppreference.com)
- std::vector (cppreference.com)
- std::forward_list (cppreference.com)
- Package container/list (The Go Authors)
- Package container/ring (The Go Authors)
- Source of container/list (list.go) (The Go Authors)
- Computer Science Curricula 2023: Algorithmic Foundations (AL) (ACM, IEEE Computer Society and AAAI)
Related tools
Report a problem with this lesson
Kept only in this browser. Your Learn progress