Linked List
- Data can be anywhere in computer memory
- Each item stores address of the next item in the list
Complexity
| Average Time | Space | |
|---|---|---|
| Access | $O(n)$ | $O(n)$ |
| Search | $O(n)$ | $O(n)$ |
| Insert | $O(1)$ | $O(n)$ |
| Delete | $O(1)$ | $O(n)$ |
| Append | $O(n)$ | $O(n)$ |
| Average Time | Space | |
|---|---|---|
| Access | $O(n)$ | $O(n)$ |
| Search | $O(n)$ | $O(n)$ |
| Insert | $O(1)$ | $O(n)$ |
| Delete | $O(1)$ | $O(n)$ |
| Append | $O(n)$ | $O(n)$ |