# Does anyone know of any reliable summary of the complexity of common data structure operations?

It seems that the most popular source on the internet on this topic is https://www.bigocheatsheet.com/:

Wikipedia and basically any other similar table I find on the internet copy this one.

There are some things that without a brief explanation are very difficult for me to understand or are a bit confusing. For example, as a user mentions here, comparing the access time of BST vs array can be "unfair... since in a BST, 'Access' also gives you the i-th smallest element, whereas in a simple array you get only some element".

I wonder if anyone knows of a good source that concisely explains the differences in complexity of those operations for those structures, without me having to read 14 lengthy wikipedia articles.

On the other hand, there is the problem that now I don't trust that sources either, since with my little knowledge on the subject I have found an error. I mean, Insertion and deletion in Singly-Linked List is not O(1) but O(n).

I would appreciate if someone can give me a hand.

• The link you provided ragarding the insertion and deletion in a singly-linked list is not stating that this operation is O(n). It clearly says that it's O(1), but if you do not have access to the element preceeding the one you wish to delete, you first have to locate it, which would be an O(n) operation. Certainly insertion and deletion in linked-lists is O(1). The question is whether you already have access to that element. This is a separate concern that generally should not be taken into account when specyfing time complexity in such details you seem to seek. Commented Aug 5, 2022 at 16:42
• We are talking about removing a node that we have access to. In the case of singly-linked list it is O(N) because although you can access the node to remove in O(1), then you need to search for the previous node in O(N). Commented Aug 5, 2022 at 20:01