4 Linked Lists

How linked lists are organized

A linked list stores an ordered sequence as connected node records rather than as a contiguous block of memory. Each node contains a payload and one or more links to neighboring nodes. The links preserve the logical order even when the nodes are located in different memory locations.

The list keeps a reference to its first node, called the head. A node’s next link identifies the following node, and the final node’s next link is null. Some implementations also maintain a tail, which refers to the last node.

A useful mental model is a chain: the head identifies where the chain begins, each node identifies the next link in the chain, and null marks its end.

Takeaway: Linked lists trade direct positional access for flexible node-based storage.

Singly and doubly linked lists

A singly linked list gives each node a link only to the next node. To perform Traversal, begin at the head and repeatedly follow next until the current reference is null. Visiting every node in a list of $n$ nodes takes $O(n)$ time.

Accessing the element at position $i$ also requires following links from the head, so it takes $O(i)$ time and can take $O(n)$ time in the worst case. The list cannot move backward directly because nodes do not store links to their predecessors.

A doubly linked list adds a prev link to every node. Its nodes can therefore move forward through next and backward through prev. The first node has prev equal to null, and the last node has next equal to null.

Doubly linked lists use more memory and require more link updates. If one link is updated without consistently updating the corresponding neighboring link, the structure can become invalid.

Takeaway: Singly linked lists are simpler and use less link storage; doubly linked lists provide bidirectional movement.

Insertion and deletion

Linked-list updates are efficient when the relevant location is already known. To insert a new node at the front, connect the new node to the current head and then make the new node the head. This requires a constant number of reference changes and takes $O(1)$ time.

If a reference to a node named current is available, insertion after it can be performed by connecting the new node to current.next and then connecting current to the new node. The relinking takes $O(1)$ time, but finding current by index or value may take $O(n)$ time.

Deleting the first node also takes $O(1)$ time: save the current head and advance the head to its next node. To delete a node after a known predecessor, connect the predecessor directly to the removed node’s successor. The pointer update is $O(1)$, while locating the predecessor may take $O(n)$.

In a doubly linked list, removing a known node requires reconnecting its previous neighbor to its next neighbor and updating the reverse link. This is $O(1)$ when the target reference is already available.

Takeaway: Separate the cost of locating a position from the cost of changing links at that position.

Searching linked lists

A linear search checks nodes one at a time. It begins at the head, compares each node’s value with the target, and stops when it finds a match or reaches null. The best case is $O(1)$ when the target is at the head. The worst case is $O(n)$ when the target is at the end or absent.

A sorted linked list may stop once it encounters a value greater than the target, but ordinary binary search is still not efficient. Binary search needs fast access to the middle element, whereas finding that element in a linked list requires walking through nodes.

Thus, linked lists are generally searched sequentially rather than by repeatedly jumping to a middle position.

Takeaway: Sorting can allow early stopping, but it does not give a linked list fast random access.

Linked lists versus arrays

An array and a linked list both represent ordered sequences, but they favor different operations.

• An array provides indexed access in $O(1)$ time because an element’s location can be calculated directly.

• A singly linked list usually needs $O(n)$ time to access an arbitrary index because it must follow links from the head.

• Searching an unsorted array or linked list takes $O(n)$ time.

• Inserting or deleting near the front or middle of an array commonly takes $O(n)$ time because elements may need to shift.

• Inserting or deleting after a known linked-list reference takes $O(1)$ time because only links change.

• Traversing all elements takes $O(n)$ time in both structures.

• Arrays usually have compact, contiguous storage, while linked lists use non-contiguous storage and require extra memory for links.

The linked-list comparison assumes that the insertion or deletion location is already known. If the program must first search for that location, the search cost must be included. A dynamic array may also append in amortized $O(1)$ time, although an occasional resize can take $O(n)$ time.

Takeaway: Choose based on the dominant operation: arrays favor random access, while linked lists favor known-location structural changes.

Choosing the right structure

Choose a singly linked list when the program mainly moves forward, low per-node memory use matters, and updates can use a known predecessor. Its simpler structure reduces link-maintenance work.

Choose a doubly linked list when the program must move both forward and backward, or when nodes need to be removed efficiently using their own references. The extra prev link costs memory and creates another relationship that must remain consistent.

A linked list is not automatically faster than an array. Its advantage appears when frequent insertions and deletions matter more than fast indexing, compact storage, or favorable cache behavior. If a program frequently accesses elements by numeric position, an array may be the better choice.

Takeaway: Match the structure to the access pattern, update pattern, memory constraints, and whether the relevant node or predecessor is already known.