Arrays
- Inserting: O(1) for all the positions, since it is done with indexes
- Deleting: O(n) if we have to find the element, O(1) if we know position of the element
- Searching: O(n) if array is unsorted and O(log n) if array is sorted and something like a binary search is used.
Linked List:
- Inserting: O(1), if done at the head, O(n) if anywhere else since we have to reach that position by traveseing the linkedlist linearly.
- Deleting: O(1), if done at the head, O(n) if anywhere else since we have to reach that position by traveseing the linkedlist linearly.
- Searching: O(n)
Doubly-Linked List:
- Inserting: O(1), if done at the head, O(n) if anywhere else since we have to reach that position by traveseing the linkedlist linearly.
- Deleting: O(1), if done at the head, O(n) if anywhere else since we have to reach that position by traveseing the linkedlist linearly.
- Searching: O(n)
Stack:
- Push: O(1)
- Pop: O(1)
- Top: O(1)
- Search (Something like lookup, as a special operation): O(n) (I guess so)
Queue/Deque/Circular Queue:
- Insert: O(1)
- Remove: O(1)
- Size: O(1)
Binary Search Tree:
- Insert, delete and search: Average case: O(log n), Worst Case: O(n)
Heap/PriorityQueue (min/max):
- findMin/findMax: O(1)
- insert: O(log n)
- deleteMin/Max: O(log n)
- lookup, delete (if at all provided): O(n), we will have to scan all the elements as they are not ordered like BST
HashMap/Hashtable/HashSet:
- Insert/Delete: O(1) amortized
- Re-size/hash: O(n)
- Contains: O(1)
Special thanks to Stackoverflow!
No comments:
Post a Comment