The Fake Geek's blog: Time complexity of different data structures

The Fake Geek's blog: Time complexity of different data structures

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)

Read full article from The Fake Geek's blog: Time complexity of different data structures