Template:List data structure comparison

From blackwiki
Revision as of 00:46, 8 August 2018 by 169.237.4.127 (talk) (1/ URLs are broken (should be http://jcsites.juniata.edu/faculty/kruse/cs240/linkedlist2.htm), and also 2/ source is not relevant as the page only presents a table of algorithms' complexity without any explanations or justifications (it refers to a book chapter instead) -- I think this useless reference should therefore be removed.)
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] N/A Θ(n) Θ(log n) Θ(log n) updating Θ(n)
Wasted space (average) Θ(n) 0 Θ(n)[4] Θ(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. 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 (1999), Resizable Arrays in Optimal Time and Space (Technical Report CS-99-09) (PDF), Department of Computer Science, University of Waterloo