Difference between revisions of "Template:List data structure comparison"
Jump to navigation
Jump to search
imported>Dcoetzee (Link linked list so it can be used in all three articles) |
imported>Dcoetzee (Add balanced tree column from array data structure) |
||
| 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]] | + | ! !![[Linked list]]!![[Array data structure|Array]]!![[Dynamic array|Dynamic<br />array]]!![[Self-balancing binary search tree|Balanced<br />tree]] |
|- | |- | ||
|Indexing | |Indexing | ||
| Line 7: | Line 7: | ||
|style="background:#ddffdd"|Θ(1) | |style="background:#ddffdd"|Θ(1) | ||
|style="background:#ddffdd"|Θ(1) | |style="background:#ddffdd"|Θ(1) | ||
| + | |style="background:#ffffdd"|Θ(log n) | ||
|- | |- | ||
|Insertion/deletion at beginning | |Insertion/deletion at beginning | ||
| Line 12: | Line 13: | ||
|{{n/a}} | |{{n/a}} | ||
|style="background:#ffdddd"|Θ(''n'') | |style="background:#ffdddd"|Θ(''n'') | ||
| + | |style="background:#ffffdd"|Θ(log n) | ||
|- | |- | ||
|Insertion/deletion at end | |Insertion/deletion at end | ||
| Line 17: | Line 19: | ||
|{{n/a}} | |{{n/a}} | ||
|style="background:#ddffdd"|Θ(1) [[Amortized analysis|amortized]] | |style="background:#ddffdd"|Θ(1) [[Amortized analysis|amortized]] | ||
| + | |style="background:#ffffdd"|Θ(log n) | ||
|- | |- | ||
|Insertion/deletion in middle | |Insertion/deletion in middle | ||
| Line 22: | Line 25: | ||
|{{n/a}} | |{{n/a}} | ||
|style="background:#ffdddd"|Θ(''n'') | |style="background:#ffdddd"|Θ(''n'') | ||
| + | |style="background:#ffffdd"|Θ(log n) | ||
|- | |- | ||
|Wasted space (average) | |Wasted space (average) | ||
|style="background:#ffdddd"|Θ(''n'') | |style="background:#ffdddd"|Θ(''n'') | ||
|style="background:#ddffdd"|0 | |style="background:#ddffdd"|0 | ||
| + | |style="background:#ffdddd"|Θ(''n'') | ||
|style="background:#ffdddd"|Θ(''n'') | |style="background:#ffdddd"|Θ(''n'') | ||
|} | |} | ||
</div> | </div> | ||
Revision as of 12:46, 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) |
- ↑ Gerald Kruse. CS 240 Lecture Notes: Linked Lists Plus: Complexity Trade-offs. Juniata College. Spring 2008.