How is LinkedList's add(int, E) of O(1) complexity?
big-o, java, linked-list, time-complexity
Solution
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.
Problem
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?