Template:List data structure comparison
Revision as of 12:42, 19 June 2011 by imported>Dcoetzee (Link linked list so it can be used in all three articles)
| Linked list | Array | Dynamic array | |
|---|---|---|---|
| Indexing | Θ(n) | Θ(1) | Θ(1) |
| Insertion/deletion at beginning | Θ(1) | N/A | Θ(n) |
| Insertion/deletion at end | Θ(1) | N/A | Θ(1) amortized |
| Insertion/deletion in middle | search time + Θ(1)[1] |
N/A | Θ(n) |
| Wasted space (average) | Θ(n) | 0 | Θ(n) |
- ↑ Gerald Kruse. CS 240 Lecture Notes: Linked Lists Plus: Complexity Trade-offs. Juniata College. Spring 2008.