<?xml version="1.0"?>
<feed xmlns="http://www.w3.org/2005/Atom" xml:lang="en">
	<id>https://blackwiki.org/api.php?action=feedcontributions&amp;feedformat=atom&amp;user=122.111.75.152&amp;*</id>
	<title>blackwiki - User contributions [en]</title>
	<link rel="self" type="application/atom+xml" href="https://blackwiki.org/api.php?action=feedcontributions&amp;feedformat=atom&amp;user=122.111.75.152&amp;*"/>
	<link rel="alternate" type="text/html" href="https://blackwiki.org/index.php?title=Special:Contributions/122.111.75.152"/>
	<updated>2026-04-04T09:22:20Z</updated>
	<subtitle>User contributions</subtitle>
	<generator>MediaWiki 1.34.2</generator>
	<entry>
		<id>https://blackwiki.org/index.php?title=Template:List_data_structure_comparison&amp;diff=7086915</id>
		<title>Template:List data structure comparison</title>
		<link rel="alternate" type="text/html" href="https://blackwiki.org/index.php?title=Template:List_data_structure_comparison&amp;diff=7086915"/>
		<updated>2020-09-09T03:06:28Z</updated>

		<summary type="html">&lt;p&gt;122.111.75.152: &lt;/p&gt;
&lt;hr /&gt;
&lt;div&gt;{|class=&amp;quot;wikitable&amp;quot;&lt;br /&gt;
|+ Comparison of list data structures&lt;br /&gt;
!&lt;br /&gt;
![[Linked list]]&lt;br /&gt;
![[Array data structure|Array]]&lt;br /&gt;
![[Dynamic array]]&lt;br /&gt;
![[Self-balancing binary search tree|Balanced tree]]&lt;br /&gt;
![[Random access list|Random {{nowrap|access list}}]]&lt;br /&gt;
![[Hashed array tree]]&lt;br /&gt;
|-&lt;br /&gt;
|Indexing&lt;br /&gt;
|style=&amp;quot;background:#ffdddd&amp;quot;|Θ(''n'')&lt;br /&gt;
|style=&amp;quot;background:#ddffdd&amp;quot;|Θ(1)&lt;br /&gt;
|style=&amp;quot;background:#ddffdd&amp;quot;|Θ(1)&lt;br /&gt;
|style=&amp;quot;background:#ffffdd&amp;quot;|Θ(log n)&lt;br /&gt;
|style=&amp;quot;background:#ffffdd&amp;quot;|Θ(log n)&amp;lt;ref name=&amp;quot;okasaki&amp;quot;&amp;gt;{{cite journal&lt;br /&gt;
 |title=Purely Functional Random-Access Lists&lt;br /&gt;
 |author=Chris Okasaki&lt;br /&gt;
 |journal=Proceedings of the Seventh International Conference on Functional Programming Languages and Computer Architecture&lt;br /&gt;
 |year=1995&lt;br /&gt;
 |pages=86-95&lt;br /&gt;
 |doi=10.1145/224164.224187&lt;br /&gt;
}}&amp;lt;/ref&amp;gt;&lt;br /&gt;
|style=&amp;quot;background:#ddffdd&amp;quot;|Θ(1)&lt;br /&gt;
|-&lt;br /&gt;
|{{nowrap|Insert/delete}} at beginning&lt;br /&gt;
|style=&amp;quot;background:#ddffdd&amp;quot;|Θ(1)&lt;br /&gt;
|{{n/a}}&lt;br /&gt;
|style=&amp;quot;background:#ffdddd&amp;quot;|Θ(''n'')&lt;br /&gt;
|style=&amp;quot;background:#ffffdd&amp;quot;|Θ(log n)&lt;br /&gt;
|style=&amp;quot;background:#ddffdd&amp;quot;|Θ(1)&lt;br /&gt;
|style=&amp;quot;background:#ffdddd&amp;quot;|Θ(''n'')&lt;br /&gt;
|-&lt;br /&gt;
|{{nowrap|Insert/delete}} at end&lt;br /&gt;
|style=&amp;quot;background:#ddffdd&amp;quot;|Θ(1) when last {{nowrap|element is known}};&amp;lt;br/&amp;gt;Θ(''n'') when last {{nowrap|element is unknown}}&lt;br /&gt;
|{{n/a}}&lt;br /&gt;
|style=&amp;quot;background:#ddffdd&amp;quot;|Θ(1) [[Amortized analysis|amortized]]&lt;br /&gt;
|style=&amp;quot;background:#ffffdd&amp;quot;|Θ(log ''n'')&lt;br /&gt;
|{{n/a}} &amp;lt;ref name=&amp;quot;okasaki&amp;quot;/&amp;gt;&lt;br /&gt;
|style=&amp;quot;background:#ddffdd&amp;quot;|Θ(1) [[Amortized analysis|amortized]]&lt;br /&gt;
|-&lt;br /&gt;
|{{nowrap|Insert/delete}} in middle&lt;br /&gt;
|style=&amp;quot;background:#ffffdd&amp;quot;|search time + {{nowrap|Θ(1)}}&amp;lt;ref&amp;gt;[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&amp;lt;/ref&amp;gt;&amp;lt;ref&amp;gt;[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''&amp;lt;/ref&amp;gt;&lt;br /&gt;
|{{n/a}}&lt;br /&gt;
|style=&amp;quot;background:#ffdddd&amp;quot;|Θ(''n'')&lt;br /&gt;
|style=&amp;quot;background:#ffffdd&amp;quot;|Θ(log ''n'')&lt;br /&gt;
|{{n/a}} &amp;lt;ref name=&amp;quot;okasaki&amp;quot;/&amp;gt;&lt;br /&gt;
|style=&amp;quot;background:#ffdddd&amp;quot;|Θ(''n'')&lt;br /&gt;
|-&lt;br /&gt;
|{{nowrap|Wasted space}} (average)&lt;br /&gt;
|style=&amp;quot;background:#ffdddd&amp;quot;|Θ(''n'')&lt;br /&gt;
|style=&amp;quot;background:#ddffdd&amp;quot;|0&lt;br /&gt;
|style=&amp;quot;background:#ffdddd&amp;quot;|Θ(''n'')&amp;lt;ref name=&amp;quot;brodnik&amp;quot;&amp;gt;{{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}}&amp;lt;/ref&amp;gt;&lt;br /&gt;
|style=&amp;quot;background:#ffdddd&amp;quot;|Θ(''n'')&lt;br /&gt;
|style=&amp;quot;background:#ffdddd&amp;quot;|Θ(''n'')&lt;br /&gt;
|style=&amp;quot;background:#ffffdd&amp;quot;|Θ({{radic|''n''}})&lt;br /&gt;
|}&lt;br /&gt;
&amp;lt;noinclude&amp;gt;{{Template reference list}}&amp;lt;/noinclude&amp;gt;&lt;/div&gt;</summary>
		<author><name>122.111.75.152</name></author>
		
	</entry>
</feed>