Linked Lists: Pointers, Nodes & Trade-offs

An array stores its items in one solid block of memory, side by side. A linked list throws that out: each value lives in its own little box, scattered wherever, and every box holds an arrow pointing to the next one. Follow the arrows and you've got a list. That one design change flips the performance trade-offs completely. Some things get instant, others get slow.

Nodes and the arrows between them

The building block of a linked list is a node. A node holds two things: a value, and a pointer to the next node (often called next). String nodes together by their next pointers and you have a singly linked list, singly because the arrows only go one way.

The first node is the head, your only handle on the whole list. The last node's next points to nothing (None in Python), which is how you know you've reached the end.

To find a value you start at the head and walk the arrows one node at a time. There's no jumping straight to "item number 5." You can only get there by stepping through 0, 1, 2, 3, 4 first. That's the cost. The payoff is on the other side.

Why inserting is cheap

Here's where linked lists shine. To insert a node at the front, you make a new node, point its next at the current head, and call the new node the head. Two pointer updates. Done. Nothing else in the list moves.

Compare that to an array. Insert at the front of an array and every existing element has to shift one slot to the right to make room, and that's O(n) work. A linked list just rewires a couple of arrows.

Watch the operations play out. We start with 1 → 2 → 3, insert 0 at the head, insert 4 at the tail, then delete the node holding 2:

Notice what happened on the delete. To remove 2, the list just points 1's arrow past it, straight at 3. The 2 node is now unreferenced and gets cleaned up. No shifting, no gap to fill. You reroute one arrow and the node is gone. That's the move arrays can't make cheaply.

Build one in Python

There's no built-in linked list in Python (lists are dynamic arrays under the hood), so you build it from a small Node class. Each Node holds a value and a next. If classes are new to you, the Python classes lesson walks through the syntax. Run this. It builds a list, inserts at the head, and traverses to print every value:

The values method is the traversal: start at head, append the value, hop to next, repeat until you hit None. That while current is not None walk is the only way to read a linked list, and it's exactly why getting the n-th item costs O(n).

Array or linked list?

Reach for an array (a Python list) when you mostly read by index, append at the end, and want cache-friendly, compact storage, which is most of the time, honestly. Reach for a linked list when you're constantly inserting and removing at the ends or at known positions and rarely need random access. Stacks and queues are a natural fit, which is why they're often built on linked lists under the hood.

The takeaway

A linked list is nodes joined by next pointers, with the head as your entry point. It trades the array's instant index access for cheap inserts and deletes, rewiring an arrow instead of shifting a block. Knowing which structure fits a problem is half of writing fast code. The other half is knowing what the operations actually cost.

Next: Trees and Binary Trees, where a node can point to more than one other node, and the structure stops being a line and becomes a hierarchy.