Difference between revisions of "Template:List data structure comparison"
Jump to navigation
Jump to search
imported>Dcoetzee (Create from Linked list, http://en.wikipedia.org/w/index.php?title=Linked_list&oldid=434305999) |
imported>Dcoetzee (Link linked list so it can be used in all three articles) |
||
| Line 1: | Line 1: | ||
<div class=tright align=right> | <div class=tright align=right> | ||
{|class="wikitable" | {|class="wikitable" | ||
| − | ! !! | + | ! !![[Linked list]]!![[Array data structure|Array]]!![[Dynamic array|Dynamic<br />array]] |
|- | |- | ||
|Indexing | |Indexing | ||
Revision as of 12:42, 19 June 2011
| Linked list | Array | Dynamic array | |
|---|---|---|---|
| Indexing | Θ(n) | Θ(1) | Θ(1) |
| Insertion/deletion at beginning | Θ(1) | N/A | Θ(n) |
| Insertion/deletion at end | Θ(1) | N/A | Θ(1) amortized |
| Insertion/deletion in middle | search time + Θ(1)[1] |
N/A | Θ(n) |
| Wasted space (average) | Θ(n) | 0 | Θ(n) |
- ↑ Gerald Kruse. CS 240 Lecture Notes: Linked Lists Plus: Complexity Trade-offs. Juniata College. Spring 2008.