How is LinkedList's add(int, E) of O(1) complexity?
Solution 1
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.
Solution 2
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 nth index = O(n)
Solution 3
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 ;)
Solution 4
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.
wchargin
Updated on August 08, 2022Comments
-
wchargin almost 2 years
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
. Theadd(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 theentry(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 thusadd(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?