- A head element followed by a series of nodes connected by links.
- Commonly singly or doubly linked. Other configurations have been proposed.
- Can be used to implement other data types including – lists, stacks, queues, associative arrays, and S-expressions.
- Quick inserts and deletes
- Dynamic size. Able to grow without having to reallocate the entire data structure. Able to shrink and return unused space.
- Insertion and removal from any point in the list in constant time.
- Does not allow random access, inherently sequential access.
- Slow traversal, requires visiting each node in order.
- Memory and space overhead of pointers – not good for small data loads.
|Insert/delete at beginning||Θ(1)|
|Insert/delete at end||Θ(n) when last element is unknown;
Θ(1) when last element is known
|Insert/delete in middle||search time + Θ(1)|
|Wasted space (average)||Θ(n)|
Singly Linked List
- Singly linked lists are recursive data structures. For that reason, many operations have a very simple recursive algorithm.
Doubly Linked List
- Require more space per node and operations are slightly more expensive.
- Easier to manipulate, sequential access forwards and backwards.
- Insertion or deletion in a constant time given only a nodes address.
Array Based Linked List
|2 (listHead)||4||-1||Adams, Adam|