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>Mikeblas
(use unique name for reference to avoid duplication at transclusion; add category)
 
(23 intermediate revisions by 16 users not shown)
Line 1: Line 1:
<div class=tright align=right>
 
 
{|class="wikitable"
 
{|class="wikitable"
!&nbsp;!![[Linked list]]!![[Array data structure|Array]]!![[Dynamic array|Dynamic<br />array]]!![[Self-balancing binary search tree|Balanced<br />tree]]!![[Random access list|Random access<br />list]]
+
|+ Comparison of list data structures
 +
!
 +
![[Linked list]]
 +
![[Array data structure|Array]]
 +
![[Dynamic array]]
 +
![[Self-balancing binary search tree|Balanced tree]]
 +
![[Random access list|Random {{nowrap|access list}}]]
 +
![[Hashed array tree]]
 
|-
 
|-
 
|Indexing
 
|Indexing
Line 8: Line 14:
 
|style="background:#ddffdd"|Θ(1)
 
|style="background:#ddffdd"|Θ(1)
 
|style="background:#ffffdd"|Θ(log n)
 
|style="background:#ffffdd"|Θ(log n)
|style="background:#ffffdd"|Θ(log n)
+
|style="background:#ffffdd"|Θ(log n)<ref name="okasakiComparison">{{cite journal
 +
|title=Purely Functional Random-Access Lists
 +
|author=Chris Okasaki
 +
|journal=Proceedings of the Seventh International Conference on Functional Programming Languages and Computer Architecture
 +
|year=1995
 +
|pages=86-95
 +
|doi=10.1145/224164.224187
 +
}}</ref>
 +
|style="background:#ddffdd"|Θ(1)
 
|-
 
|-
|Insert/delete at beginning
+
|{{nowrap|Insert/delete}} at beginning
 
|style="background:#ddffdd"|Θ(1)
 
|style="background:#ddffdd"|Θ(1)
 
|{{n/a}}
 
|{{n/a}}
Line 16: Line 30:
 
|style="background:#ffffdd"|Θ(log n)
 
|style="background:#ffffdd"|Θ(log n)
 
|style="background:#ddffdd"|Θ(1)
 
|style="background:#ddffdd"|Θ(1)
 +
|style="background:#ffdddd"|Θ(''n'')
 
|-
 
|-
|Insert/delete at end
+
|{{nowrap|Insert/delete}} at end
|style="background:#ddffdd"|Θ(1)
+
|style="background:#ddffdd"|Θ(1) when last {{nowrap|element is known}};<br/>Θ(''n'') when last {{nowrap|element is unknown}}
 
|{{n/a}}
 
|{{n/a}}
 
|style="background:#ddffdd"|Θ(1) [[Amortized analysis|amortized]]
 
|style="background:#ddffdd"|Θ(1) [[Amortized analysis|amortized]]
|style="background:#ffffdd"|Θ(log n)
+
|style="background:#ffffdd"|Θ(log ''n'')
|style="background:#ffffdd"|Θ(log n) updating
+
|{{n/a}} <ref name="okasakiComparison"/>
 +
|style="background:#ddffdd"|Θ(1) [[Amortized analysis|amortized]]
 
|-
 
|-
|Insert/delete in middle
+
|{{nowrap|Insert/delete}} in middle
|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:#ffffdd"|search time + {{nowrap|Θ(1)}}<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
+
|{{n/a}} <ref name="okasakiComparison"/>
 +
|style="background:#ffdddd"|Θ(''n'')
 
|-
 
|-
|Wasted space (average)
+
|{{nowrap|Wasted space}} (average)
 
|style="background:#ffdddd"|Θ(''n'')
 
|style="background:#ffdddd"|Θ(''n'')
 
|style="background:#ddffdd"|0
 
|style="background:#ddffdd"|0
|style="background:#ffdddd"|Θ(''n'')<ref name="brodnik">{{Citation | title=Resizable Arrays in Optimal Time and Space | date=Technical Report CS-99-09 | url=http://www.cs.uwaterloo.ca/research/tr/1999/09/CS-99-09.pdf | year=1999 | first1=Andrej | last1=Brodnik | first2=Svante | last2=Carlsson | first5=ED | last5=Demaine | first4=JI | last4=Munro | first3=Robert | last3=Sedgewick | author3-link=Robert Sedgewick (computer scientist) | publisher=Department of Computer Science, University of Waterloo}}</ref>
+
|style="background:#ffdddd"|Θ(''n'')<ref>{{Citation | title=Resizable Arrays in Optimal Time and Space (Technical Report CS-99-09) | url=http://www.cs.uwaterloo.ca/research/tr/1999/09/CS-99-09.pdf | year=1999 | first1=Andrej | last1=Brodnik | first2=Svante | last2=Carlsson | first5=ED | last5=Demaine | first4=JI | last4=Munro | first3=Robert | last3=Sedgewick | author3-link=Robert Sedgewick (computer scientist) | publisher=Department of Computer Science, University of Waterloo}}</ref>
 
|style="background:#ffdddd"|Θ(''n'')
 
|style="background:#ffdddd"|Θ(''n'')
 
|style="background:#ffdddd"|Θ(''n'')
 
|style="background:#ffdddd"|Θ(''n'')
 +
|style="background:#ffffdd"|Θ({{radic|''n''}})
 
|}
 
|}
</div>
+
<noinclude>{{Template reference list}}[[Category:Templates that generate named references]]</noinclude>
<noinclude>{{Template reference list}}</noinclude>
 

Latest revision as of 21:43, 28 September 2020

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) N/A [1] Θ(1) amortized
Insert/delete in middle search time + Θ(1)[2][3] N/A Θ(n) Θ(log n) N/A [1] Θ(n)
Wasted space (average) Θ(n) 0 Θ(n)[4] Θ(n) Θ(n) Θ(Template:Radic)

References

  1. 1.0 1.1 1.2 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