Data Structures
What Is a Linked List?
A linked list is a sequence of nodes where each node holds a value and a pointer to the next node, instead of sitting side by side in memory.
Definition
A linked list stores items in nodes. Each node holds a value and a reference (pointer) to the next node. The list is reached through its first node, the head, and the last node points to nothing.
Because nodes can sit anywhere in memory, the list grows one node at a time without moving the others.
How it works
Inserting or removing a node takes O(1) time once you hold the node before it: you only change one pointer. Finding the nth item takes O(n), because you must walk from the head.
In a doubly linked list each node also points back to the previous node, so you can walk in both directions.