03 Linked Lists

A progressive guide to linked-list structure, traversal, update operations, complexity, and practical trade-offs among singly linked, doubly linked, and circular designs.

Structure and representation

A stores a sequence of elements in separate objects connected by references. Each contains data and link information that identifies another . The links create the logical order even when the nodes are distributed throughout memory.

The identifies the first . In a noncircular list, the final normally has no successor, represented by null or None. An implementation may also keep a and a size counter.

A link identifies or locates another ; it does not duplicate the entire . This indirection allows local insertions and removals without shifting every later element as an array-backed structure may need to do.

Takeaway: Think of a as data-bearing nodes plus links that define the sequence.

Singly linked traversal

In a , every has one successor link, usually called next. Traversal begins at the and repeatedly follows next until the final is reached.

A complete traversal visits each of the $n$ nodes once, so its running time is $O(n)$ . An iterative traversal uses $O(1)$ extra space. Searching for a value and finding an element by index also take $O(n)$ time in the worst case because the list has no direct route to an arbitrary position.

A cannot move directly backward from a : it does not store a predecessor link. This makes it simple and memory-efficient compared with a doubly linked design, but less convenient for reverse traversal and some deletion operations.

Takeaway: Singly linked lists are directional and sequential; following links is efficient only when the required position is already near the current traversal point.

Bidirectional links

A stores both prev and next links in each . The next link supports forward traversal, while prev supports backward traversal.

When a target is already known, inserting before it or removing it requires updating a small, fixed number of neighboring links. These link changes take $O(1)$ time. The implementation must update both directions consistently; omitting one update can make forward and backward traversals disagree.

Doubly linked lists use more memory per than singly linked lists and require more link maintenance. Their advantage is convenient reverse traversal and direct access to a known 's predecessor.

Takeaway: The extra predecessor link buys flexibility at the cost of additional memory and update work.

Insertion, deletion, and locating nodes

Insertion and deletion are best understood as two separate costs: locating the relevant position and changing the links once that position is known.

At the front of a , insertion takes $O(1)$ time when the new first points to the current and the is then replaced by the new . Reversing those updates can make the original list unreachable.

Appending with only a reference requires finding the final , so it takes $O(n)$ time. With a maintained , appending can take $O(1)$ time, including appropriate handling of the empty-list case.

Inserting after a known or removing the after a known predecessor changes only local links and takes $O(1)$ time. If the or predecessor must first be found by value or index, the complete operation may take $O(n)$ .

Takeaway: A local link update can be constant-time even when finding the place to perform it is linear-time.

Circular organization and traversal

A connects its final back to its first instead of using a null successor. In a circular , the tail's next link is the . In a circular , the 's prev link is the tail and the tail's next link is the .

Circular structures are useful when processing repeats continuously, such as round-robin scheduling. Traversal must stop when the current returns to the starting ; waiting for null would never terminate on a nonempty circular list.

The empty and one- cases need explicit treatment. An empty circular list has no nodes, while a one- circular list has a whose successor refers to itself.

Takeaway: Circularity changes the stopping condition and makes careful empty-list and one- handling essential.

Complexity and design choices

Linked lists provide useful local updates but have important performance trade-offs. Traversal, searching, and indexed access are generally $O(n)$ . Inserting at the is $O(1)$ , and insertion or deletion near a known can also be $O(1)$ . A usually needs $O(n)$ time to delete its tail because it must find the predecessor, whereas a with a can delete its tail in $O(1)$ time.

Linked-list nodes require extra storage for links, and many separate allocations may be slower than allocating one contiguous array. Nodes scattered through memory can also reduce cache locality. These practical costs mean that an $O(1)$ linked-list operation is not automatically faster than an array operation.

Choose a when frequent insertions or deletions occur near known nodes, sequential traversal is more important than indexing, or the structure naturally behaves as a queue, deque, or circular process. Prefer an array-backed list when indexed access, traversal speed, cache locality, or low memory overhead is more important.

Takeaway: Choose the representation for the complete workload, not for one isolated Big-O bound.