Linked Lists

The last lesson ended on a puzzle: how can a queue remove from its front in O(1) when deleting from the front of an array shifts every other element? The answer is to stop storing elements in one solid block at all. An array keeps its elements in a single contiguous run of memory, so element k lives at a known offset — instant access, yes, but inserting in the middle means shifting everything after it. A linked list makes the opposite bargain: it scatters elements anywhere in memory and chains them with pointers (a pointer is just a stored reference to where the next node lives). Splicing a node in or out is trivial; reaching the k-th element means walking the chain from the start. This same trade-off decides everyday design choices — an LRU cache, for instance, keeps its entries in a linked list precisely so it can move a “just-used” item to the front in O(1).

Nodes and pointers

A linked list is a sequence of nodes. Each node holds a value and a pointer to the next node; the last node points to nothing (null). A separate head reference marks the start. In a singly linked list each node points only forward; in a doubly linked list each node also stores a prev pointer, so you can walk backward and delete a node knowing only that node.

The cost trade-off

Because there is no index, access and search are O(n) — to reach the k-th node you must follow k pointers from the head. But once you are at a node, insert and delete are O(1): you just relink a couple of pointers, with no shifting of other elements. That is the exact reverse of an array, which indexes in O(1) but pays O(n) to insert or delete in the middle (everything after must shift). This is also the answer to last lesson’s puzzle — a queue built on a linked list dequeues from the front by moving one pointer, never shifting a thing.

Pick the operation you do most. Drive each one and watch what the two structures actually have to do:

One caveat the diagram hides: the O(1) insert/delete assumes you already hold the relevant node. If you must first find the position by value or index, that search is O(n) — the splice itself is still O(1), but getting there is not free.

How GATE asks this

Usually an MCQ or MSQ: it states an operation (traverse, insert after a node, delete a node) and asks for the cost, or it lists array-vs-linked-list claims and asks which are true. The reliable approach is to ask two questions — do I already have the node, or must I search for it? and am I accessing by position or relinking? — then read the cost straight off the table above.

Worked example — relinking is O(1), finding is O(n)

Start with the singly linked list A -> B -> C and a head pointing at A.

Insert a node X after the head. Two pointer writes: point X.next at whatever the head pointed to (B), then point head.next at X. No other node moves.

before:  head -> A -> B -> C
step 1:  X.next = head.next        (X now points to B)
step 2:  head.next = X             (A now points to X)
after:   head -> A -> X -> B -> C   (2 pointer updates, O(1))

Delete node B. Given the node before it (here A), one pointer write: re-point A.next to B.next (which is C). B is now unreachable and the chain is intact.

before:  A -> B -> C
step 1:  A.next = B.next           (A now points to C)
after:   A -> C                    (1 pointer update, O(1))

Both edits are O(1) once you hold the right node. Contrast finding the 4th element: with no index you must follow pointers head -> 1st -> 2nd -> 3rd -> 4th, an O(n) traversal. The relink is cheap; the navigation is what costs.

A question to carry forward

Look back at the cost table and one row refuses to improve: search by value is O(n) for both the array and the linked list. Whether elements sit in a solid block or a chain of pointers, finding a particular value means scanning until you stumble on it. That feels almost inevitable — until you ask a stranger question. What if, instead of searching for where a value lives, you could compute its location directly from the value itself, and jump straight there? Here is the thread onward: is there a structure that turns “look up this key” into roughly a single step — O(1) on average — and what trick makes that possible?

In one breath

• A linked list = nodes (value + next pointer) chained in memory; a head marks the start, the last node points to null.
• Singly = forward pointers only; doubly = also a prev pointer (more memory, but backward walk + delete a node knowing only itself).
• Cost: O(1) insert/delete at a known node (just relink), but O(n) access/search (no index — traverse from the head). The mirror of an array (O(1) index, O(n) middle splice).
• Worked: insert-after-head = 2 pointer writes, delete-given-predecessor = 1; both O(1).
• Choose by the dominant operation — and note both array and list search by value in O(n).

Practice