Pointer into Java LinkedList Node
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.
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"
The problem with storing a pointer to the item you wish to remove is that removing an item from a linked list requires knowledge of the item preceding the item you wish to remove as well.
A LinkedList is not designed for removing specific items at low cost - you should re-evaluate what List you use (an ArrayList removes in O(1)). Is there any reason you want a LinkedList?
链接地址: http://www.djcxy.com/p/18712.html