View source for Template:List data structure comparison

{|class="wikitable"
|+ Comparison of list data structures
|-
! rowspan=2 |
! rowspan=2 | Peek <br/>(index)
! colspan=3 | Mutate (insert or delete) at …
! rowspan=2 | Excess space, <br/>average
|-
! Beginning
! End
! Middle
|-
| [[Linked list]]
| {{no|Θ(''n'')}}
| {{yes|Θ(1)}}
| {{yes|Θ(1), known end element;<br/>Θ(''n''), unknown end element}}
| {{partial|Peek time + <br/>Θ(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>}}
| {{no|Θ(''n'')}}
|-
| [[Array data structure|Array]]
| {{yes|Θ(1)}}
| {{n/a}}
| {{n/a}}
| {{n/a}}
| {{yes|0}}
|-
| [[Dynamic array]]
| {{yes|Θ(1)}}
| {{no|Θ(''n'')}}
| {{yes|Θ(1) [[amortized analysis|amortized]]}}
| {{no|Θ(''n'')}}
| {{no|Θ(''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>}}
|-
| [[Self-balancing binary search tree|Balanced tree]]
| {{partial|Θ(log n)}}
| {{partial|Θ(log n)}}
| {{partial|Θ(log ''n'')}}
| {{partial|Θ(log ''n'')}}
| {{no|Θ(''n'')}}
|-
| Random-{{nowrap|access list}}
| {{partial|Θ(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>}}
| {{yes|Θ(1)}}
| {{n/a}}<ref name="okasakiComparison"/>
| {{n/a}}<ref name="okasakiComparison"/>
| {{no|Θ(''n'')}}
|-
| [[Hashed array tree]]
| {{yes|Θ(1)}}
| {{no|Θ(''n'')}}
| {{yes|Θ(1) [[amortized analysis|amortized]]}}
| {{no|Θ(''n'')}}
| {{partial|Θ(√''n'')}}
|}
<noinclude>{{Template reference list}}[[Category:Templates that generate named references]]</noinclude>