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

Question

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, and O(1) access at the front (and optionally back) positions as well as O(1) next element access. Random access has O(N) complexity and is usually unimplemented.

^{(emphasis mine)}

I was surprised to read this – how can the list insert at a random index with a lower complexity than simply reading that index?

So I looked at the source code for java.util.LinkedList. The add(int, E) method is:

public void add(int index, E element) { addBefore(element, (index==size ? header : entry(index))); }

The addBefore(E, Entry<E> method is simply pointer reassignment, but there's also the entry(int) method:

if (index < 0 || index >= size) throw new IndexOutOfBoundsException("Index: "+index+ ", Size: "+size); Entry<E> e = header; if (index < (size >> 1)) { for (int i = 0; i <= index; i++) e = e.next; } else { for (int i = size; i > index; i--) e = e.previous; } return e; }

Even with the half-size optimization, the for loop in here (one or the other) seems to me a dead giveaway that this method (and thus add(int, E)) operates in a minimum worst-case scenario of O(n) time, and certainly not constant time.

What am I missing? Am I misunderstanding the big-O notation?

Thanakron Tandavas · Accepted Answer · 2013-03-31 17:40:27Z

28

This is because the article that you are reading considered "getting to that index" as a separate operation. The article assumes that you are already at the index you wish to perform add(int, E).

To conclude:

Insert or Remove operation = O(1)

Finding node at n^th index = O(n)

answered Mar 31, 2013 at 17:40

Thanakron Tandavas

5,7035 gold badges31 silver badges41 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

João Matos Over a year ago

According to this answer stackoverflow.com/a/18679284/4828060, finding a node at nth index is O(1). Not sure yet which of the answers I agree with :|

harperska Over a year ago

@JoãoMatos, that particular answer was to a question asking about the complexity of the addLast() method. As java's LinkedList is a doubly linked list maintaining pointers to the first and last element, addLast() is O(1). Looking up a node at an arbitrary index is still O(n).

thejh · Accepted Answer · 2013-03-31 17:40:54Z

Well, they do support constant-time inserts at arbitrary positions – but only if you happen to have a pointer to the list entry after which or in front of which you want to insert something. Of course, this won't work if you just have the index, but that's not what you usually do in optimized code.

In Java, you can do that, too, but only using a list iterator.

This property of linked lists is their biggest advantage compared to arraylists or so – for example, if you want to remove a user from the user list of a chatroom, you can store a pointer to the user's position in the userlist in the user so that, when he wants to leave the room, that can be implemented as a O(1) operation.

In other words: LinkedList<E>.add(int, E) is not O(1), but ListIterator<E>.add is (for iterators that come from a LinkedList).

Mik378 · Accepted Answer · 2013-03-31 17:42:35Z

The operation of linking the new node to any node is O(1) but the operation of finding (helps to the loop) the concerned index is definitely O(n).

There is no magic ;)

NPE · Accepted Answer · 2013-03-31 17:42:36Z

The wiki page you quote says:

O(1) insert and removal at any position

Then you ask:

I was surprised to read this – how can the list insert at a random index

Herein lies the confusion: the terms position and index are not being used to mean the same thing. The wiki talks about an iterator or a pointer, not about an index.

Although position is a bit ambiguous... and "insert ... at" suggests the index interpretation. I've suggested a tag wiki edit to clarify, what do you think about it?
@thejh: I personally think it's pretty clear. However, given that at least one person found it confusing, I don't see what harm a little clarification could do.

Collectives™ on Stack Overflow

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

4 Answers 4

2 Comments

1 Comment

Comments

2 Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

2 Comments

1 Comment

Comments

2 Comments

Linked

Related