Template:List data structure comparison

From blackwiki
Revision as of 01:44, 24 February 2017 by 2001:56a:71ab:3a00:a5b1:ef7e:be63:ed0a (talk) (The last element is known in most implementations (keeping a tail pointer is cheap))
Jump to navigation Jump to search
Comparison of list data structures
Linked list Array Dynamic array Balanced tree Random access list hashed array tree
Indexing Θ(n) Θ(1) Θ(1) Θ(log n) Θ(log n)[1] Θ(1)
Insert/delete at beginning Θ(1) N/A Θ(n) Θ(log n) Θ(1) Θ(n)
Insert/delete at end Θ(1) when last element is known;
Θ(n) when last element is unknown
N/A Θ(1) amortized Θ(log n) Θ(log n) updating Θ(1) amortized
Insert/delete in middle search time + Θ(1)[2][3][4] N/A Θ(n) Θ(log n) Θ(log n) updating Θ(n)
Wasted space (average) Θ(n) 0 Θ(n)[5] Θ(n) Θ(n) Θ(Template:Sqrt)

References

  1. Chris Okasaki (1995). "Purely Functional Random-Access Lists". Proceedings of the Seventh International Conference on Functional Programming Languages and Computer Architecture: 86–95. doi:10.1145/224164.224187.
  2. Gerald Kruse. CS 240 Lecture Notes: Linked Lists Plus: Complexity Trade-offs. Juniata College. Spring 2008.
  3. Day 1 Keynote - Bjarne Stroustrup: C++11 Style at GoingNative 2012 on channel9.msdn.com from minute 45 or foil 44
  4. Number crunching: Why you should never, ever, EVER use linked-list in your code again at kjellkod.wordpress.com
  5. Brodnik, Andrej; Carlsson, Svante; Sedgewick, Robert; Munro, JI; Demaine, ED (1999), Resizable Arrays in Optimal Time and Space (Technical Report CS-99-09) (PDF), Department of Computer Science, University of Waterloo