Singly, Doubly and Circular Linked Lists

A linked list stores a sequence in separately allocated nodes. Each node contains an element and one or more links that identify neighboring nodes. Unlike an array, the nodes do not have to occupy consecutive memory locations. Their links establish the logical order.

This organization makes insertion and deletion efficient when the relevant position is already known, because neighboring links can be changed without shifting later elements. The tradeoff is that direct indexed access is lost. To reach position i, traversal generally begins at an endpoint and follows links one node at a time, taking O(i) time and O(n) in the worst case.

Singly Linked Lists

A singly linked node contains a data value and a next reference. A head reference identifies the first node. The final node has a null next reference and a null head represents an empty list. If a tail reference is maintained, it identifies the final node.

The fundamental representation invariant is that following next from the head visits every node in sequence exactly once and eventually reaches null. For an empty list, both head and a maintained tail should be null. For a nonempty list, tail must be reachable from head and tail.next must be null. A stored size, if present, must equal the number of reachable nodes.

Traversal starts at head and repeatedly replaces the current reference with current.next. It stops when current becomes null. Searching compares each visited value with the target. Successful search can finish early, while an unsuccessful search examines all n nodes. Thus search and arbitrary indexed access are O(n).

Insertion

To insert value x at the front, create a node whose next link is the old head, then assign head to the new node. If the list was empty, tail must also identify the new node. The operation takes O(1) time.

To insert after an already known node p, create node q, set q.next to p.next and then set p.next to q. This order preserves the remainder of the list. If p was the tail, update tail to q. The relinking takes O(1), although finding p may have required O(n) time.

Appending is O(1) when a valid tail reference is maintained: connect tail.next to the new node and move tail. Without a tail, the list must be traversed to find its final node, so append is O(n). Maintaining tail improves append but adds an invariant that every deletion must preserve.

Deletion

Deleting the head saves its value, moves head to head.next and returns the saved value. When this removes the only node, tail must also become null. Deleting a node after a known predecessor p sets p.next to p.next.next; if the removed node was the tail, tail becomes p.

To unlink a particular node from a singly linked list, its predecessor is generally needed because that predecessor holds the link that bypasses the node. A tail reference alone does not make tail deletion constant-time: the new tail’s location still has to be found by walking from the head. Tail deletion is therefore O(n) unless additional backward information is stored.

References to removed nodes should be treated carefully. In manually managed languages, the node’s storage must be released exactly once after it is disconnected. In garbage-collected languages, removing all list references makes an otherwise unreachable node eligible for collection. External references held elsewhere may keep it alive even though it is no longer in the list.

Reversing a Singly Linked List

Iterative reversal redirects every next link. Three references are sufficient: previous, current and next. Initially, previous is null and current is head. On each iteration:

Save current.next in next.
Set current.next to previous.
Move previous to current.
Move current to the saved next node.

Saving the original next reference before overwriting it is essential; otherwise, the unprocessed suffix becomes unreachable. When current becomes null, previous identifies the new head. If a tail is stored, the old head becomes the new tail. Every node is visited once, giving O(n) time and O(1) auxiliary reference space.

A recursive reversal can express the same transformation compactly. It reverses the suffix, makes the successor point back to the current node and clears the current node’s old forward link. Its running time is O(n), but it uses O(n) call-stack space and risks stack overflow for a very long list.

Doubly Linked Lists

A doubly linked node contains both next and previous references. The list commonly maintains head and tail, enabling traversal in either direction. The head has no predecessor and the tail has no successor.

Given a known node, insertion before or after it and deletion of it can be performed in O(1) time. Removing node x connects x.previous.next to x.next and connects x.next.previous to x.previous. At the boundaries, head or tail must be updated instead of dereferencing a missing neighbor. Clearing x’s links after removal can make accidental reuse easier to detect and can avoid unnecessary retention in some environments.

