What are the time complexities of various data structures?

Question

I am trying to list time complexities of operations of common data structures like Arrays, Binary Search Tree, Heap, Linked List, etc. and especially I am referring to Java. They are very common, but I guess some of us are not 100% confident about the exact answer. Any help, especially references, is greatly appreciated.

E.g. For singly linked list: Changing an internal element is O(1). How can you do it? You HAVE to search the element before changing it. Also, for the Vector, adding an internal element is given as O(n). But why can't we do it in amortized constant time using the index? Please correct me if I am missing something.

I am posting my findings/guesses as the first answer.

Answer 1

Arrays

• Set, Check element at a particular index: O(1)
• Searching: O(n) if array is unsorted and O(log n) if array is sorted and something like a binary search is used,
• As pointed out by Aivean, there is no Delete operation available on Arrays. We can symbolically delete an element by setting it to some specific value, e.g. -1, 0, etc. depending on our requirements
• Similarly, Insert for arrays is basically Set as mentioned in the beginning

ArrayList:

• Add: Amortized O(1)
• Remove: O(n)
• Contains: O(n)
• Size: O(1)

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 or tail, 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 or tail, 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)

Red-Black Tree:

• Insert, delete and search: Average case: O(log n), Worst Case: O(log n)

Heap/PriorityQueue (min/max):

• Find Min/Find Max: O(1)
• Insert: O(log n)
• Delete Min/Delete Max: O(log n)
• Extract Min/Extract 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)