The two most fundamental data structures. Every higher-level structure (stacks, queues, trees, graphs) is implemented on top of them.
| Operation | Time | Reason |
|---|---|---|
| Access by index | O(1) | Direct address = base + i × size |
| Search (unsorted) | O(n) | Must scan all elements |
| Insert at end | O(1) amortized | Dynamic array doubles when full |
| Insert in middle | O(n) | Must shift elements right |
| Delete in middle | O(n) | Must shift elements left |
Trade-off: Arrays give O(1) random access but expensive middle insertions. Linked lists give O(1) head insert/delete but no random access. Choose based on workload.
For DS&A, you must internalize complexity for all operations:
| Structure | Access | Search | Insert | Delete |
|---|---|---|---|---|
| Array | O(1) | O(n) | O(n) | O(n) |
| Linked List | O(n) | O(n) | O(1)* | O(1)* |
| Hash Table | — | O(1) avg | O(1) avg | O(1) avg |
| BST (balanced) | — | O(log n) | O(log n) | O(log n) |
*at known position
Array access by index is O(1) because
Inserting in the middle of an array is O(n) because
A linked list has O(n) access because
When would you prefer a linked list over an array?
Dynamic arrays (like Python lists) achieve O(1) amortized append by