3.1: Contiguous vs Linked Data Structures
Linked lists vs static arrays
The relative advantages of linked lists over static arrays include:
- Overflow on linked structures can never occur unless the memory is actually full.
- Insertions and deletions are simpler than for contiguous (array) lists.
- With large records, moving pointers is easier and faster than moving the items themselves.
while the relative advantages of arrays include:
- Linked structures require extra space for storing pointer fields.
- Linked lists do not allow efficient random access to items.
- Arrays allow better memory locality and cache performance than random pointer jumping.