| Structure | Array | Dynamic Array |
|---|---|---|
| Prepend | O(n) | O(n) |
| Insert | O(n) | O(n) |
| Append | O(n) | O(1) |
| Remove First | O(n) | O(n) |
| Remove Index | O(n) | O(n) |
| Remove Last | O(n) | O(1) |
| Random Access | O(1) | O(1) |
What if we stored memory non-contiguously?
Unlike arrays, in linked lists, data is stored
non-contiguously in
these nodes
Where nodes only contain data and *next
Where nodes only contain data and *next, but no node points to null
Where nodes only contain data and *next, but no node points to null
Where nodes only contain data and *next, but no node points to null
What should the underlying structure be?
They allow fast pushes and pops from either end.