The extra previous link improves backward traversal and makes unlinking a known node independent of a separate predecessor search. It also increases storage and doubles the link relationships that mutations must maintain. For every adjacent pair a and b, if a.next == b, then b.previous must equal a. A half-updated operation can leave traversal working in one direction but broken in the other.

Doubly linked lists are useful for deques, navigation histories, least-recently-used caches and structures where arbitrary known nodes frequently move or disappear. An LRU cache commonly combines a hash table, which finds a node in expected O(1) time, with a doubly linked list, which moves or removes that node in O(1) time.

Circular Linked Lists

In a circular linked list, traversal does not end at null. The final node links back into the list, commonly to the head. A nonempty singly circular list with a tail can identify its head as tail.next. This allows constant-time insertion at either logical end: inserting after tail adds a front node, while inserting after tail and then moving tail adds a rear node.

Traversal must use a circular stopping condition. Starting from a node, process it and advance until the current reference returns to the starting node. A do-while structure is often natural because a nonempty circular list must process its starting node once before testing for a return. Searching only for null would never terminate in a correctly formed circle.

A one-node circular list points back to itself. Deleting that only node must produce the chosen empty representation, usually a null tail or head. With multiple nodes, deleting head changes tail.next; deleting tail still needs the predecessor in a singly circular representation.

Circular lists suit repeated cyclic processing such as round-robin scheduling, turn rotation and playlists. Circularity is a structural property rather than proof that every node belongs to the intended cycle. A corrupted link can create a smaller unintended cycle and make some nodes unreachable.

Sentinel Nodes

A sentinel or dummy node is a permanent structural node that does not represent an ordinary list element. A singly linked list may use a head sentinel whose next link identifies the first data node. A doubly linked list may use head and tail sentinels or one circular sentinel connected to itself when the list is empty.

Sentinels reduce boundary cases. Insertion and deletion can often update ordinary neighboring nodes without separately asking whether the position is at the beginning or end. They do not eliminate the need for invariants and client code must not return the sentinel as user data. Their small space cost can simplify implementation considerably.

Cycle Detection

Floyd’s cycle-detection algorithm uses a slow reference that advances one link per step and a fast reference that advances two. If a reachable cycle exists, the two references eventually meet inside it. If the fast reference reaches null, the list is acyclic. The algorithm takes O(n) time and O(1) auxiliary space.

After a meeting, the cycle entry can be found by moving one reference to head and then advancing both references one step at a time; their next meeting is the entry. This works because of the distance relationships created by the first meeting. A hash set of visited node identities is an easier alternative, but it uses O(n) additional space.

Arrays, Lists and Indexed Links

Arrays provide O(1) indexed access, compact storage and strong cache locality. Linked lists provide flexible node-by-node growth and constant-time relinking at a known location. They do not automatically make insertion “faster”: if the program must first find position i, the search still takes O(n). Modern memory hierarchies also make array traversal substantially faster in many practical workloads.

Links need not be machine references. A program can store nodes in an array and use integer indices as next and previous links. This cursor-based representation supports pools, serialization and environments where raw pointers are unsuitable. The same logical invariants apply, with a special index such as -1 representing no link.

Safe Mutation and Testing

Link updates should be planned from the invariant outward. Preserve any reference that will be needed after a link changes, update both directions in a doubly linked list and handle transitions involving zero or one node deliberately. Mutating while traversing requires saving the next traversal position before deleting the current node.

Useful boundary cases include an empty list, one element, two elements, insertion and deletion at both ends, removal of a missing value and repeated removal until empty. For circular lists, traversal tests need an explicit step bound so corruption is reported rather than hanging. An invariant checker can count reachable nodes, compare the count with stored size, verify endpoints, validate forward and backward links and detect an unexpected cycle.

The choice among singly, doubly and circular forms depends on the operations. Singly linked lists minimize link storage and suit forward processing. Doubly linked lists support bidirectional movement and constant-time removal of a known node. Circular lists represent repeated rotation naturally. Their value comes from matching those access patterns, not merely from avoiding contiguous memory.