Linked list

A linked list is a sequence of nodes. Each node stores a value and a link to the next node; a doubly linked list stores links in both directions.

The priority queue in Priority queue already expresses the urgent-work rule. A linked list is worth considering only for a different requirement, such as frequent local insertion and removal when the relevant node is already known.

first = node(value: "first")
second = node(value: "second")
first.next = second

Inserting or removing a node is usually O(1) when you already have the relevant node. Finding an item by position is O(n) because the list must be traversed from its head. Linked lists also use extra memory for links and usually have poorer cache locality than arrays.

For this case study, the linked list is not automatically an improvement over the report log or the built-in queue.

See Linked list examples for runnable examples in supported programming languages.