3
$\begingroup$

I thought this would be a very simple O(n) b.c. you can do the insert any where with in the list.

The longer the list, the longer it will take on average to do the insert.

However according to bigocheatsheet it is O(1) or has no dependency on the size of the list.

What is wrong here?

| cite | improve this question | |
$\endgroup$
  • 2
    $\begingroup$ Insertion != ordered insertion. That said, the cheat sheet does seem to be inconsistent with what the operations mean. You should contact the author. $\endgroup$ – Raphael♦ Oct 20 '15 at 18:58
  • $\begingroup$ @Raphael, you certainly can insert in constant time at the beginning of the list. $\endgroup$ – vonbrand Oct 20 '15 at 19:55
  • 1
    $\begingroup$ @vonbrand Right. Also anywhere, if you have a pointer to a neighbour. $\endgroup$ – Raphael♦ Oct 20 '15 at 20:05
6
$\begingroup$

Either if you want to insert at the end of the list or at the beginning of the list, you're going to have $O(1)$ Complexity for that and $O(1)$ space. If you want to insert at the beginning of the list, you just make the new list head the node you want to insert, and link it to the previous list head. If you want to insert at the end of the list, you can also hold the end of the list as a pointer and insert a new node after it. If you want to insert in an arbitrary place in the list, then linearly going there is going to be the best you can do ( to my knowledge ). Statistically you'll have to go through $(n+1)/2 $ nodes to get through yours.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ So the issue was that the chart on the link I posted did not specify. For time complexity it is O(1) for inserting at the beginning or end and O(n) for inserting at some arbitrary point in between. $\endgroup$ – cade galt Oct 9 '15 at 17:24
  • $\begingroup$ same question addressed here - stackoverflow.com/questions/840648/… $\endgroup$ – Abhi Jan 24 at 11:16
4
$\begingroup$

If you have no additional requirements on the contents of the list, you can just insert the item at the head, which is O(1).

If you do (e.g. the list must be kept sorted or deduplicated), insertion is more expensive.

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

https://www.bigocheatsheet.com considering finding (Access) the position of the element before insert as separate operation.

Array:

  • Access - O(1) // we can get the element by index directly
  • Insertion - O(n) // in the worst case we need to resize the array to have a space for the new element

Linked list:

  • Access - O(n) // we need to reach the element
  • Insertion - O(1) // we need to just link the new element with the next and previous
| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.