Difference between revisions of "Template:List data structure comparison"

From blackwiki
Jump to navigation Jump to search
(search time is _the_ huge tradeoff for linked lists. In theory the memory isn't fragmented. In reality memory is fragmented so while searching through the list you are maximising cache misses. Arrays are faster in insert/delete because of search time)
imported>Dcoetzee
(Restoring red to inserting in middle of dynamic array - it's awful in theory and in practice for a large dynamic array.)
Line 27: Line 27:
 
|style="background:#ffdddd"|search time +<br/>Θ(1)<ref>Gerald Kruse. [http://www.juniata.edu/faculty/kruse/cs240/syllabus.htm CS 240 Lecture Notes]: [http://www.juniata.edu/faculty/kruse/cs240/linkedlist2.htm Linked Lists Plus: Complexity Trade-offs]. Juniata College. Spring 2008.</ref><ref>[http://channel9.msdn.com/Events/GoingNative/GoingNative-2012/Keynote-Bjarne-Stroustrup-Cpp11-Style ''Day 1 Keynote - Bjarne Stroustrup: C++11 Style''] at ''GoingNative 2012'' on ''channel9.msdn.com'' from minute 45 or foil 44</ref><ref>[http://kjellkod.wordpress.com/2012/02/25/why-you-should-never-ever-ever-use-linked-list-in-your-code-again/ ''Number crunching: Why you should never, ever, EVER use linked-list in your code again''] at ''kjellkod.wordpress.com''</ref>
 
|style="background:#ffdddd"|search time +<br/>Θ(1)<ref>Gerald Kruse. [http://www.juniata.edu/faculty/kruse/cs240/syllabus.htm CS 240 Lecture Notes]: [http://www.juniata.edu/faculty/kruse/cs240/linkedlist2.htm Linked Lists Plus: Complexity Trade-offs]. Juniata College. Spring 2008.</ref><ref>[http://channel9.msdn.com/Events/GoingNative/GoingNative-2012/Keynote-Bjarne-Stroustrup-Cpp11-Style ''Day 1 Keynote - Bjarne Stroustrup: C++11 Style''] at ''GoingNative 2012'' on ''channel9.msdn.com'' from minute 45 or foil 44</ref><ref>[http://kjellkod.wordpress.com/2012/02/25/why-you-should-never-ever-ever-use-linked-list-in-your-code-again/ ''Number crunching: Why you should never, ever, EVER use linked-list in your code again''] at ''kjellkod.wordpress.com''</ref>
 
|{{n/a}}
 
|{{n/a}}
|style="background:#ffffdd"|Θ(''n'')
+
|style="background:#ffdddd"|Θ(''n'')
 
|style="background:#ffffdd"|Θ(log n)
 
|style="background:#ffffdd"|Θ(log n)
 
|style="background:#ffffdd"|Θ(log n) updating
 
|style="background:#ffffdd"|Θ(log n) updating

Revision as of 00:07, 28 April 2012

  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][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)