0

I want a data structure with the following operations:

  • Random access delete: Take reference to object, delete from structure (elements are unique)
  • Add element at end
  • Bidirectional iteration

Random access deletion, and element appending should be possible during iteration.

A linked list hashset should theoretically support doing all of these in O(1) but I cannot seem to get LinkedHashSet to do these for me.

If there is an easy way to do it optimally I'd like to know. Otherwise, what's a good way able to cope with about 10k elements? All operations are performed roughly the same amount of times.

user1417648
  • 101
  • 1
  • Have you tried using a linked list? http://docs.oracle.com/javase/6/docs/api/java/util/LinkedList.html – ChadNC May 25 '12 at 15:10
  • What's not working with the LinkedHashSet? – keyser May 25 '12 at 15:11
  • Keyser: 1. The iterators returned by this class's iterator method are fail-fast: if the set is modified at any time after the iterator is created, in any way except through the iterator's own remove method, the iterator will throw a ConcurrentModificationException. 2. Only forward iteration – user1417648 May 25 '12 at 15:25
  • Take a look to GapList: http://stackoverflow.com/a/24140749/3315914 – rpax Jun 11 '14 at 07:32

1 Answers1

0

A nice overview about the performance of List, Set and Map operations can be found in this article.

Omnaest
  • 3,131
  • 1
  • 17
  • 18