Linked Lists

The array's whole personality came from one decision: keep every element adjacent in memory. The linked list makes the opposite decision and gets the opposite personality. Each element lives in its own little parcel of memory called a node, holding two things: the value, and a pointer, the address of the next node. The list is just the address of the first node, the head; everything else is reachable only by following pointers, link by link, like a treasure hunt where every clue names the location of the next.

The array was a welded row of numbered lockers. The linked list is a scavenger hunt: each note tells you where the next note is hidden, and the notes can be scattered anywhere in the city. Finding the tenth note means visiting the nine before it, there is no shortcut, because note ten's location is written only on note nine. But inserting a new note between two others is wonderfully cheap if you are already standing at the right spot: write the new note pointing where the old note pointed, then change one line on the old note. Nobody else in the whole hunt has to move.

The inverted price list

Because nodes are scattered, there is no address arithmetic: reaching position i means walking i links from the head, O(n) access, and searching is likewise a walk, O(n). What the structure buys with that sacrifice is splicing. To insert after a node you already hold a pointer to: create the new node, aim it at the current successor, aim the held node at the newcomer. Two pointer writes, O(1), regardless of list length, and no other node moves. Deletion at a known node is the same surgery in reverse. Where the array shifted everything to preserve contiguity, the list rewires two arrows, and this is its entire reason to exist, as laid out in the SLList and DLList chapters of Open Data Structures.

Singly versus doubly linked

A singly linked list points only forward, so it can be walked only forward, and one operation exposes the weakness: deleting the last node. Deletion requires rewiring the predecessor, and in a singly linked list the only way to find the predecessor is to walk from the head, O(n) even with a tail pointer telling you where the last node is. The doubly linked list fixes this by giving every node a second pointer, to its predecessor. Now every neighbor is reachable from every node, deletion anywhere you stand is O(1), and the list can be walked in both directions. The price is one extra pointer of memory per node and slightly more bookkeeping per operation.

• Access by index or search: O(n) in both variants, walking is walking.
• Insert or delete at the head: O(1) in both.
• Insert at the tail: O(1) in both, given a tail pointer.
• Delete at the tail: O(n) singly, the predecessor must be found by walking; O(1) doubly, the predecessor is one link back.
• Insert or delete at a node you already hold: O(1) in both, after whatever it cost to get there.

That last row hides the trap that catches most first-time users: the phrase after whatever it cost to get there. The O(1) splice is real only when an algorithm naturally holds node references as it works, an iterator moving through the list, a cache evicting the node it just touched, a queue holding its own tail. Code that addresses a linked list by numeric index pays the O(n) walk before every cheap splice and ends up slower than an array at everything. The challenge below measures exactly this mistake.

The honest tradeoff

On the asymptotic scoreboard, linked lists win any workload dominated by splicing at held positions and lose any workload dominated by indexing. But the practical scoreboard adds a thumb on the scale that the big-O table cannot see: memory layout. Array elements are adjacent, so scanning one streams beautifully through CPU caches; list nodes are scattered, so every hop is a potential cache miss, and each node carries pointer overhead on top of its value. The result, measured on real machines, is that dynamic arrays beat linked lists even at some workloads the asymptotics say they should lose. The fair summary: reach for a linked list when the algorithm genuinely holds node references and splices constantly, and default to the dynamic array otherwise. Knowing when a structure loses is as important as knowing when it wins.

Pointers, chains, and shipped code

The linked list is your first pointer-built structure, and the mental muscle it trains, objects referencing objects by address, is the foundation for trees and graphs in the coming lessons, which are the same idea with more pointers per node. That muscle also has a protection payoff: in memory dumps and decompiled output, analysts recognize structures by their pointer patterns, a chain of same-shaped nodes each referencing one successor reads as a list even with every name stripped. And free lists, the allocator structures that manage a program's heap memory, are linked lists doing invisible infrastructure work in nearly every runtime this Academy covers.

A linked list scatters nodes anywhere in memory and connects them with pointers: access and search fall to O(n), but insertion and deletion at a node you hold become two pointer writes, O(1). Doubly linked variants add backward pointers to make deletion cheap everywhere. The O(1) splice counts only when the algorithm already holds the node, and cache behavior keeps arrays competitive in practice.

Frequently asked questions