Template:List data structure comparison

From blackwiki
Revision as of 13:15, 22 July 2012 by imported>Angbor (insert/delete somewhere in middle of linked list is only O(1); additional time comes from indexing which is usually not necessary and listed separately)
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 Θ(1) N/A Θ(n) Θ(log n) Θ(log n) updating
Wasted space (average) Θ(n) 0 Θ(n)[1] Θ(n) Θ(n)

References

  1. 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)