Arrays & Linked Lists
In short: a Python list is a dynamic array — one contiguous block
of memory, so values[i] jumps straight there and append is usually
instant. A linked list is a chain of separate Node objects, each
holding a value and a pointer to the next — cheap to splice a node in or out
once you're standing at it, but no jumping to index i: you have to walk
there one link at a time. Python rarely asks you to build a linked list
yourself (list and collections.deque already cover almost every real
case), but the shape shows up constantly in interviews, and understanding it
makes "why is this slow?" answerable. The DSA course covers the Big-O of
both in full; this is the Python-shaped tour.
Prepend a song to a playlist
A playlist app keeps the queue as a plain Python list — values[i] reaches
any track instantly, which is exactly what a dynamic array is built for.
The trouble starts the moment someone taps "play next" on a track that
isn't at the front yet. Pushing it to position 0 feels like it should cost
the same as adding a track at the end, but it doesn't:
values = [2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
values.insert(0, 1)
print(values[5])That's the mistake: treating insert(0, x) as a cheap operation because
values[i] is cheap. They are not the same thing. Indexing jumps straight
to a slot; inserting at the front has to physically move every item after
it one slot over to make room, which gets slower the longer the playlist
gets. append stays cheap no matter how long the list grows, because
nothing after it needs to move — there's nothing after it yet. That
asymmetry (cheap at the end, expensive at the front) is the whole reason
collections.deque exists: it's built to make both ends cheap, which
you'll meet properly in the next lesson.
Walk a browser's back-button history
A browser can't jump to "the 7th page I visited" the way a list jumps to an
index — it only knows "the page before this one." That's a linked list: a
chain of separate Node objects, each holding a value and a pointer to
whatever comes next, with None marking the end of the chain:
There's no history[2] — walking one .next at a time is the only way in.
The mistake people make here is reaching for square brackets out of habit,
because that's how every sequence has worked so far in Python:
TypeErrorRun it and read the error. Then print the third node's value WITHOUT square brackets.
A Node has no __getitem__, so indexing simply isn't defined — Python
raises TypeError rather than guessing. The payoff for giving up indexing:
once you're already standing at a node (say, the "product" page), splicing
a new page in next to it is a couple of pointer rewrites — no shifting
anything else in the whole chain, which is exactly the opposite trade-off
from the playlist above.
Picking between the two
In real Python code, that choice almost always comes down to one question:
do you need to jump to a position by index, or only ever walk forward from
wherever you are? A playlist, a spreadsheet row, anything you address by
position — use a list. A browser's back/forward history, an undo chain,
anything you only ever step through one link at a time and need to splice
mid-walk — a linked chain (or, in practice, collections.deque, which you
meet properly in the next lesson) fits better. Python's own list quietly
covers both jobs reasonably well for small data, which is exactly why this
trade-off only starts to matter once a collection gets large or the
front gets touched constantly.
Quick practice
class Node:
def __init__(self, val, next=None):
self.val = val
self.next = next
a = Node(1)
b = Node(2)
a.next = b
b.next = a
print(a.next.next.val)values = [1, 2, 3, 4, 5]
print(values[2], values[-1])🎯 Your turn
Write round_trip(values). Build a linked list from values using a Node
class, then walk it back into a plain Python list and return that:
round_trip([1, 2, 3])→[1, 2, 3]round_trip([])→[]
Hint — build(values) links each new Node onto a running tail;
to_list(head) walks node = node.next until it hits None, collecting
.val as it goes.
Press ▶ Run, try the Live App chips, then ✓ Check. After that, the practice set below reverses a chain in place — no library, just pointers.