View source for Template:List data structure comparison

{|class="wikitable"
|+ 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
|style="background:#ffdddd"|Θ(''n'')
|style="background:#ddffdd"|Θ(1)
|style="background:#ddffdd"|Θ(1)
|style="background:#ffffdd"|Θ(log n)
|style="background:#ffffdd"|Θ(log n)<ref>{{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)
|-
|{{nowrap|Insert/delete}} at beginning
|style="background:#ddffdd"|Θ(1)
|{{n/a}}
|style="background:#ffdddd"|Θ(''n'')
|style="background:#ffffdd"|Θ(log n)
|style="background:#ddffdd"|Θ(1)
|style="background:#ffdddd"|Θ(''n'')
|-
|{{nowrap|Insert/delete}} at end
|style="background:#ddffdd"|Θ(1) when last {{nowrap|element is known}};<br/>Θ(''n'') when last {{nowrap|element is unknown}}
|{{n/a}}
|style="background:#ddffdd"|Θ(1) [[Amortized analysis|amortized]]
|style="background:#ffffdd"|Θ(log ''n'')
|style="background:#ffffdd"|Θ(log ''n'') updating
|style="background:#ddffdd"|Θ(1) [[Amortized analysis|amortized]]
|-
|{{nowrap|Insert/delete}} in middle
|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}}
|style="background:#ffdddd"|Θ(''n'')
|style="background:#ffffdd"|Θ(log ''n'')
|style="background:#ffffdd"|Θ(log ''n'') updating
|style="background:#ffdddd"|Θ(''n'')
|-
|{{nowrap|Wasted space}} (average)
|style="background:#ffdddd"|Θ(''n'')
|style="background:#ddffdd"|0
|style="background:#ffdddd"|Θ(''n'')<ref name="brodnik">{{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:#ffffdd"|Θ({{sqrt|''n''}})
|}
<noinclude>{{Template reference list}}</noinclude>