Linked List
Nodes connected by references instead of contiguous addresses
Follow links to reach data
A singly linked list stores a value and a reference to the next node in each node. The nodes may live anywhere in memory, so the list can grow without relocating all existing values. The tradeoff is traversal: reaching index i requires following every preceding link, which takes O(i) time.
Select a node, then choose an operation above.
Once a node is known, inserting or removing its successor only rewires a constant number of references. Finding that position may still cost O(n), so linked lists are most useful when an algorithm already holds the relevant node.
Doubly linked lists move both ways
Adding a previous reference enables backward traversal and constant-time removal of a known node. It also increases memory use and makes every update responsible for two directions. Move the cursor and watch both neighbor links remain consistent.
Each node has prev and next links. Traverse backward, or select a node to delete it.
a and b, a.next === b and b.prev === a. A partial update can silently split the list. Linked nodes are the building blocks behind the stack, queues, and the recency order in an LRU cache.