Template:List data structure comparison

From blackwiki
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)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search
  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)
  1. Gerald Kruse. CS 240 Lecture Notes: Linked Lists Plus: Complexity Trade-offs. Juniata College. Spring 2008.