Difference between revisions of "Template:List data structure comparison"
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: | ||
| − | |||
{|class="wikitable" | {|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 | |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:# | + | |{{n/a}} <ref name="okasakiComparison"/> |
| + | |style="background:#ddffdd"|Θ(1) [[Amortized analysis|amortized]] | ||
|- | |- | ||
| − | |Insert/delete in middle | + | |{{nowrap|Insert/delete}} in middle |
| − | |style="background:# | + | |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:# | + | |style="background:#ffdddd"|Θ(''n'') |
| − | |style="background:#ffffdd"|Θ(log n) | + | |style="background:#ffffdd"|Θ(log ''n'') |
| − | |style="background:# | + | |{{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 | + | |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''}}) | ||
|} | |} | ||
| − | + | <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
| 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.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.
- ↑ Day 1 Keynote - Bjarne Stroustrup: C++11 Style at GoingNative 2012 on channel9.msdn.com from minute 45 or foil 44
- ↑ Number crunching: Why you should never, ever, EVER use linked-list in your code again at kjellkod.wordpress.com
- ↑ 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