A linked list is a data structure that stores a sequence in nodes. Each node in a singly linked list holds a value and a reference to the next node. A head reference points to the first node, and the last node normally points to null. In a market-data replay queue, these links let a worker insert or remove a job with a few reference changes if it already has the right node. An incorrect link can also send the worker around a loop instead of letting it finish the queue. Morin, Open Data Structures, §3.1 · Carnegie Mellon, Linked Lists, §§2–3
Change the link that leads into the gap
A fictional replay queue starts with A → B → D. The worker has a reference to B and wants to schedule job C immediately after it. First set C's next link to D, the old successor of B. Then point B to C. Saving the old successor before overwriting B's link keeps the rest of the queue connected. The traversal now visits A, B, C and D.
Next, cancel B. The worker already holds A, the node immediately before B. Set A's next link to B's successor, C. From the head, the worker now visits A, C and D. C and D stay in place, and D still points to null.
Inserting C changes two next links. Removing B redirects A's link and leaves C's link to D intact.
With these references in hand, both edits take work on the list. Starting with only a job ID, the worker may have to search through nodes. Even a direct reference to B generally leaves a search for its predecessor when removing that exact node from a plain singly linked list. A doubly linked list adds a previous reference to each node. With a reference to B, the worker can then update both neighbours directly. A hash table can map job IDs to nodes in that design, so the lookup and the unlink are separate operations with separate costs. Cornell, Linked Data, Adding and Removing Elements · Morin, Open Data Structures, §3.2
Tail access and scan costs
A maintained tail reference lets a singly linked list append in time. Removing the tail still takes in the worst case when the predecessor is unknown. The tail gives you the last node, but the next link in that node provides no way back. On removal, the previous node must become the new tail. When the only node is removed, both head and tail become null. A doubly linked list with both end references supports constant-time insertion and removal at either end. These are the operations of a deque, an interface that can also use a circular array. Morin, Open Data Structures, §3.1 · §3.2 · §2.4
An array can jump directly to a given index, whereas the singly linked list generally follows links from the head. Inserting in the middle of a packed, array-backed list shifts later slots, while a list splice changes only a few links after the position is found. A full scan is linear in either case, but contiguous slots let one cache-line fetch serve several nearby reads. With individually allocated nodes, each next link can lead to a different cache line. If the workload repeatedly scans the queue, memory layout can matter even when the growth rates match. Morin, Open Data Structures, §2.1 · Cornell, Memory and Locality
When the walk never reaches null
A cycle occurs when following next links from the head brings you back to a node you have already visited. Suppose a faulty edit makes D point to C after B is removed. The worker follows A → C → D → C and then keeps alternating between D and C. Two jobs with the same value are harmless here. What matters is revisiting the same node.
Floyd's cycle detection starts a slow and a fast reference at the head. In each round, move slow one link and fast two links. Stop with no cycle if fast is null or has no successor before a round. Check for a meeting after moving, since both references started at the head. On the faulty replay queue, the two references meet in round 2.
| Round | Slow | Fast |
|---|---|---|
| Start | A | A |
| 1 | C | D |
| 2 | D | D |
On the ordinary list, fast is already at D after round 1 and D has no successor. With the bad link, both references enter the loop and fast gains one position per round relative to slow. It must catch up within as many rounds as there are nodes in the loop. The meeting at D detects a cycle even though C is the first node in that cycle. With distinct reachable nodes and fixed links during the check, this takes time and extra space. Cornell, Linked Data, Exercise 13.11 · Carnegie Mellon, Linked Lists, §3
Further reading
For diagrams of contiguous and linked storage and exercises on FIFO and LIFO, see Arrays, Linked Lists, Stacks, and Queues (public preview, full lesson with membership).
Sources
- Pat Morin, Open Data Structures. §3.1 Singly linked lists, §3.2 Doubly linked lists §2.1 Array-backed lists and §2.4 Array-backed deques.
- Cornell CS 3110. Memory and locality.
- Cornell CS 2110. Linked Data, Exercise 13.11.
- Carnegie Mellon 15-122. Linked Lists, §§2–3.