1

I'm new to Java. I tried to store iterators of LinkedList elements in a Map, and delete them later:

Map<Integer, Iterator<Integer>> map = new HashMap<>();
LinkedList<Integer> list = new LinkedList<>();
list.addFirst(1);
map.put(1, list.iterator());
list.addFirst(2);
map.put(2, list.iterator());

Iterator<Integer> iter = map.get(1);
iter.next();
iter.remove(); // list is supposed to be [2]

However, ConcurrentModificationException occurs. I think as soon as I add '2' in the list, the iterator of '1' expires, right?

In C++, list<int>::iterator represents the pointer of a node from a linked list, which stays constant and available whenever new nodes are inserted into the list. I'm a little bit confused about this in Java.

Sorry for the confusion. Now I know that Iterator is usually used in iterations, not to 'locate' an element, which is a bit different from that in C++.

I actually try to preserve the reference of elements from a linked list, so that the elements can be efficiently accessible in a complexity of O(1) instead of O(n).

Is there any related kind of Collection or Util? Or maybe I have to implement DeLinkedList and DeLinkedNode by myself. Thanks in advance.

cosimoth
  • 167
  • 10
  • I'm gonna take a wild guess and say it is probably because you created a second iterator. Try what you have but without the part that creates the second iterator and see what happens – smac89 Aug 07 '20 at 05:40
  • 2
    Yes this is the expected behavior. Can you clarify what you're trying to do here? Java is not c++ and many idioms and techniques you've used in c++ either don't work or are better expressed in a different way in Java. For example, the LinkedList class is almost never used in Java, because its alternatives are much better – Joni Aug 07 '20 at 05:41
  • 2
    To me, it looks like you are trying to implement a linked list with a lookup time complexity of *O(1)*... – MC Emperor Aug 07 '20 at 05:45
  • I wanna save the Iterator of an element in a map. When I get it from the map and call `Iter.remove()` method, I think the operation can be O(1) and more efficient than `list.remove(elementValue)`, which is O(n) I think. – cosimoth Aug 07 '20 at 05:46
  • 2
    Might as well use a LinkedHashMap – smac89 Aug 07 '20 at 05:48
  • If I just `addFisrt(2)` without putting its iterator in the map, error still occurs... – cosimoth Aug 07 '20 at 05:50
  • You should use `Map>`. And you can get `Iterator` with `map.get(1).iterator()`. –  Aug 07 '20 at 05:55
  • 1
    *I wanna save the Iterator of an element in a map* -. See this is sort of thing you don't do in Java because the standard library works in a completely different way than c++ STL. If you explained what the over all end goal is maybe we can suggest an alternative approach that actually works. Also when you answer someone tag them with @ so they get a notification – Joni Aug 07 '20 at 05:57
  • 1
    Yea it looks like linkedlist does not like it when you add an item to the list after you have created an iterator. What you're trying to do won't work in Java because often times, the internals are not simply pointers to actual memory, but can be more complex than that. Also note that in C++, this method won't even work reliably because the list can reallocate memory and recreate it's internals, which leaves you with a dangling pointer. Unless you control the allocator in C++, there is really no guarantee – smac89 Aug 07 '20 at 05:57
  • 2
    If you explain the reason why you want to do this, (i.e. your end goal), then you might get an actual answer – smac89 Aug 07 '20 at 06:00
  • Does this answer your question? [Concurrent Modification exception](https://stackoverflow.com/questions/1496180/concurrent-modification-exception) – smac89 Aug 07 '20 at 06:03
  • the efficency of the removal in any case depends on the list implementation you use. The iterator is basically a 'tool' you use to iterate on the structure in an implementation agnostic way – Massimo Petrus Aug 07 '20 at 06:32
  • Note that iterators track the number of changes made to a collection by themselves why the collections track that number as well. Thus if you make a change from outside an iterator those numbers won't match anymore and the iterator will throw a ConcurrentModificationException - and that is by design! (think about it: the element might not even be in the list anymore). - The main question would be: _What exactly are you trying to do? What are you trying to achieve with this?_ – Thomas Aug 07 '20 at 06:33
  • 1
    The real question seems to be what do you want to do with this data structure ? Iterate efficently ? Remove or add elements efficently ? Finding elements efficently ? – Massimo Petrus Aug 07 '20 at 06:37
  • It sounds like you should be using an `ArrayList` instead, that has exactly the properties you want to achieve (and it takes less memory than a `LinkedList`, and is faster in almost all (if not all) usages). – Mark Rotteveel Aug 07 '20 at 07:42

2 Answers2

0

If you want the ordering and O(1) insertion and removal of a linked list, coupled with the O(1) lookup of a hash table, LinkedHashSet is likely your best bet.

A LinkedHashSet is a Set that preserves insertion order. So you can do things like:

import java.util.LinkedHashSet;

...

LinkedHashSet<Integer> set = new LinkedHashSet();
set.add(2);
set.add(1);

set.remove(1);

A couple of caveats:

  • This is a Set, so you won't be able to keep more than one copy of an element.
  • There is no addFirst equivalent. Items are always added to the end.
Mad Physicist
  • 107,652
  • 25
  • 181
  • 264
0

Instead of using LinkedList, use ConcurrentLinkedDeque. The iterators will then work as you are hoping.

If you need the List functionality, as opposed to just iterators, you can very easily use the AbstractSequentialList class to create a List implementation from your ConcurrentLinkedDeque.

Simon G.
  • 6,587
  • 25
  • 30