User:Xionbox/Algorithms
 | This user page is actively undergoing a major edit for a little while. To help avoid edit conflicts, please do not edit this page while this message is displayed. This page was last edited at 09:06, 11 July 2011 (UTC) (14 years ago) – this estimate is cached, . Please remove this template if this page hasn't been edited for a significant time. If you are the editor who added this template, please be sure to remove it or replace it with {{Under construction}} between editing sessions. |
Data structures
| Linked list | Array | Dynamic array |
Balanced tree | |
|---|---|---|---|---|
| Search | Θ(n) | Θ(1) | Θ(1) | Θ(log n) |
| Insert/delete at beginning | Θ(1) | — | Θ(n) | Θ(log n) |
| Insert/delete at end | Θ(1) | — | Θ(1) amortized | Θ(log n) |
| Insert/delete in middle | search time + Θ(1) |
— | Θ(n) | Θ(log n) |
| Wasted space (average) | Θ(n) | 0 | Θ(n) | Θ(n) |