Template:List data structure comparison

From blackwiki
Revision as of 01:45, 20 June 2011 by imported>Dcoetzee (Reference for linear space wasted by dynamic array)
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)[2] Θ(n)

References

  1. Gerald Kruse. CS 240 Lecture Notes: Linked Lists Plus: Complexity Trade-offs. Juniata College. Spring 2008.
  2. Brodnik, Andrej; Carlsson, Svante; Sedgewick, Robert; Munro, JI; Demaine, ED (Technical Report CS-99-09), Resizable Arrays in Optimal Time and Space (PDF), Department of Computer Science, University of Waterloo Check date values in: |date=, |year= / |date= mismatch (help)