Template:List data structure comparison
Revision as of 12:40, 19 June 2011 by imported>Dcoetzee (Create from Linked list, http://en.wikipedia.org/w/index.php?title=Linked_list&oldid=434305999)
| Doubly 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.