Difference between revisions of "Template:List data structure comparison"

From blackwiki
Jump to navigation Jump to search
imported>Dcoetzee
(Add balanced tree column from array data structure)
imported>Salamurai
(<noinclude>{{Template reference list}}</noinclude>)
Line 34: Line 34:
 
|}
 
|}
 
</div>
 
</div>
 +
<noinclude>{{Template reference list}}</noinclude>

Revision as of 17:38, 19 June 2011

  Linked list Array Dynamic
array
Balanced
tree
Indexing Θ(n) Θ(1) Θ(1) Θ(log n)
Insertion/deletion at beginning Θ(1) N/A Θ(n) Θ(log n)
Insertion/deletion at end Θ(1) N/A Θ(1) amortized Θ(log n)
Insertion/deletion in middle search time +
Θ(1)[1]
N/A Θ(n) Θ(log n)
Wasted space (average) Θ(n) 0 Θ(n) Θ(n)

References

  1. Gerald Kruse. CS 240 Lecture Notes: Linked Lists Plus: Complexity Trade-offs. Juniata College. Spring 2008.