Singly Linked List

A singly linked list is built from nodes shaped like {val, next}. The val stores the payload, and next points to the following node or null at the end. The entire structure is reached through a head pointer, so losing head means losing access to the list.

Think of the list as head -> 1 -> 2 -> 3 -> null. The arrows are not positions inside one block of memory. They are references from one object to another, which means traversal follows links instead of doing address arithmetic.

A singly linked list has no random access. To reach the third real node in 1 -> 2 -> 3 -> null, you must start at head, follow next to 2, then follow next again to 3. Access by position is therefore O(n), not O(1).

This is the most important contrast with arrays. An array can jump to arr[i] because indices map to addresses. A linked list can only move from the current node to the next node it references. That makes sequential scans natural and repeated index lookups expensive.

The reward for giving up random access is cheap pointer rewiring. If you already have the previous node, inserting after it is O(1): point the new node at the old successor, then point the previous node at the new node. Deleting after a previous node is also O(1): skip the removed node by assigning prev.next to prev.next.next.

The phrase given the node or previous node matters. Finding that location may still cost O(n). Interviews often test whether you separate the traversal cost from the local mutation cost.

Arrays are strong when you need random access, binary search over sorted data, compact memory, and cache-friendly scans. Linked lists are strong when the algorithm already holds the node to change and needs many local insertions or deletions without shifting a suffix of elements.

In practice, linked lists are less common than arrays for raw storage because pointer chasing has overhead. Interviewers reach for them because they reveal whether you can reason about object identity, aliasing, null, and pointer update order without losing part of the structure.