Java sorted double-linked list: How to insert a new node quickly in the right position?

Question

I have a double-linked list that needs to have fast inserts and removes. I can just transverse the whole thing in either direction to find where to insert or remove, but is there a more clever way to find the insertion or removal point? First thing that came to mind was binary search, but since it is a linked list with no indexes (not an array), I am not sure how to jump around my linked list.

What is the right approach here to make insertions and removals the fastest they can be?

Answer 1

The smart way is to move towards a Skip List.

Other approaches include cacheing recent accesses and making intelligent guesses where to start your search, at the end, at the start or at a recent spot.

Answer 2

You may use a B-tree instead of the double linked list or, as mentioned in an other answer, use a Skip_list. For fast searching a double linked list is the wrong data-structure.

Answer 3

As you indicate yourself, because the linked list is not indexable there is no way than to loop over the list to find the right insertion point...