2

In C++, I would sometimes store objects in a linked list. I would associated the object with an iterator pointing to its location. Then, given the iterator, I could remove the object from the linked list in O(1) time. The operation is O(1), because the list just updates the pointers to the previous and next elements in the list. The C++ method I'm talking about: http://www.cplusplus.com/reference/list/list/erase/

Is there a way to do this with the same O(1) complexity in Java?

LinkedList seems to shift subsequent elements: https://docs.oracle.com/javase/7/docs/api/java/util/LinkedList.html#remove(int)

Maybe there is a different Java class to achieve this?

Thanks

Improve this question
1
  • 1
    If you are worried about speed, use a linked list with caution. Sure, you can insert and remove easily, but pretty much absolutely everything else you do has a price. Sometimes quite hefty. For one thing, those linked list elements are all over the place making for really bad locality. The CPU's ability to predict and cache goes into the crapper. Commented Apr 16, 2016 at 20:28

3 Answers 3

Reset to default
4

The standard library LinkedList doesn't let you do this. remove(int) doesn't need to shift elements, but it does need to find the list node to remove, and that takes linear time. You could use an iterator, but Java iterator invalidation is much more aggressive than C++ iterator invalidation. After removing one element through an iterator positioned at that element, any other iterators would be invalidated.

You'd probably have to write your own LinkedList class.

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

3 Comments

Oh by shift elements, I meant that it also loops through elements after the removed element and decrements their indices in the list. I forgot that it'll also loop through the list to get to the position to remove. So, actually, it loops through the entire list. What do you mean by you could use an iterator? Without a custom LinkedList I don't think you can. edit: I see, you were probably talking about iterator's remove method
@walter2011: "I meant that it also loops through elements after the removed element and decrements their indices in the list" - it doesn't do that. Nodes don't track their indices explicitly, so there's no per-node index data to adjust. As for using an iterator, I did indeed mean the iterator's remove method.
I think I was interpreting the javadoc too literally then. It says "Shifts any subsequent elements to the left (subtracts one from their indices)."
1

Nobody ever said that manipulating the previous and next pointers took O(n) time in a Linked List. It's finding the element that makes it O(n).

If you had one of these "iterators" (which isn't what they might be called) for each element in the list, you'd still have to go through each one of these "iterators" to find the one for any random object in the list. That's an O(n) operation.

Once you have found the right object, updating the previous and next elements is not dependent on the number of elements, so it is O(n), regardless of language.

Improve this answer

Comments

0

Once you have found an Item using an Iterator, you can call remove() on it and remove the element in O(1) however this only works if you haven't modified the list or use a List which supports concurrent updates.

Improve this answer

Comments

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.