Why is inserting in the middle of a linked list O(1)?

Question

According to the Wikipedia article on linked lists, inserting in the middle of a linked list is considered O(1). I would think it would be O(n). Wouldn't you need to locate the node which could be near the end of the list?

Does this analysis not account for the finding of the node operation (though it is required) and just the insertion itself?

EDIT:

Linked lists have several advantages over arrays. Insertion of an element at a specific point of a list is a constant-time operation, whereas insertion in an array may require moving half of the elements, or more.

The above statement is a little misleading to me. Correct me if I'm wrong, but I think the conclusion should be:

Arrays:

• Finding the point of insertion/deletion O(1)
• Performing the insertion/deletion O(n)

Linked Lists:

• Finding the point of insertion/deletion O(n)
• Performing the insertion/deletion O(1)

I think the only time you wouldn't have to find the position is if you kept some sort of pointer to it (as with the head and the tail in some cases). So we can't flatly say that linked lists always beat arrays for insert/delete options.

Answer 1

Because it does not involve any looping.

Inserting is like:

• insert element
• link to previous
• link to next
• done

this is constant time in any case.

Consequently, inserting n elements one after the other is O(n).

Answer 2

You are correct, the article considers "Indexing" as a separate operation. So insertion is itself O(1), but getting to that middle node is O(n).

Answer 3

Inserting is O(1) once you know where you're going to put it.

Answer 4

No, when you decide that you want to insert, it's assumed you are already in the middle of iterating through the list.

Operations on Linked Lists are often done in such a way that they aren't really treated as a generic "list", but as a collection of nodes--think of the node itself as the iterator for your main loop. So as you're poking through the list you notice as part of your business logic that a new node needs to be added (or an old one deleted) and you do so. You may add 50 nodes in a single iteration.

Edit: Man, you type a second paragraph and all of a sudden instead of being the first responder you're the 5th saying the same thing as the first 4!

Answer 5

Does this analysis not account for the finding of the node operation (though it is required) and just the insertion itself?

You got it. Insertion at a given point assumes that you already hold a pointer to the item that you want to insert after:

InsertItem(item * newItem, item * afterItem)

Answer 6

The insertion itself is O(1). Node finding is O(n).

Answer 7

The article is about comparing arrays with lists. Finding the insert position for both arrays and lists is O(N), so the article ignores it.

Answer 8

O(1) is depending of that fact that you have a item where you will insert the new item. (before or after). If you don´t, it´s O(n) becuase you must find that item.

Answer 9

No, it does not account for searching. But if you already have hold of a pointer to an item in the middle of the list, inserting at that point is O(1).

If you have to search for it, you'd have to add on the time for searching, which should be O(n).

Answer 10

I think it's just a case of what you choose to count for the O() notation. In the case of inserting the normal operation to count is copy operations. With an array, inserting in the middle involves copying everything above the location up in memory. With a linked list, this becomes setting two pointers. You need to find the location no matter what to insert.

Answer 11

For purposes of comparing with an array, which is what that chart shows, it's O(1) because you don't have to move all the items after the new node.

So yes, they are assuming that you already have the pointer to that node, or that getting the pointer is trivial. In other words, the problem is stated: "given node at X, what is the code to insert after this node?" You get to start at the insert point.

Answer 12

If you have the reference of the node to insert after the operation is O(1) for a linked list.
For an array it is still O(n) since you have to move all consequtive nodes.

Answer 13

The most common cases are probably inserting at the begining or at the end of the list (and the ends of the list might take no time to find).

Contrast that with inserting items at the begining or the end of an array (which requires resizing the array if it's at the end, or resizing and moving all the elements if it's at the begining).

Answer 14

Insertion into a linked list is different than iterating across it. You aren't locating the item, you are resetting pointers to put the item in there. It doesn't matter if it is going to be inserted near the front end or near the end, the insertion still involves pointers being reassigned. It'll depend on how it was implemented, of course, but that is the strength of lists - you can insert easily. Accessing via index is where an array shines. For a list, however, it'll typically be O(n) to find the nth item. At least that's what I remember from school.