Complexity Analysis of General Data Structures for Common Operations:
|
Linked list |
||||
Indexing |
Θ(n) |
Θ(1) |
Θ(1) |
Θ(log n) |
Θ(log n) |
Insert/delete at beginning |
Θ(1) |
N/A |
Θ(n) |
Θ(log n) |
Θ(1) |
Insert/delete at end |
Θ(1) |
N/A |
Θ(1) amortized |
Θ(log n) |
Θ(log n) updating |
Insert/delete in middle |
search time + |
N/A |
Θ(n) |
Θ(log n) |
Θ(log n) updating |
Wasted space (average) |
Θ(n) |
0 |
Θ(n)[2] |
Θ(n) |
Θ(n) |
Complexity Analysis of Python’s Data Structures for Common Operations:
list
Internally, a list is represented as an array
Operation |
Average Case |
|
Copy |
O(n) |
O(n) |
Append[1] |
O(1) |
O(1) |
Insert |
O(n) |
O(n) |
Get Item |
O(1) |
O(1) |
Set Item |
O(1) |
O(1) |
Delete Item |
O(n) |
O(n) |
Iteration |
O(n) |
O(n) |
Get Slice |
O(k) |
O(k) |
Del Slice |
O(n) |
O(n) |
Set Slice |
O(k+n) |
O(k+n) |
Extend[1] |
O(k) |
O(k) |
O(n log n) |
O(n log n) |
|
Multiply |
O(nk) |
O(nk) |
x in s |
O(n) |
|
min(s), max(s) |
O(n) |
|
Get Length |
O(1) |
O(1) |
collections.deque
A deque (double-ended queue) is represented internally as a doubly linked list
Operation |
Average Case |
Amortized Worst Case |
Copy |
O(n) |
O(n) |
append |
O(1) |
O(1) |
appendleft |
O(1) |
O(1) |
pop |
O(1) |
O(1) |
popleft |
O(1) |
O(1) |
extend |
O(k) |
O(k) |
extendleft |
O(k) |
O(k) |
rotate |
O(k) |
O(k) |
remove |
O(n) |
O(n) |
dict
Operation |
Average Case |
Amortized Worst Case |
Copy[2] |
O(n) |
O(n) |
Get Item |
O(1) |
O(n) |
Set Item[1] |
O(1) |
O(n) |
Delete Item |
O(1) |
O(n) |
Iteration[2] |
O(n) |
O(n) |
Reference: