Data Structure | Worst Case Complexity |
Notes |
Array |
Insert |
O(1) |
Retrieve |
O(1) |
|
|
Linked List |
Insert at Tail |
O(n) |
Insert at Head |
O(1) |
Retrieve |
O(n) |
|
Note that if new elements are added at the head of the linkedlist then insert becomes a O(1) operation. |
Binary Tree |
Insert |
O(n) |
Retrieve |
O(n) |
|
In worst case, the binary tree becomes a linked-list. |
Dynamic Array |
Insert |
O(1) |
Retrieve |
O(1) |
|
Note by retrieving it is implied we are retrieving from a specific index of the array. |
Stack |
|
There are no complexity trick questions asked for stacks or queues. We only mention them here for completeness. The two data-structures are more important from a last-in last-out (stack) and first in first out (queue) perspective. |
Queue |
Enqueue |
O(1) |
Dequeue |
O(1) |
|
|
Priority Queue (binary heap) |
Insert |
O(lgn) |
Delete |
O(lgn) |
Get Max/Min |
O(1) |
|
|
Hashtable |
Insert |
O(n) |
Retrieve |
O(n) |
|
Be mindful that a hashtable's average case for insertion and retrieval is O(1) |
B-Trees |
Insert |
O(logn) |
Retrieve |
O(logn) |
|
|
Red-Black Trees |
Insert |
O(logn) |
Retrieve |
O(logn) |
|
|