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"