Answers.Body: <p>I worry that you are asking for learning and insight without putting in the work that it requires. Having a &quot;quick hit&quot; explanation of some phenomenon doesn't mean that you actually understand it. Whatever is wrong with reading fourteen wikipedia pages? What is wrong with finding a good book on algorithms and data structures and doing a lot of the exercises in it? That is how learning is attained.</p>
  <p>Shallow knowledge won't take you very far.</p>
  <p>There is a book I like a lot, though it is old and now (sometimes) expensive unless you can find a used copy (or a library copy). <a href="https://rads.stackoverflow.com/amzn/click/com/038790641X" rel="nofollow noreferrer" rel="nofollow noreferrer">The Science of Programming: David Gries</a>. David was once a mentor of mine and I learned a huge amount from his work. It is actually a book about programming, as the name implies, but it has a lot to say about data structures and efficiency of algorithms.</p>
  <p>The big idea in the book is programming with pre and post-conditions and program invariants. Big, big idea.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-08-05T20:04:09.757Z
Answers.Text: Certainly a table is not going to save me the time of reading all the data structures; I just wanted to know if there was a well-done summary or table that would serve as a starting point. Maybe I didn't express myself well. Thanks for recommending that book, I'll check it out!
Answers.UserDisplayName: GermanJablo
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-08-05T19:02:08.900Z
Answers.LastActivityDate: 2022-08-05T19:21:39.537Z
Answers.LastEditDate: 2022-08-05T19:21:39.537Z
Answers.UserDisplayName: Buffy
Body: <p>It seems that the most popular source on the internet on this topic is <a href="https://www.bigocheatsheet.com/" rel="nofollow noreferrer">https://www.bigocheatsheet.com/</a>:
  <a href="https://i.sstatic.net/nef2h.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/nef2h.png" alt="enter image description here" /></a></p>
  <p><a href="https://en.wikipedia.org/wiki/Best,_worst_and_average_case#Sorting_algorithms" rel="nofollow noreferrer">Wikipedia</a> and basically any other similar table I find on the internet copy this one.</p>
  <p>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 <a href="https://cs.stackexchange.com/questions/82669/why-is-big-o-not-defined-here-for-a-hash-table">mentions here</a>, comparing the access time of BST vs array can be &quot;unfair... since in a BST, 'Access' also gives you the i-th smallest element, whereas in a simple array you get only some element&quot;.</p>
  <p>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.</p>
  <p>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, <a href="https://stackoverflow.com/questions/56206535/what-is-the-time-complexity-for-deletion-in-singly-and-doubly-linked-lists">Insertion and deletion in Singly-Linked List is not O(1) but O(n)</a>.</p>
  <p>I would appreciate if someone can give me a hand.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-08-05T16:42:40.583Z
Comments.Text: 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.
Comments.UserDisplayName: Fureeish
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-08-05T20:01:44.933Z
Comments.Text: 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).
Comments.UserDisplayName: GermanJablo
Tags: <resource-request><algorithms><data-structure><complexity-theory>
Title: Does anyone know of any reliable summary of the complexity of common data structure operations?
ThreadText: # Does anyone know of any reliable summary of the complexity of common data structure operations?
  
  (Asked by: username_0 on 2022-08-05)
  
  It seems that the most popular source on the internet on this topic is <https://www.bigocheatsheet.com/>:
  [![enter image description here](https://i.sstatic.net/nef2h.png)](https://i.sstatic.net/nef2h.png)
  
  [Wikipedia](https://en.wikipedia.org/wiki/Best,_worst_and_average_case#Sorting_algorithms) 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](https://cs.stackexchange.com/questions/82669/why-is-big-o-not-defined-here-for-a-hash-table), 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)](https://stackoverflow.com/questions/56206535/what-is-the-time-complexity-for-deletion-in-singly-and-doubly-linked-lists).
  
  I would appreciate if someone can give me a hand.
  
  **Tags:** resource-request, algorithms, data-structure, complexity-theory
  
  > **Comments:**
  > **username_1**: 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.  
  > **username_0**: 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).  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2022-08-05. Score: 1
  
  I worry that you are asking for learning and insight without putting in the work that it requires. Having a "quick hit" explanation of some phenomenon doesn't mean that you actually understand it. Whatever is wrong with reading fourteen wikipedia pages? What is wrong with finding a good book on algorithms and data structures and doing a lot of the exercises in it? That is how learning is attained.
  
  Shallow knowledge won't take you very far.
  
  There is a book I like a lot, though it is old and now (sometimes) expensive unless you can find a used copy (or a library copy). [The Science of Programming: David Gries](https://rads.stackoverflow.com/amzn/click/com/038790641X). David was once a mentor of mine and I learned a huge amount from his work. It is actually a book about programming, as the name implies, but it has a lot to say about data structures and efficiency of algorithms.
  
  The big idea in the book is programming with pre and post-conditions and program invariants. Big, big idea.
  
  > **Comments:**
  > **username_0**: Certainly a table is not going to save me the time of reading all the data structures; I just wanted to know if there was a well-done summary or table that would serve as a starting point. Maybe I didn't express myself well. Thanks for recommending that book, I'll check it out!  
  
  ---
  
  