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

linked-list big-o
Rob Sobers picture Rob Sobers · May 8, 2009 · Viewed 53.1k times · Source

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

CookieOfFortune picture CookieOfFortune · May 8, 2009

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).

Related questions

How is LinkedList's add(int, E) of O(1) complexity?

From the linked-list tag wiki excerpt: A linked list is a data structure in which the elements contain references to the next (and optionally the previous) element. Linked lists offer O(1) insert and removal at any position, O(1) list concatenation, …

Read More
How is it possible to do binary search on a singly-linked list in O(n) time?

This earlier question talks about doing binary search over a doubly-linked list in O(n) time. The algorithm in that answer work as follows: Go to the middle of the list to do the first comparison. If it's equal to …

Read More
When to use LinkedList over ArrayList in Java?

I've always been one to simply use: List<String> names = new ArrayList<>(); I use the interface as the type name for portability, so that when I ask questions such as these I can rework my code. …

Read More