Circular and doubly linked lists
Definitions, invariants, operations, complexities, pointer-update steps, and Python examples for circular singly, doubly, and circular doubly linked lists.
Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.
Why it matters
Circular and doubly linked lists help when data must be frequently inserted/removed from arbitrary positions with constant-time pointer updates, without shifting elements as in arrays. Engineers use them in LRU caches, undo–redo stacks with bidirectional traversal, playlist queues that loop, job schedulers, and memory allocators.
Key ideas
- Pointer (reference): A variable that holds the address (identity) of another node; in diagrams we draw arrows. In Python, this is a reference to another object.
- Head: The pointer/reference to the first node of a linked list. For an empty list, head = null (None in Python).
- Tail: The last node of a non-circular list whose next pointer is null; for circular lists, tail.next points back to head.
- Predecessor / Successor: For a node x in a list, its predecessor is the node just before x; its successor is the node just after x.
- Doubly linked list (DLL): A linked structure where each node stores two pointers: prev (to predecessor) and next (to successor). The first node’s prev = null; the last node’s next = null.
- Circular singly linked list (CSLL): A linked structure where each node has next only, and the last node’s next points back to the head. For a non-empty CSLL, no next is null; for an empty CSLL, head = null.
- Circular doubly linked list (CDLL): A linked structure where each node has prev and next, and the list is circular in both directions: head.prev = tail and tail.next = head. For an empty CDLL, head = null.
- Sentinel (dummy) node: A special node (not holding user data) used as a fixed boundary to simplify insert/delete; in CDLL a common pattern is a circular list where the sentinel’s next is the first element and prev is the last.
- Invariants (exact statements you can quote):
- DLL invariant: For every node x except the first and last, x.prev.next = x and x.next.prev = x; for the first node f, f.prev = null; for the last node l, l.next = null.
- CSLL invariant: If head ≠ null, then by following next repeatedly you visit each node exactly once and return to head; exactly one cycle containing all nodes exists.
- CDLL invariant: If head ≠ null, head.prev.next = head and head.next.prev = head; tail.next = head and head.prev = tail; following next (or prev) repeatedly cycles through all nodes.
- Empty-list invariant: If head = null, the list contains no nodes, and no operation may dereference head.
- Time complexity model (RAM model): Pointer/reference assignment and comparison are O(1). Dereferencing a known pointer is O(1). Traversing k nodes costs O(k). Array random access by index is O(1); linked list access to i-th element is O(i).
- Operation costs (assuming we already hold a direct pointer to the target position/node):
- Insert at head/tail in DLL or CDLL: O(1).
- Insert after/before a given node in DLL/CDLL: O(1).
- Delete a given node (with pointer to it) in DLL/CDLL: O(1).
- Search by key (if unsorted): O(n) in DLL/CSLL/CDLL, because you may traverse all n nodes.
- Traversal (forward or backward for DLL/CDLL): O(n).
- Space overhead:
- Singly linked list: one pointer per node.
- DLL/CDLL: two pointers per node (extra prev), trading space for O(1) deletions without needing the predecessor.
- Edge cases to handle:
- Empty list: head = null; insertion creates the first node; deletion is a no-op.
- Singleton list: head.next = null and head.prev = null (DLL); head.next = head (CSLL); or head.next = head and head.prev = head (CDLL). Deleting the only node must set head = null.
- Head/tail updates: When operations touch the first or last node, update head (and tail or their circular equivalents) properly.
- Why circular? Eliminates null checks at ends and supports algorithms that wrap around naturally (e.g., round-robin scheduling, Josephus problem). Traversal must stop using a visited-head check to avoid infinite loops.
- Why doubly? Easy O(1) delete of the current node and bidirectional traversal. Useful for LRU caches (move-to-front and delete from middle in O(1)).
Exact pointer-update recipes (diagram notes follow each):
- Insert x after node p in DLL:
- x.prev = p
- x.next = p.next
- if p.next ≠ null: p.next.prev = x
- p.next = x
- If p was tail, update tail = x Diagram to draw: three boxes in a row labeled p, oldSucc, (space), and a new box x above; draw arrows implementing steps; label prev/next on each arrow; cross out old arrows replaced in step 3.
- Insert x before node p in DLL: symmetric to “after”; swap roles of prev/next and head/tail updates.
- Delete node p from DLL (p is known, and p is in the list):
- if p.prev ≠ null: p.prev.next = p.next else head = p.next
- if p.next ≠ null: p.next.prev = p.prev else tail = p.prev
- Optionally clear p.prev = p.next = null (avoids dangling references) Diagram: three boxes prev — p — next; cross the arrows from prev→p and p→next; draw prev→next and next→prev.
- Insert x in empty CDLL:
- head = x
- x.next = x.prev = x Diagram: single box x with next and prev both looping to itself; head arrow to x.
- Insert x after p in CDLL:
- x.next = p.next
- x.prev = p
- p.next.prev = x
- p.next = x Diagram: four boxes in a cycle p → succ → …; insert x between p and succ; update four arrows as labeled.
- Delete p from CDLL (assuming non-empty):
- if p.next == p: head = null (singleton case)
- else: p.prev.next = p.next; p.next.prev = p.prev; if head == p: head = p.next
- Clear p.prev = p.next = null Diagram: cycle of 3–5 boxes, remove p, reconnect neighbors, adjust head arrow if needed.
Proof-style reasoning often asked:
- Statement: “Given a direct pointer to a node p in a DLL, deletion takes O(1) time.” Assumptions: memory model with O(1) pointer writes; p is valid and in the list. Derivation: Only constant steps (at most four pointer updates and possibly one head/tail assignment) are executed independent of n; hence time Θ(1).
- Statement: “Searching an unsorted linked list is O(n).” Assumptions: No extra index; comparisons cost O(1). Derivation: In the worst case you must check each node exactly once; that’s n comparisons and up to n−1 pointer traversals; hence Θ(n).
What to draw in exam diagrams:
- DLL: Three nodes in a row, each as a rectangle split into [prev | data | next]; arrows left for prev, right for next; null drawn as a diagonal slash. Head arrow to first, Tail arrow to last. For an insertion, show before-and-after with changed arrows bolded or highlighted in labels.
- CSLL: 4–5 nodes in a circle; each node rectangle split into [data | next]; next arrows form a cycle; head arrow to an arbitrary node in the cycle; no nulls.
- CDLL: 4–5 nodes in a ring; each node rectangle split into [prev | data | next]; draw two directed cycles (clockwise next, counterclockwise prev); head arrow to one node; label tail = head.prev.
Formulas
Programming syntax and patterns to remember (Python-like pseudocode and Python):
class Node: def __init__(self, data): self.data = data; self.prev = None; self.next = NoneNode structure for DLL/CDLL; data is the payload; prev/next are references.# Insert x after p in DLL: x.prev = p; x.next = p.next; if p.next: p.next.prev = x; p.next = xFour-pointer update pattern; O(1) if p is known.# Delete p in DLL: if p.prev: p.prev.next = p.next else: head = p.next; if p.next: p.next.prev = p.prev else: tail = p.prevHandles head and middle/tail cases.# CSLL traversal: cur = head; if cur: do {...; cur = cur.next} while cur != headUse a do–while style loop or a visited-head check to avoid infinite loop.# CDLL empty insert: head = x; x.next = x.prev = xSingleton CDLL invariant.# Time: search unsorted list = O(n); insert/delete with pointer = O(1); traversal = O(n)Complexity summary assuming unit-cost pointer ops.
Worked examples
Example 1 — Python: Doubly linked list build, traverse, delete, and insert Program:
# Doubly Linked List: build from input, traverse forward/backward, delete a key, insert at both ends
import sys
class Node:
def __init__(self, data):
self.data = data
self.prev = None
self.next = None
class DoublyLinkedList:
def __init__(self):
self.head = None
self.tail = None
def insert_back(self, x):
n = Node(x)
if self.head is None:
self.head = self.tail = n
return
n.prev = self.tail
self.tail.next = n
self.tail = n
def insert_front(self, x):
n = Node(x)
if self.head is None:
self.head = self.tail = n
return
n.next = self.head
self.head.prev = n
self.head = n
def delete_key(self, key):
cur = self.head
while cur is not None and cur.data != key:
cur = cur.next
if cur is None:
return False
if cur.prev is not None:
cur.prev.next = cur.next
else:
self.head = cur.next
if cur.next is not None:
cur.next.prev = cur.prev
else:
self.tail = cur.prev
cur.prev = cur.next = None
return True
def forward(self):
out = []
cur = self.head
while cur is not None:
out.append(str(cur.data))
cur = cur.next
return " ".join(out)
def backward(self):
out = []
cur = self.tail
while cur is not None:
out.append(str(cur.data))
cur = cur.prev
return " ".join(out)
# Read input: first token is n, followed by n integers
tokens = sys.stdin.read().split()
if not tokens:
n = 0
arr = []
else:
n = int(tokens[0])
arr = list(map(int, tokens[1:1+n]))
lst = DoublyLinkedList()
for v in arr:
lst.insert_back(v)
print("Forward:", lst.forward())
print("Backward:", lst.backward())
# Operations: delete 30, then insert 5 at front and 60 at back
lst.delete_key(30)
lst.insert_front(5)
lst.insert_back(60)
print("After ops (del 30, push_front 5, push_back 60):")
print("Forward:", lst.forward())
print("Backward:", lst.backward())
Sample input:
5
10 20 30 40 50
Exact output:
Forward: 10 20 30 40 50
Backward: 50 40 30 20 10
After ops (del 30, push_front 5, push_back 60):
Forward: 5 10 20 40 50 60
Backward: 60 50 40 20 10 5
Example 2 — Python: Circular singly linked list and the Josephus elimination order Program:
# Circular Singly Linked List (CSLL) to simulate Josephus problem (n, k)
import sys
class Node:
def __init__(self, data):
self.data = data
self.next = None
def build_csll(n):
if n <= 0:
return None
head = Node(1)
prev = head
for i in range(2, n+1):
cur = Node(i)
prev.next = cur
prev = cur
prev.next = head # make circular
return head, prev # return head and tail (prev)
# Read n and k
parts = sys.stdin.read().split()
if len(parts) >= 2:
n = int(parts[0]); k = int(parts[1])
else:
n = 0; k = 0
if n <= 0 or k <= 0:
print("Elimination order:")
print("Survivor:")
else:
head, tail = build_csll(n)
current = head
prev = tail
elimination = []
# Repeat until one node remains (prev == current)
while current != prev:
# move k-1 steps
for _ in range(k-1):
prev = current
current = current.next
# eliminate current
elimination.append(current.data)
prev.next = current.next
if current == head:
head = current.next
current = prev.next
print("Elimination order:", " ".join(map(str, elimination)))
print("Survivor:", current.data)
Sample input:
5 3
Exact output:
Elimination order: 3 1 5 2
Survivor: 4
Example 3 — Theory: Insert-before and delete operations in a circular doubly linked list (CDLL) Model answer outline:
- Definitions: A CDLL stores for each node x two references prev and next; for a non-empty list the invariants x.prev.next = x and x.next.prev = x hold for all nodes; head.prev = tail and tail.next = head.
- Insert a new node x before a given node p (p is known and in the list): Step 1: Set x.next = p. Step 2: Set x.prev = p.prev. Step 3: Set p.prev.next = x. Step 4: Set p.prev = x. Step 5: If p == head, set head = x. Complexity: All steps are constant-time; total Θ(1).
- Delete a given node p from CDLL: Case A (singleton): If p.next == p (only one node), set head = null; clear p.prev = p.next = null. Case B (general): Set p.prev.next = p.next; set p.next.prev = p.prev; if p == head, set head = p.next; clear p.prev = p.next = null. Complexity: Θ(1).
- Edge-case demonstration (with text-diagram): Suppose list has nodes [10]⇄[20]⇄[30] in a ring with head at 10. Insert 15 before 20. After Step 5, head becomes 15 because p was the old head? No: here p = 20 is not head, so head remains 10. To make head update visible, insert 5 before 10: after steps 1–4, set head = 5.
- Correctness argument sketch: For both operations, after updates the four equalities (x.prev.next = x, x.next.prev = x, head.prev = tail, tail.next = head) remain true because every broken pointer is replaced with one that reconnects the cycle locally; global cycle structure is preserved.
Common mistakes
- Not updating head (and tail or head.prev) when the operation touches the first or last node, causing stale head or a broken circular link.
- Infinite loops on circular lists by writing a while cur: loop instead of stopping when cur returns to head; always check cur == head to terminate.
- Deleting a node in a singly linked list when only a pointer to that node is given (without its predecessor) and assuming it is O(1) in all cases; in fact, without the predecessor, you cannot relink the previous node; a common workaround copies data from next node, but that fails at tail and violates semantics in some contexts.
- Mishandling the singleton case in CDLL: forgetting that head.prev and head.next both refer to head, so delete must set head = null.
- Off-by-one errors in Josephus/round-robin using CSLL: advancing k times instead of k−1 before deletion, which shifts the elimination order.
- Mixing zero-based and one-based positions when inserting by index; define clearly whether position 1 means head.
For your exam
- Short notes: Compare singly vs doubly vs circular lists (time for insert/delete/search, space overhead, use-cases). Include a compact complexity table and at least one real-world example (e.g., LRU cache, playlist).
- Algorithms: Step-by-step insert-after, insert-before, and delete for DLL/CDLL. List pointer updates in order and explicitly handle empty and singleton cases.
- Proof-style/Reasoning: Justify O(1) insert/delete given a pointer; justify O(n) search; argue why circular structure removes null checks but needs a stopping rule.
- Diagrams: Neatly draw nodes as boxes with prev/data/next, arrows for links, and mark head/tail. For circular lists draw a ring; label where an insertion happens; show before-and-after.
- Programs: Implement a DLL or CSLL with insert, delete, and traversal. Full marks typically require: correct handling of empty and singleton lists; no memory leaks/dangling links (in Python: clear references when deleting); correct output formatting; and demonstration of both forward and backward traversal for DLL/CDLL.
- Applications: Explain how CDLL supports a round-robin scheduler or CSLL supports Josephus; outline algorithm and give complexity.
Quick check
- State the invariant that distinguishes a CSLL from a regular singly linked list.
- How many pointer/reference fields per node are there in a CDLL, and what is the worst-case time to search an unsorted CDLL of size n?
- You have a pointer to a node p in a DLL. List the two assignments that must happen to unlink p from its neighbors (ignore head/tail for this question). Answers: (1) In a non-empty CSLL, following next from head eventually returns to head after visiting each node exactly once; there is no null next. (2) Two pointers per node (prev and next); search is O(n) in the worst case. (3) p.prev.next = p.next and p.next.prev = p.prev (plus updating head/tail if needed).
Finished this topic? Mark it so your progress, study plan and readiness keep up.
Stuck on something here?