Linked Lists & the Linked Playlist
Tunebox keeps a playlist in a Python list, and that works fine until someone drags a track into slot 2 of a 5,000-track party mix. To open that slot, Python shifts 4,998 tracks one place to the right. A linked list holds the same tracks as a chain of nodes, each pointing at the next, so splicing a track in means changing two arrows, however long the playlist is.
Why a list shifts on insert
A Python list is an array: its items sit side by side in one block of memory.
That's what makes tracks[4000] instant, because Python can work out where slot
4000 is. It's also why inserting near the front is slow: every item after the gap
has to move, so inserting at position 0 of n items moves all n.
A node: one value, one arrow
A linked list gives up the single block. Each track lives in its own small object, a node, which holds the value and a reference to the next node:
The whole list is just a reference to its first node, the head. No length is stored anywhere, and there is no index. There are only arrows.
Coming from Java/JS:
nextis an ordinary object reference, exactly like aNode next;field in Java or{ val, next }in JS.Noneplays the part ofnull.
Every box in this lesson declares Node again so it runs on its own. The fastest
way to build a chain is to keep putting a new node in front of the head:
class Node:
def __init__(self, val, next=None):
self.val = val
self.next = next
head = None
for title in ["A", "B", "C"]:
head = Node(title, head)
print(head.val)Walking the chain
With no index, the only way through is to follow the arrows. This loop is inside almost every linked-list function, and these two helpers convert between plain lists and chains for the rest of the course:
Walking also means no random access. To reach index i you take i hops, so
reading tracks[4000] goes from O(1) on a list to O(n) on a chain.
class Node:
def __init__(self, val, next=None):
self.val = val
self.next = next
head = Node("A", Node("B", Node("C")))
cur, hops = head, 0
while cur.next:
cur = cur.next
hops += 1
print(cur.val, hops)Splicing in O(1)
This is what you get in return. Once you hold a node, inserting after it or deleting the node after it changes one or two arrows, and nothing shifts:
The order of the two assignments matters. The new node has to take its arrow before the old arrow gets overwritten:
This should splice Bridge in after Intro and print all four tracks. It prints Bridge over and over instead.
❓ Cross-question — "O(1)? You still had to find Intro first." True, and that walk is O(n). The splice is O(1) only when you already hold the node. A player usually does, since it holds the node that's playing, so "play this next" needs no walk. Searching by title costs O(n) to find plus O(1) to splice.
The dummy head
Deleting the first node is awkward. There's no node before it to rewire, so the
head itself has to change, and every function ends up with an extra if. Put a
dummy node in front of the head and every real node has a predecessor:
Reversing in place
Reversing a chain copies nothing. Walk it once and flip each arrow to point
backwards. prev holds the part already reversed, cur is the node being flipped,
and nxt saves the rest before the flip cuts it off. Step through it:
It takes one pass, so O(n) time, and O(1) extra memory. Once the idea is clear, you
can write the loop body as cur.next, prev, cur = prev, cur, cur.next.
Fast and slow pointers
Two walkers moving at different speeds can answer questions a single walk can't.
Move slow one hop and fast two hops per step. When fast runs out of chain,
slow is at the middle.
The same trick finds a loop. If a bug links the last track back into the middle of
the playlist, a plain walk never ends. With two speeds, fast eventually laps slow
and both land on the same node. This is Floyd's cycle detection:
❓ Cross-question — "Why not keep a set of the nodes I've visited?" That works too, but the set costs O(n) memory. Two pointers find the loop in O(n) time with O(1) memory, and that saving is the only reason the trick exists.
What it costs
| operation | Python list | singly linked list |
|---|---|---|
read index i |
O(1) | O(n): walk i hops |
| insert / delete at the front | O(n): everything shifts | O(1) |
| insert / delete after a node you hold | O(n) | O(1) |
| append at the end | O(1) amortized | O(n), or O(1) if you keep a tail |
| find a value | O(n) | O(n) |
| memory per item | one reference | a whole object: value plus next |
Idioms & real-world patterns
- Convert only at the edges. Build the chain from a plain list, work on nodes, and turn it back into a list at the end. That's how every graded function in this course works.
- Pick the loop condition deliberately.
while cur:visits every node,while cur.next:stops on the tail, andwhile fast and fast.next:checks before a double hop. - Use a dummy whenever the head might change.
- Where they live: Python's
dequeis a doubly linked list of small blocks, a Git commit points to its parent, and many hash tables chain their collisions.
❓ Cross-question — "So should Tunebox store titles in one?" Not a plain list of titles: a Python
listis more compact and faster to loop over. Linked lists pay off when you hold node references and splice around them constantly, as an LRU cache does.
⚡ Advanced — doubly linked lists and LRU caches
Give each node a prev arrow as well, and a node can unlink itself in O(1),
without anyone walking to its predecessor first. The cost is one more reference per
node and two arrows to keep in step on every change. Real implementations also put a
stand-in node (a sentinel) at both ends, so prev and next are never None:
That self-unlinking is what an LRU cache is built on. Tunebox keeps recently
played tracks for offline listening and, when the cache is full, evicts the least
recently used one. A dict from title to node finds a track in O(1). A doubly linked
list in recency order moves that node to the fresh end, or drops the stale end, in
O(1). Python ships the pairing as collections.OrderedDict, where move_to_end(key)
and popitem(last=False) are those two moves, and functools.lru_cache uses it to
remember a function's recent results.
🎯 Your turn
Build splice_tracks(tracks, edits), the linked playlist behind Tunebox's playlist
editor. Build a chain from tracks, then apply each edit in order:
["insert", after, title]splicestitlein straight after the first track namedafter. WhenafterisNone, the track goes at the front.["remove", title]unlinks the first track namedtitle.
Skip any edit whose track isn't in the playlist, and return the final playlist as a list:
splice_tracks(["Intro", "Chorus", "Outro"], [["insert", "Intro", "Verse"], ["remove", "Outro"]])→["Intro", "Verse", "Chorus"]splice_tracks(["B", "C"], [["insert", None, "A"]])→["A", "B", "C"]
Hint: put a dummy node in front of the chain. Inserting at the front then becomes inserting after the dummy, and removing the head needs no special case.
Then press ▶ Run, tap the Live App try chips to call it with different inputs, and hit ✓ Check. Green = this piece of the app is built. ✅