Java: Inserting into LinkedList efficiently

Question

I am optimizing an implementation of a sorted LinkedList.

To insert an element I traverse the list and compare each element until I have the correct index, and then break loop and insert.

I would like to know if there is any other way that I can insert the element at the same time as traversing the list to reduce the insert from O(n + (n capped at size()/2)) to O(n).

A ListIterator is almost what Im after because of its add() method, but unfortunately in the case where there are elements in the list equal to the insert, the insert has to be placed after them in the list. To implement this ListIterator needs a peek() which it doesnt have.

edit: I have my answer, but will add this anyway since a lot of people havent understood correctly: I am searching for an insertion point AND inserting, which combined is higher than O(n)

• Alexander: Why don't you use a Multiset?
• Thomas: I don't get why iterating over the list and inserting after the last element that is less or equal to the one being inserted would have a complexity of more than O(n). In a linked list it's basically just iterating until you found the insert point (which is O(n)) and then insert at that point (which is O(1)).
• Thomas: Additionally: why don't you use a balanced binary tree instead of a sorted linked list? This should reduce the insert cost to O(log(n)) (the cost for searching the insert point).
• Numeron: @Thomas Because I iterate over the list to find the index, and the LinkedList.insert(index, element) iterates over the list to insert.
• user207421: Your statement 'optimizing a sorted LinkedList implementation' contains at least two internal contradictions.

Answer 1

You may consider a skip list, which is implemented using multiple linked lists at varying granularity. E.g. the linked list at level 0 contains all items, level 1 only links to every 2nd item on average, level 2 to only every 4th item on average, etc.... Searching starts from the top level and gradually descends to lower levels until it finds an exact match. This logic is similar to a binary search. Thus search and insertion is an O(log n) operation.

A concrete example in the Java class library is ConcurrentSkipListSet (although it may not be directly usable for you here).

Answer 2

I'd favor Péter Török suggestion, but I'd still like to add something for the iterator approach:

Note that ListIterator provides a previous() method to iterate through the list backwards. Thus first iterate until you find the first element that is greater and then go to the previous element and call add(...). If you hit the end, i.e. all elements are smaller, then just call add(...) without going back.

Answer 3

I have my answer, but will add this anyway since a lot of people havent understood correctly: I am searching for an insertion point AND inserting, which combined is higher than O(n).

Your require to maintain a collection of (possibly) non-unique elements that can iterated in an order given by a ordering function. This can be achieved in a variety of ways. (In the following I use "total insertion cost" to mean the cost of inserting a number (N) of elements into an initially empty data structure.)

• A singly or doubly linked list offers O(N^2) total insertion cost (whether or not you combine the steps of finding the position and doing the insertion!), and O(N) iteration cost.

• A TreeSet offers O(NlogN) total insertion cost and O(N) iteration cost. But has the restriction of no duplicates.

• A tree-based multiset (e.g. TreeMultiset) has the same complexity as a TreeSet, but allows duplicates.

• A skip-list data structure also has the same complexity as the previous two.

Clearly, the complexity measures say that a data structure that uses a linked list performs the worst as N gets large. For this particular group of requirements, a well-implemented tree-based multiset is probably the best, assuming there is only one thread accessing the collection. If the collection is heavily used by many threads (and it is a set), then a ConcurrentSkipListSet is probably better.

---

You also seem to have a misconception about how "big O" measures combine. If I have one step of an algorithm that is O(N) and a second step that is also O(N), then the two steps combined are STILL O(N) .... not "more than O(N)". You can derive this from the definition of "big O". (I won't bore you with the details, but the Math is simple.)