Linked list is a Data Structure made of nodes where each node stores a value and a reference to the next node.
Unlike an array, the elements of a linked list do not need to be stored next to each other in memory.
Each node usually contains:
- A value
- A pointer or reference to the next node
Linked lists are useful when:
- Insertions and deletions near known nodes are common
- The collection changes size frequently
- Contiguous memory is not required
Common tradeoffs:
- Access by index is O(n)
- Searching is O(n)
- Inserting after a known node is O(1)
- Deleting after a known node is O(1)
A linked list has slower random access than an array because it must be traversed node by node.
flowchart LR Head["head"] --> A["node: A"] A --> B["node: B"] B --> C["node: C"] C --> Nil["nil"]
Anki
id: linked-list-definition deck: Computer Science::Data Structures tags: data-structures linked-list
Q: What does each node in a linked list store? A: A value and a reference or pointer to the next node.
id: linked-list-vs-array deck: Computer Science::Data Structures tags: data-structures linked-list array
Q: Why is finding the 100th item in a linked list slower than finding the 100th item in an array? A: A linked list must follow links one by one; an array can jump directly to an index.