Learn
B4.1.3 | CONSTRUCT AND APPLY LINKED LISTS (HL ONLY)
01 | FROM A SKETCH TO A WORKING STRUCTURE
In the previous lesson, you evaluated linked representations. Now you will build them. Each implementation must keep a usable entry point, connect new nodes safely and repair the chain when a node is removed. A diagram is a useful plan, but the code also has to handle the empty list and the final remaining node.
We will construct a singly linked linear list, a doubly linked linear list and a singly linked circular list. Each supports insertion, deletion, traversal and search. The circular implementation also provides rotation for a turn-taking application.
Use small integer values while learning the mechanics. A node’s identity is separate from its stored value, so repeated values are permitted.
02 | AGREE THE OPERATION RULES FIRST
| Operation | Contract in this lesson |
|---|---|
| append(value) | Add a new node at the end |
| prepend(value) | Add a new node at the beginning |
| find(value) | Return the first matching node from head, or None |
| insert_after(target, value) | Insert after the first matching target; return True, or False without mutation if absent |
| delete_first(value) | Remove the first matching node; return True, or False without mutation if absent |
| values() | Return the current forward sequence as a separate Python list |
| size | Number of nodes currently in the list |
The methods append and prepend have no useful returned result. The first-match rule makes duplicate handling predictable. find returns a live node reference for learning; do not modify its links from caller code unless an operation explicitly supports that. A production API might expose fewer internal handles.
The examples are single-threaded. Every complete method must restore the list invariants before returning, even though its individual link assignments can temporarily leave an update unfinished.
03 | UNDERSTAND THE REFERENCE FIELDS
A singly linked node has value and next. A doubly linked node also has prev. A list object stores metadata such as head, tail and size. None represents an absent node reference in Python; Java uses null.
self.head is the entry point belonging to the list instance. current is usually a local traversal reference. Changing current does not move head. Changing current.next changes the link on the node that current reaches.
Before assigning a link, identify its owner and its destination. For example, previous.next = current.next changes the predecessor’s next field to the successor reference. It does not copy the successor’s data into previous.
04 | SINGLY LINKED: INITIALIZATION AND APPEND
# Inside SinglyList:
def append(self, value):
node = SNode(value)
if self.tail is None:
self.head = node
else:
self.tail.next = node
self.tail = node
self.size += 1
Initialize head and tail to None and size to zero. For the first append, the new node becomes both head and tail. For later appends, connect the old tail to the new node before replacing tail.
Because this implementation maintains a tail reference, append does not search from head. Its link work is O(1). Every linear tail must finish with next = None.
05 | PREPEND WITHOUT LOSING THE OLD HEAD
# Inside SinglyList:
def prepend(self, value):
node = SNode(value, self.head)
self.head = node
if self.tail is None:
self.tail = node
self.size += 1
The node constructor records the old head as the new node’s successor. Then head is redirected. If the list was empty, tail must also identify the same new node. If it was non-empty, tail stays where it was.
Do not create a shared mutable node or list as a class-level default for every instance. Each list needs its own metadata and each inserted item needs its own node object.
06 | TRAVERSE AND SEARCH WITH A LOCAL REFERENCE
# Inside SinglyList:
def find(self, value):
current = self.head
while current is not None:
if current.value == value:
return current
current = current.next
return None
The while condition checks whether current refers to a node before reading current.value. A match returns immediately. Only return None after the entire reachable chain has been checked; placing that return inside the non-matching branch would stop after the first node.
values follows the same progression but records every value. An absent search can take O(n) comparisons. Returning a node lets code distinguish a match from None even when a permitted stored value itself is None.
07 | INSERT AFTER THE FIRST MATCH
| Step | Reference effect |
|---|---|
| previous = find(target) | Locate the first matching predecessor |
| node = SNode(value, previous.next) | Preserve its old successor in the new node |
| previous.next = node | Connect the predecessor to the new node |
| If previous was tail, set tail = node | Keep final-node metadata correct |
| Increment size | Count the newly inserted node |
For 10, 20, 30, insert_after(10, 15) produces 10, 15, 20, 30. If target is absent, return False before creating a linked node or changing metadata.
The splice uses a fixed number of assignments after locating the target. This public method includes find, so its worst-case cost is O(n), not O(1).
08 | DELETE WITH CURRENT AND PREVIOUS
Start previous = None and current = head. Move both references together until the first matching node is reached. If previous is None at the match, current is the head, so set head = current.next. Otherwise bypass current through previous.next.
| Case | Required update |
|---|---|
| Delete head of several nodes | head = current.next |
| Delete internal node | previous.next = current.next |
| Delete tail | Also tail = previous |
| Delete the only node | Both head and tail become None |
| Target absent | Return False with no state change |
After reconnecting the live chain, set current.next = None to detach the removed node’s old outgoing route, decrement size once and return True. Detachment does not destroy an object that another reference still reaches.
09 | COMPLETE PYTHON SINGLY LINKED LIST
Save this as singly_list.py or place it in a combined practice file. SNode is the node type used only by this implementation. You can run the shared caller in section 21 after defining all three list classes.
class SNode:
def __init__(self, value, next_node=None):
self.value = value
self.next = next_node
class SinglyList:
def __init__(self):
self.head = None
self.tail = None
self.size = 0
def append(self, value):
node = SNode(value)
if self.tail is None:
self.head = node
else:
self.tail.next = node
self.tail = node
self.size += 1
def prepend(self, value):
node = SNode(value, self.head)
self.head = node
if self.tail is None:
self.tail = node
self.size += 1
def find(self, value):
current = self.head
while current is not None:
if current.value == value:
return current
current = current.next
return None
def insert_after(self, target, value):
previous = self.find(target)
if previous is None:
return False
node = SNode(value, previous.next)
previous.next = node
if previous is self.tail:
self.tail = node
self.size += 1
return True
def delete_first(self, value):
previous = None
current = self.head
while current is not None:
if current.value == value:
if previous is None:
self.head = current.next
else:
previous.next = current.next
if current is self.tail:
self.tail = previous
current.next = None
self.size -= 1
return True
previous = current
current = current.next
return False
def values(self):
result = []
current = self.head
while current is not None:
result.append(current.value)
current = current.next
return result
Read delete_first with empty, head, tail and singleton sketches beside you. The same comparison current is self.tail checks identity rather than equal values. This matters when two different nodes store the same value.
10 | DOUBLY LINKED: MAINTAIN TWO DIRECTIONS
DNode adds prev. Our linear invariants require head.prev = None, tail.next = None and agreement between adjacent forward and backward references. Empty state means both endpoints are None and size is zero.
Forward traversal starts at head and follows next. Reverse traversal starts at tail and follows prev. You do not reverse the values or reconstruct the list to move backwards; the extra links already provide that route.
11 | APPEND AND PREPEND A DOUBLY LINKED NODE
| Append | Prepend |
|---|---|
| Set node.prev to old tail | Set node.next to old head |
| If non-empty, old tail.next = node | If non-empty, old head.prev = node |
| If empty, head = node | If empty, tail = node |
| Set tail = node | Set head = node |
| Increment size | Increment size |
A new DNode starts with both links equal to None. This makes the missing outer neighbour correct when adding at an endpoint. The old endpoint, when present, must point back towards the new node.
A frequent bug is a list that traverses forwards correctly but backwards incorrectly. Test both directions after every kind of insertion.
12 | INSERT IN BOTH DIRECTIONS
# After previous is found, inside DoublyList.insert_after:
node = DNode(value)
node.prev = previous
node.next = previous.next
if previous.next is None:
self.tail = node
else:
previous.next.prev = node
previous.next = node
self.size += 1
The new node first remembers both neighbours. If an old successor exists, redirect its prev towards the new node. Then redirect the predecessor’s next. If there was no successor, the new node becomes tail instead.
These are implementation steps inside one operation. Do not call a general traversal halfway through a splice and assume the entire public contract has already been restored.
13 | DELETE THROUGH THE NEIGHBOURS
Once the matching DNode is found, its prev and next references identify both neighbours. If prev is missing, update head; otherwise reconnect prev.next. If next is missing, update tail; otherwise reconnect next.prev.
| Remove B between A and C | Reason |
|---|---|
| A.next = C | Forward traversal bypasses B |
| C.prev = A | Backward traversal bypasses B |
| B.prev = None and B.next = None | Detach the removed node’s old routes |
| Decrease size by one | Keep metadata consistent |
The endpoint branches also handle the only-node case: head and tail both become None. The unlinking is constant-size after finding the node. Searching by value remains O(n) worst case.
14 | COMPLETE PYTHON DOUBLY LINKED LIST
class DNode:
def __init__(self, value):
self.value = value
self.prev = None
self.next = None
class DoublyList:
def __init__(self):
self.head = None
self.tail = None
self.size = 0
def append(self, value):
node = DNode(value)
node.prev = self.tail
if self.tail is None:
self.head = node
else:
self.tail.next = node
self.tail = node
self.size += 1
def prepend(self, value):
node = DNode(value)
node.next = self.head
if self.head is None:
self.tail = node
else:
self.head.prev = node
self.head = node
self.size += 1
def find(self, value):
current = self.head
while current is not None:
if current.value == value:
return current
current = current.next
return None
def insert_after(self, target, value):
previous = self.find(target)
if previous is None:
return False
node = DNode(value)
node.prev = previous
node.next = previous.next
if previous.next is None:
self.tail = node
else:
previous.next.prev = node
previous.next = node
self.size += 1
return True
def delete_first(self, value):
current = self.find(value)
if current is None:
return False
if current.prev is None:
self.head = current.next
else:
current.prev.next = current.next
if current.next is None:
self.tail = current.prev
else:
current.next.prev = current.prev
current.prev = None
current.next = None
self.size -= 1
return True
def values(self):
result = []
current = self.head
while current is not None:
result.append(current.value)
current = current.next
return result
def reverse_values(self):
result = []
current = self.tail
while current is not None:
result.append(current.value)
current = current.prev
return result
reverse_values is a deliberate structural test as well as a useful operation. After complete methods, its result should equal the reversed forward values. If it does not, one of the prev routes or the tail is probably wrong.
Use fresh list objects while comparing examples. A shared node attached to two independently maintained lists can break their ownership and link assumptions.
15 | CIRCULAR: STORE TAIL AND DERIVE HEAD
# Inside CircularList:
@property
def head(self):
return None if self.tail is None else self.tail.next
This representation stores tail and size. A read-only head property derives the starting node as tail.next. It avoids maintaining a second independent head field that could disagree with the circular closure.
An empty circle has tail = None and size = 0. A one-node circle has tail.next is tail. For every non-empty circle, following exactly size next links from head returns to the same head object.
16 | CIRCULAR APPEND VERSUS PREPEND
| Stage | Append | Prepend |
|---|---|---|
| Empty list | New node points to itself; tail becomes it | The same singleton setup |
| Non-empty: preserve old head | node.next = tail.next | node.next = tail.next |
| Connect old tail to new node | tail.next = node | tail.next = node |
| Choose logical last node | Move tail to node | Keep tail at the old last node |
| Count the addition | Increment size | Increment size |
Both operations splice a node between tail and head, but only append moves the tail marker. That one metadata difference determines which value is first in the resulting logical sequence.
For 10, 20, 30, appending 40 yields 10, 20, 30, 40. Prepending 5 yields 5, 10, 20, 30. Draw tail.next after each assignment rather than assuming a circular list has an absent end link.
17 | BOUNDED TRAVERSAL AND SEARCH
# Inside CircularList:
def find(self, value):
current = self.head
for _ in range(self.size):
if current.value == value:
return current
current = current.next
return None
The underscore is a conventional name for an unused loop counter. range(size) causes exactly size visits at most, so a valid circle cannot loop forever. On an empty list, the body executes zero times and never dereferences None.
This relies on size being correct. An alternative is to stop on returning to the starting node identity after processing it once. Neither approach should stop merely because the same data value appears again.
18 | CIRCULAR DELETION: HEAD, TAIL AND ONLY NODE
For a circular singly linked search, start previous = tail and current = head. The tail is the predecessor of the head, so the first candidate already has the route needed for bypassing. Keep both references moving for at most size visits.
| Matching case | Update |
|---|---|
| More than one node | previous.next = current.next |
| The removed node is tail | Also tail = previous |
| The removed node is head | The updated tail.next now provides the new head |
| Only one node remains | Set tail = None |
| After successful removal | Detach current.next, decrement size, return True |
Do the singleton check before applying the general bypass rule. Otherwise you can leave a tail pointing at the supposedly removed self-linked node. The method returns immediately after removal, so its precomputed loop bound does not cause extra visits.
19 | COMPLETE PYTHON CIRCULAR LIST
class CNode:
def __init__(self, value):
self.value = value
self.next = None
class CircularList:
def __init__(self):
self.tail = None
self.size = 0
@property
def head(self):
return None if self.tail is None else self.tail.next
def append(self, value):
node = CNode(value)
if self.tail is None:
node.next = node
else:
node.next = self.tail.next
self.tail.next = node
self.tail = node
self.size += 1
def prepend(self, value):
node = CNode(value)
if self.tail is None:
node.next = node
self.tail = node
else:
node.next = self.tail.next
self.tail.next = node
self.size += 1
def find(self, value):
current = self.head
for _ in range(self.size):
if current.value == value:
return current
current = current.next
return None
def insert_after(self, target, value):
previous = self.find(target)
if previous is None:
return False
node = CNode(value)
node.next = previous.next
previous.next = node
if previous is self.tail:
self.tail = node
self.size += 1
return True
def delete_first(self, value):
previous = self.tail
current = self.head
for _ in range(self.size):
if current.value == value:
if self.size == 1:
self.tail = None
else:
previous.next = current.next
if current is self.tail:
self.tail = previous
current.next = None
self.size -= 1
return True
previous = current
current = current.next
return False
def values(self):
result = []
current = self.head
for _ in range(self.size):
result.append(current.value)
current = current.next
return result
def rotate(self):
if self.tail is not None:
self.tail = self.tail.next
rotate moves the logical start one place by advancing tail to its successor. The node links themselves do not change: the same ring is viewed from a new starting point. Rotation of an empty or one-node circle leaves the visible sequence unchanged.
This is a singly linked circle. A doubly linked circular version would also maintain prev, including reciprocal links at the closure. The three implementations here make the specified singly, doubly and circular construction choices explicit.
20 | STEP THROUGH ALL THREE IMPLEMENTATIONS
Choose a representation. Each scenario starts empty and performs the same core operations, then tests missing targets, deletion down to empty and reuse. The circular scenario also rotates. The diagrams and link tables come from executing the actual Python methods shown above.
The table keeps references to removed nodes for teaching, so a detached row is not a claim that the object has already been reclaimed. It also shows exactly where head and tail point after each complete operation.
21 | ONE CALLER, THREE IMPLEMENTATIONS
Place the three Python definitions in one file, then add the following caller. Click Run in your editor. Each class has the same basic method names and first-match contract, so exercise works with all three.
def exercise(ListClass):
items = ListClass()
for value in (10, 20, 30):
items.append(value)
items.prepend(5)
print(items.insert_after(10, 15))
print(items.values())
print(items.find(20) is not None)
print(items.delete_first(20))
print(items.values(), items.size)
print(items.delete_first(99))
for ListClass in (SinglyList, DoublyList, CircularList):
exercise(ListClass)
circle = CircularList()
for value in (10, 20, 30):
circle.append(value)
circle.rotate()
print(circle.values())
For each implementation, the results are True; [5, 10, 15, 20, 30]; True; True; [5, 10, 15, 30] 4; False. The final circular rotation prints [20, 30, 10]. Each semicolon here separates an output line.
The caller does not edit a link field. It requests operations, then inspects returned values and snapshots. This carries the ADT boundary from B4.1.1 into working code.
22 | COMPLETE JAVA IMPLEMENTATIONS
Save this as LinkedListsExample.java. It contains all three integer implementations and a common IntChain interface. Only LinkedListsExample is public. Use main to run the same application sequence for each representation.
import java.util.ArrayList;
import java.util.List;
interface IntChain {
void append(int value);
void prepend(int value);
boolean insertAfter(int target, int value);
boolean deleteFirst(int value);
boolean contains(int value);
List<Integer> values();
}
class SNode {
int value;
SNode next;
SNode(int value) { this.value = value; }
}
class SinglyList implements IntChain {
private SNode head, tail;
private int size;
public void append(int value) {
SNode n = new SNode(value);
if (tail == null) head = n;
else tail.next = n;
tail = n;
size++;
}
public void prepend(int value) {
SNode n = new SNode(value);
n.next = head;
head = n;
if (tail == null) tail = n;
size++;
}
private SNode find(int value) {
for (SNode n = head; n != null; n = n.next) {
if (n.value == value) return n;
}
return null;
}
public boolean contains(int value) { return find(value) != null; }
public boolean insertAfter(int target, int value) {
SNode p = find(target);
if (p == null) return false;
SNode n = new SNode(value);
n.next = p.next;
p.next = n;
if (p == tail) tail = n;
size++;
return true;
}
public boolean deleteFirst(int value) {
SNode p = null, n = head;
while (n != null) {
if (n.value == value) {
if (p == null) head = n.next;
else p.next = n.next;
if (n == tail) tail = p;
n.next = null;
size--;
return true;
}
p = n;
n = n.next;
}
return false;
}
public List<Integer> values() {
List<Integer> result = new ArrayList<>();
for (SNode n = head; n != null; n = n.next) result.add(n.value);
return result;
}
}
class DNode {
int value;
DNode prev, next;
DNode(int value) { this.value = value; }
}
class DoublyList implements IntChain {
private DNode head, tail;
private int size;
public void append(int value) {
DNode n = new DNode(value);
n.prev = tail;
if (tail == null) head = n;
else tail.next = n;
tail = n;
size++;
}
public void prepend(int value) {
DNode n = new DNode(value);
n.next = head;
if (head == null) tail = n;
else head.prev = n;
head = n;
size++;
}
private DNode find(int value) {
for (DNode n = head; n != null; n = n.next) {
if (n.value == value) return n;
}
return null;
}
public boolean contains(int value) { return find(value) != null; }
public boolean insertAfter(int target, int value) {
DNode p = find(target);
if (p == null) return false;
DNode n = new DNode(value);
n.prev = p;
n.next = p.next;
if (p.next == null) tail = n;
else p.next.prev = n;
p.next = n;
size++;
return true;
}
public boolean deleteFirst(int value) {
DNode n = find(value);
if (n == null) return false;
if (n.prev == null) head = n.next;
else n.prev.next = n.next;
if (n.next == null) tail = n.prev;
else n.next.prev = n.prev;
n.prev = null;
n.next = null;
size--;
return true;
}
public List<Integer> values() {
List<Integer> result = new ArrayList<>();
for (DNode n = head; n != null; n = n.next) result.add(n.value);
return result;
}
public List<Integer> reverseValues() {
List<Integer> result = new ArrayList<>();
for (DNode n = tail; n != null; n = n.prev) result.add(n.value);
return result;
}
}
class CNode {
int value;
CNode next;
CNode(int value) { this.value = value; }
}
class CircularList implements IntChain {
private CNode tail;
private int size;
private CNode head() { return tail == null ? null : tail.next; }
public void append(int value) {
CNode n = new CNode(value);
if (tail == null) n.next = n;
else {
n.next = tail.next;
tail.next = n;
}
tail = n;
size++;
}
public void prepend(int value) {
CNode n = new CNode(value);
if (tail == null) {
n.next = n;
tail = n;
} else {
n.next = tail.next;
tail.next = n;
}
size++;
}
private CNode find(int value) {
CNode n = head();
for (int i = 0; i < size; i++) {
if (n.value == value) return n;
n = n.next;
}
return null;
}
public boolean contains(int value) { return find(value) != null; }
public boolean insertAfter(int target, int value) {
CNode p = find(target);
if (p == null) return false;
CNode n = new CNode(value);
n.next = p.next;
p.next = n;
if (p == tail) tail = n;
size++;
return true;
}
public boolean deleteFirst(int value) {
CNode p = tail, n = head();
for (int i = 0; i < size; i++) {
if (n.value == value) {
if (size == 1) tail = null;
else {
p.next = n.next;
if (n == tail) tail = p;
}
n.next = null;
size--;
return true;
}
p = n;
n = n.next;
}
return false;
}
public List<Integer> values() {
List<Integer> result = new ArrayList<>();
CNode n = head();
for (int i = 0; i < size; i++) {
result.add(n.value);
n = n.next;
}
return result;
}
public void rotate() { if (tail != null) tail = tail.next; }
}
public class LinkedListsExample {
public static void exercise(IntChain items) {
items.append(10);
items.append(20);
items.append(30);
items.prepend(5);
System.out.println(items.insertAfter(10, 15));
System.out.println(items.values());
System.out.println(items.contains(20));
System.out.println(items.deleteFirst(20));
System.out.println(items.values());
System.out.println(items.deleteFirst(99));
}
public static void main(String[] args) {
exercise(new SinglyList());
exercise(new DoublyList());
exercise(new CircularList());
CircularList turns = new CircularList();
turns.append(10);
turns.append(20);
turns.append(30);
turns.rotate();
System.out.println(turns.values());
}
}
Each implementation prints true; [5, 10, 15, 20, 30]; true; true; [5, 10, 15, 30]; false. The final rotation prints [20, 30, 10]. Python also prints size in its shared caller; this compact Java caller prints the values only.
Java uses private metadata and contains rather than returning an internal node to callers. The underlying find methods remain internal. These interface differences are intentional; the shared insertion, first-match deletion and sequence behaviours are the same.
23 | APPLY A CIRCULAR LIST TO TURNS
turns = CircularList()
for player in ("Maya", "Leo", "Sam"):
turns.append(player)
print(turns.head.value)
turns.rotate()
print(turns.head.value)
turns.delete_first("Leo")
print(turns.values())
# Maya
# Leo
# ['Sam', 'Maya']
After rotating, Leo is the head, so the logical order is Leo, Sam, Maya. Removing Leo reconnects the last node to Sam. Maya is still the tail, and its next supplies the new head Sam.
For a real game, decide whether a removed current player’s successor acts next and how to handle no players. That application policy should be clear before the code chooses rotation and deletion order.
24 | COSTS OF THESE EXACT METHODS
| Operation | SinglyList | DoublyList | CircularList |
|---|---|---|---|
| append / prepend | O(1) | O(1) | O(1) |
| find by value | O(n) | O(n) | O(n) |
| insert_after by target value | O(n) | O(n) | O(n) |
| delete_first by value | O(n) | O(n) | O(n) |
| values snapshot | O(n) time and output space | O(n) time and output space | O(n) time and output space |
| Extra navigation | Forward only | Forward and reverse | Forward with wraparound |
The search is included in these public operations. If a separate API accepted an already-known valid doubly linked node, unlinking could be O(1). This lesson deliberately uses first-match value methods to keep caller behaviour consistent.
Each structure has O(n) total storage, with different link overhead and practical allocation costs. A maintained tail gives singly linked append constant link work but does not remove the predecessor-search cost for tail deletion.
25 | TEST STRUCTURE AS WELL AS OUTPUT
For every class, test append and prepend on empty and non-empty lists, insertion after head and tail, and deletion of head, middle, tail and the only node. Include duplicate values and absent targets. A failed request must preserve size and sequence.
For singly linked lists, head and tail must both be None exactly when empty, and tail.next must be None when non-empty. For doubly linked lists, also check head.prev and each reciprocal neighbour route; reverse_values should match reversed forward values.
For circular lists, size zero implies no tail. Otherwise exactly size next steps from head must visit distinct node identities and return to head, and the final visited node must be tail. Repeated values are allowed, so compare node identity for this structural test.
26 | BUILD, TRACE, THEN EXPLAIN
Your challenge is a small playlist tool supporting add-last, add-first, insert-after-first-match, remove-first-match and show-all. Implement it using two of the representations, keep the same user-facing contract and use the same tests on both.
Explain each update in terms of the old neighbour, the preserved successor and the new route. If a method fails, draw the smallest failing state first. A singleton or endpoint often exposes the missing branch faster than a large random example.
The next lesson introduces binary search trees, where nodes can have left and right children instead of a single sequence successor. Carry forward the habit of defining the invariant before changing references.