https://www.vigyanwiki.in/index.php?action=history&feed=atom&title=Template%3AList_data_structure_comparison 2026-04-28T06:34:11Z Revision history for this page on the wiki MediaWiki 1.39.3 https://www.vigyanwiki.in/index.php?title=Template:List_data_structure_comparison&diff=58261&oldid=prev 2022-12-31T13:46:26Z

<p>1 revision imported from <a href="https://alpha.indicwiki.in/index.php?title=Template:List_data_structure_comparison" class="extiw" title="alpha:Template:List data structure comparison">alpha:Template:List_data_structure_comparison</a></p> <table style="background-color: #fff; color: #202122;" data-mw="interface"> <tr class="diff-title" lang="en-GB"> <td colspan="1" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td> <td colspan="1" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 19:16, 31 December 2022</td> </tr><tr><td colspan="2" class="diff-notice" lang="en-GB"><div class="mw-diff-empty">(No difference)</div> </td></tr></table>

Indicwiki https://www.vigyanwiki.in/index.php?title=Template:List_data_structure_comparison&diff=58260&oldid=prev 2022-12-19T07:54:30Z

<p>Created page with &quot;{|class=&quot;wikitable&quot; |+ Comparison of list data structures |- ! rowspan=2 | ! rowspan=2 | Peek &lt;br/&gt;(index) ! colspan=3 | Mutate (insert or delete) at … ! rowspan=2 | Excess...&quot;</p> <p><b>New page</b></p><div>{|class=&quot;wikitable&quot;<br /> |+ Comparison of list data structures<br /> |-<br /> ! rowspan=2 |<br /> ! rowspan=2 | Peek &lt;br/&gt;(index)<br /> ! colspan=3 | Mutate (insert or delete) at …<br /> ! rowspan=2 | Excess space, &lt;br/&gt;average<br /> |-<br /> ! Beginning<br /> ! End<br /> ! Middle<br /> |-<br /> | [[Linked list]]<br /> | {{no|Θ(''n'')}}<br /> | {{yes|Θ(1)}}<br /> | {{yes|Θ(1), known end element;&lt;br/&gt;Θ(''n''), unknown end element}}<br /> | {{partial|Peek time + &lt;br/&gt;Θ(1)&lt;ref&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&lt;/ref&gt;&lt;ref&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''&lt;/ref&gt;}}<br /> | {{no|Θ(''n'')}}<br /> |-<br /> | [[Array data structure|Array]]<br /> | {{yes|Θ(1)}}<br /> | {{n/a}}<br /> | {{n/a}}<br /> | {{n/a}}<br /> | {{yes|0}}<br /> |-<br /> | [[Dynamic array]]<br /> | {{yes|Θ(1)}}<br /> | {{no|Θ(''n'')}}<br /> | {{yes|Θ(1) [[amortized analysis|amortized]]}}<br /> | {{no|Θ(''n'')}}<br /> | {{no|Θ(''n'')&lt;ref&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}}&lt;/ref&gt;}}<br /> |-<br /> | [[Self-balancing binary search tree|Balanced tree]]<br /> | {{partial|Θ(log n)}}<br /> | {{partial|Θ(log n)}}<br /> | {{partial|Θ(log ''n'')}}<br /> | {{partial|Θ(log ''n'')}}<br /> | {{no|Θ(''n'')}}<br /> |-<br /> | Random-{{nowrap|access list}}<br /> | {{partial|Θ(log n)&lt;ref name=&quot;okasakiComparison&quot;&gt;{{cite journal<br /> |title=Purely Functional Random-Access Lists<br /> |author=Chris Okasaki<br /> |journal=Proceedings of the Seventh International Conference on Functional Programming Languages and Computer Architecture<br /> |year=1995<br /> |pages=86-95<br /> |doi=10.1145/224164.224187<br /> }}&lt;/ref&gt;}}<br /> | {{yes|Θ(1)}}<br /> | {{n/a}}&lt;ref name=&quot;okasakiComparison&quot;/&gt;<br /> | {{n/a}}&lt;ref name=&quot;okasakiComparison&quot;/&gt;<br /> | {{no|Θ(''n'')}}<br /> |-<br /> | [[Hashed array tree]]<br /> | {{yes|Θ(1)}}<br /> | {{no|Θ(''n'')}}<br /> | {{yes|Θ(1) [[amortized analysis|amortized]]}}<br /> | {{no|Θ(''n'')}}<br /> | {{partial|Θ(√''n'')}}<br /> |}<br /> &lt;noinclude&gt;{{Template reference list}}[[Category:Templates that generate named references]]&lt;/noinclude&gt;</div>

alpha>Sarika