Template:List data structure comparison

From blackwiki
Revision as of 12:46, 19 June 2011 by imported>Dcoetzee (Add balanced tree column from array data structure)
Jump to navigation Jump to search
  Linked list Array Dynamic
array
Balanced
tree
Indexing Θ(n) Θ(1) Θ(1) Θ(log n)
Insertion/deletion at beginning Θ(1) N/A Θ(n) Θ(log n)
Insertion/deletion at end Θ(1) N/A Θ(1) amortized Θ(log n)
Insertion/deletion in middle search time +
Θ(1)[1]
N/A Θ(n) Θ(log n)
Wasted space (average) Θ(n) 0 Θ(n) Θ(n)
  1. Gerald Kruse. CS 240 Lecture Notes: Linked Lists Plus: Complexity Trade-offs. Juniata College. Spring 2008.