Template:List data structure comparison

From blackwiki
Revision as of 17:38, 19 June 2011 by imported>Salamurai (<noinclude>{{Template reference list}}</noinclude>)
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)

References

  1. Gerald Kruse. CS 240 Lecture Notes: Linked Lists Plus: Complexity Trade-offs. Juniata College. Spring 2008.