Template:List data structure comparison

From blackwiki
Revision as of 09:58, 18 May 2013 by 60.242.88.97 (talk) (for a simple singly linked list without a direct pointer to the last node, insert/delete at end for a linked list is O(n) to get to the last node.)
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 Θ(n) N/A Θ(1) amortized Θ(log n) Θ(log n) updating
Insert/delete in middle search time +
Θ(1)[1][2][3]
N/A Θ(n) Θ(log n) Θ(log n) updating
Wasted space (average) Θ(n) 0 Θ(n)[4] Θ(n) Θ(n)

References

  1. Gerald Kruse. CS 240 Lecture Notes: Linked Lists Plus: Complexity Trade-offs. Juniata College. Spring 2008.
  2. Day 1 Keynote - Bjarne Stroustrup: C++11 Style at GoingNative 2012 on channel9.msdn.com from minute 45 or foil 44
  3. Number crunching: Why you should never, ever, EVER use linked-list in your code again at kjellkod.wordpress.com
  4. 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)