104

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.

Bhushan
  • 18,329
  • 31
  • 104
  • 137
  • 4
    Time and Space Complexities for all data structures [Big O cheat sheet](http://bigocheatsheet.com/) – Vbp Feb 26 '14 at 16:25
  • 1
    In case someone else steps into this, take a minute to also check this link: http://infotechgems.blogspot.gr/2011/11/java-collections-performance-time.html – vefthym Apr 07 '14 at 08:12
  • Big o Cheatsheet - Data structures and Algorithms with thier complexities https://www.hackerearth.com/practice/notes/big-o-cheatsheet-series-data-structures-and-algorithms-with-thier-complexities-1/ – Amitesh Bharti Feb 19 '22 at 06:52

2 Answers2

286

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 traversing the linkedlist linearly.
  • Deleting: O(1), if done at the head, O(n) if anywhere else since we have to reach that position by traversing 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 traversing 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 traversing 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)
fzbd
  • 477
  • 2
  • 8
Bhushan
  • 18,329
  • 31
  • 104
  • 137
  • 4
    Inserting an element into Array (and by _insert_ I mean adding new element into position, shifting all elements to the right) will take O(n). Same for deletion. Only replacing existent element will take O(n). Also it's possible that you mixed it with adding new element to resizable array (it has amortized O(1) time). – Aivean Sep 23 '14 at 17:23
  • Also please note, that for Doubly-linked list inserting and deleting to both head and tail will take O(1) (you mentioned only head). – Aivean Sep 23 '14 at 17:26
  • And final note, balanced search trees (for example, Red-black tree that is actually used for TreeMap in Java) has guaranteed worst-case time of O(ln n) for all operations. – Aivean Sep 23 '14 at 17:28
  • @Aivean: I am just trying to list standard operations for standard data-structures. For Arrays: Shifting elements while adding/deleting is not a standard operation. Also, replacing existing element takes O(1) using index, not O(n). For Doubly-Linked List: You are right, I am making correction. For Red-Black Trees: Again, you are right. But I have listed just a BST, which need not be balanced. So, I will add new entry for Red-Black Trees. Thanks for the comments! – Bhushan Sep 23 '14 at 19:13
  • @Bhushan Yep, I meant O(1), just a typo. I still can't understand how do you insert or remove element in array in O(1). Because nulling existing element in some position can hardly be considered as removing. – Aivean Sep 23 '14 at 19:25
  • I think you should distinguish arrays from `ArrayList`. If you do that, insert/remove is not supported for arrays, only replace (including by a `null` value but it is not a remove). Also, this answer is not java-oriented although the question was. For example, java's `LinkedList` actually implements `Deque`. – Didier L Sep 23 '14 at 19:41
  • For ArrayList remove (if not last element) is O(n). – Aivean Sep 23 '14 at 22:42
  • What are the complexities for `SET`? – Suhail Gupta Jan 17 '17 at 14:11
  • 1
    @SuhailGupta: Complexity for Set is already given as the last point. – Bhushan Jan 17 '17 at 18:53
  • why O(1) for stack size ? do you mean memory complexity ? or cpu complexity of getting the size ? if thats memory complexity its weird because arraylist and queue both have O(n) memory complexity ... – Amir Ziarati Jun 18 '18 at 09:32
  • Can You please add time complexity for Vector class? – Kumaresan Perumal Aug 23 '22 at 07:27
0

Baeldung pointed out some time complexities for the ArrayList, LinkedList, and CopyOnWriteArrayList here: https://www.baeldung.com/java-collections-complexity and for Map implementations here: https://www.baeldung.com/java-hashmap

He also added benchmarks to highlight differences among the implementations.

Danilo Teodoro
  • 733
  • 5
  • 5