Pointer into Java LinkedList Node

Question

I am pushing n entries into Java LinkedList at O(1).
There are few unique items i would like to remove later on at O(1).
I though about keeping an array with "pointers" to the unique nodes at the LinkedList so i can later on remove them.
is there a way to do it on LinkedList or any other java class?
I tried storing iterators to the items. So i can use iter.remove(). But i understood that there can be only one iterator on a list at the time.

I know that an easy solution could be implementing link list on my own. But i rather use LinkedList or some other Java class already implemented.

Answer 1

The Java List implementations do not offer O(1) performance on removes*. Using an iterator you have to traverse to the index ( O(n) ), with an ArrayList you have an after-remove shift ( O(n) ), and even though LinkedList is a doubly-linked list, it does not expose the nodes in the list for you to be able to remove them directly by simply reassigning the next/last references - a traversal is required to find the node to remove ( O(n) ).

You could write your own MyDoublyLinkedList<MyNode<T>> that did so, exposing the nodes rather than the values contained within, which would allow for O(1) removals if you retained a reference to the node. Indexing is of course O(n) to get something from the list by index. Depending on your use patterns it may be a viable design choice.

Short of that, if you want to use the data structures provided by Java, use a data structure that provides that performance:

If ordering isn't important and there are no duplicate items, use a HashSet (note, however, this does not allow direct indexing at all)

Otherwise, reworking your code to use a Map implementation is probably your best bet.

[*] LinkedList and the Deque implementations are O(1) for head/tail removal.

Edit to add from comments:

As mentioned above, no, there is no O(1) time complexity remove operation.

The reason for this is that except in the most extreme edge cases, it's irrelevant.

On my 5 year old, 3Ghz desktop it takes .2ms (point-two) for the worst-case O(n) removal on a LinkedList with 100,000 entries via an index (that is to say, index = length/2)

I start running into windows swapiness disk I/O due to windows memory management on this box if I up it to 1,000,000 entries.

In short, you're trying to solve a problem that doesn't exist in most cases. This is generally called "Premature Optimization"