7

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.

Improve this question
4
  • "But i understood that there can be only one iterator on a list at the time." That's not true. Commented Jan 22, 2014 at 21:24
  • 2
    @LouisWasserman Even if he could have multiple iterators, would it help? "if the list is structurally modified at any time after the iterator is created, in any way except through the Iterator's own remove or add methods, the iterator will throw a ConcurrentModificationException". Seems like if he removes an element using iter.remove on one iterator, all the others would then become unusable. Commented Jan 22, 2014 at 21:30
  • @ajb: Yes, you'd have to do all this manipulation through a single iterator, but you couldn't do it if the elements were noncontiguous and you had more than one to deal with. Commented Jan 22, 2014 at 21:39
  • @LouisWasserman "but you couldn't do it if the elements were noncontiguous and you had more than one to deal with" - thats exactly the case. Commented Jan 23, 2014 at 8:30

2 Answers 2

Reset to default
5

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"

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

So 'Java' don't have any data structure can that offer the same performance as a simple self-written MyDoublyLinkedList<MyNode<T>> ?
@roy Edited to answer.
-2

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?

Improve this answer

9 Comments

It's debatable that an ArrayList removes in O(1), it has to shift everything back down which is relegated to the native System.arraycopy method. depending on how this is implemented, it may well be O(n)
The size of the list is n, therefore O(n) worst case.
An Arraylist simply moves where the cost occurs, but has the same performance; it doesn't traverse to find the element, but it has to shift everything after. Both are O(n).
To be clear, a LinkedList in Java is a doubly linked list. Removing items from a dll is efficient if you have a reference to the node; it's O(1). Java just doesn't allow you access to the nodes to do so.
Lol, No,really, it is, and its O(n) see: stackoverflow.com/questions/2710002/… you seem to not understand that a single native call != O(1)
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.