Template:List data structure comparison

From blackwiki
Revision as of 05:10, 31 October 2011 by 91.213.255.7 (talk) (link was badly done)
Jump to navigation Jump to search
  Linked list Array Dynamic
array
Balanced
tree
Random access
list
Indexing Θ(n) Θ(1) Θ(1) Θ(log n) Θ(log n)
Insert/delete at beginning Θ(1) N/A Θ(n) Θ(log n) Θ(1)
Insert/delete at end Θ(1) N/A Θ(1) amortized Θ(log n) Θ(log n) updating
Insert/delete in middle search time +
Θ(1)[1]
N/A Θ(n) Θ(log n) Θ(log n) updating
Wasted space (average) Θ(n) 0 Θ(n)[2] Θ(n) Θ(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)