https://blackwiki.org/api.php?action=feedcontributions&feedformat=atom&user=91.213.255.7&* blackwiki - User contributions [en] 2026-08-18T05:02:48Z User contributions MediaWiki 1.34.2 https://blackwiki.org/index.php?title=Template:List_data_structure_comparison&diff=7086891 Template:List data structure comparison 2011-10-31T05:10:31Z <p>91.213.255.7: link was badly done</p> <hr /> <div>&lt;div class=tright align=right&gt;<br /> {|class=&quot;wikitable&quot;<br /> !&amp;nbsp;!![[Linked list]]!![[Array data structure|Array]]!![[Dynamic array|Dynamic&lt;br /&gt;array]]!![[Self-balancing binary search tree|Balanced&lt;br /&gt;tree]]!![[Random access list|Random access&lt;br /&gt;list]]<br /> |-<br /> |Indexing<br /> |style=&quot;background:#ffdddd&quot;|Θ(''n'')<br /> |style=&quot;background:#ddffdd&quot;|Θ(1)<br /> |style=&quot;background:#ddffdd&quot;|Θ(1)<br /> |style=&quot;background:#ffffdd&quot;|Θ(log n)<br /> |style=&quot;background:#ffffdd&quot;|Θ(log n)<br /> |-<br /> |Insert/delete at beginning<br /> |style=&quot;background:#ddffdd&quot;|Θ(1)<br /> |{{n/a}}<br /> |style=&quot;background:#ffdddd&quot;|Θ(''n'')<br /> |style=&quot;background:#ffffdd&quot;|Θ(log n)<br /> |style=&quot;background:#ddffdd&quot;|Θ(1)<br /> |-<br /> |Insert/delete at end<br /> |style=&quot;background:#ddffdd&quot;|Θ(1)<br /> |{{n/a}}<br /> |style=&quot;background:#ddffdd&quot;|Θ(1) [[Amortized analysis|amortized]]<br /> |style=&quot;background:#ffffdd&quot;|Θ(log n)<br /> |style=&quot;background:#ffffdd&quot;|Θ(log n) updating<br /> |-<br /> |Insert/delete in middle<br /> |style=&quot;background:#ddffdd&quot;|search time +&lt;br/&gt;Θ(1)&lt;ref&gt;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.&lt;/ref&gt;<br /> |{{n/a}}<br /> |style=&quot;background:#ffdddd&quot;|Θ(''n'')<br /> |style=&quot;background:#ffffdd&quot;|Θ(log n)<br /> |style=&quot;background:#ffffdd&quot;|Θ(log n) updating<br /> |-<br /> |Wasted space (average)<br /> |style=&quot;background:#ffdddd&quot;|Θ(''n'')<br /> |style=&quot;background:#ddffdd&quot;|0<br /> |style=&quot;background:#ffdddd&quot;|Θ(''n'')&lt;ref name=&quot;brodnik&quot;&gt;{{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}}&lt;/ref&gt;<br /> |style=&quot;background:#ffdddd&quot;|Θ(''n'')<br /> |style=&quot;background:#ffdddd&quot;|Θ(''n'')<br /> |}<br /> &lt;/div&gt;<br /> &lt;noinclude&gt;{{Template reference list}}&lt;/noinclude&gt;</div> 91.213.255.7 https://blackwiki.org/index.php?title=Template:List_data_structure_comparison&diff=7086890 Template:List data structure comparison 2011-10-31T05:09:52Z <p>91.213.255.7: random access list</p> <hr /> <div>&lt;div class=tright align=right&gt;<br /> {|class=&quot;wikitable&quot;<br /> !&amp;nbsp;!![[Linked list]]!![[Array data structure|Array]]!![[Dynamic array|Dynamic&lt;br /&gt;array]]!![[Self-balancing binary search tree|Balanced&lt;br /&gt;tree]]!![[Random access&lt;br /&gt; list]]<br /> |-<br /> |Indexing<br /> |style=&quot;background:#ffdddd&quot;|Θ(''n'')<br /> |style=&quot;background:#ddffdd&quot;|Θ(1)<br /> |style=&quot;background:#ddffdd&quot;|Θ(1)<br /> |style=&quot;background:#ffffdd&quot;|Θ(log n)<br /> |style=&quot;background:#ffffdd&quot;|Θ(log n)<br /> |-<br /> |Insert/delete at beginning<br /> |style=&quot;background:#ddffdd&quot;|Θ(1)<br /> |{{n/a}}<br /> |style=&quot;background:#ffdddd&quot;|Θ(''n'')<br /> |style=&quot;background:#ffffdd&quot;|Θ(log n)<br /> |style=&quot;background:#ddffdd&quot;|Θ(1)<br /> |-<br /> |Insert/delete at end<br /> |style=&quot;background:#ddffdd&quot;|Θ(1)<br /> |{{n/a}}<br /> |style=&quot;background:#ddffdd&quot;|Θ(1) [[Amortized analysis|amortized]]<br /> |style=&quot;background:#ffffdd&quot;|Θ(log n)<br /> |style=&quot;background:#ffffdd&quot;|Θ(log n) updating<br /> |-<br /> |Insert/delete in middle<br /> |style=&quot;background:#ddffdd&quot;|search time +&lt;br/&gt;Θ(1)&lt;ref&gt;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.&lt;/ref&gt;<br /> |{{n/a}}<br /> |style=&quot;background:#ffdddd&quot;|Θ(''n'')<br /> |style=&quot;background:#ffffdd&quot;|Θ(log n)<br /> |style=&quot;background:#ffffdd&quot;|Θ(log n) updating<br /> |-<br /> |Wasted space (average)<br /> |style=&quot;background:#ffdddd&quot;|Θ(''n'')<br /> |style=&quot;background:#ddffdd&quot;|0<br /> |style=&quot;background:#ffdddd&quot;|Θ(''n'')&lt;ref name=&quot;brodnik&quot;&gt;{{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}}&lt;/ref&gt;<br /> |style=&quot;background:#ffdddd&quot;|Θ(''n'')<br /> |style=&quot;background:#ffdddd&quot;|Θ(''n'')<br /> |}<br /> &lt;/div&gt;<br /> &lt;noinclude&gt;{{Template reference list}}&lt;/noinclude&gt;</div> 91.213.255.7