Java LinkedHashSet remove some elements from the end

Question

I am working on a problem where i'm required to store elements with requirements of No Duplication and Maintaining order. I chose to go with LinkedHashSet Since it fulfilled both my requirements.

Let's say I have this code:

 LinkedHashSet hs = new LinkedHashSet();
  hs.add("B");
  hs.add("A");
  hs.add("D");
  hs.add("E");
  hs.add("C");
  hs.add("F");
  if(hs.contains("D")){
       //do something to remove elements added after"D" i-e remove "E", "C" and "F"
       //maybe hs.removeAll(Collection<?>c) ??
   }

Can anyone please guide me with the logic to remove these elements?

Am I using the wrong datastructure? If so, then what would be a better alternative?

Answer 1

So, after trying a couple of things mentioned above, I chose to implement a different Data structure. Since I did not have any issue with the O(n) for this problem (as my data is very small)

I used Graphs, this library came in really handy: http://jgrapht.org/

What I am doing is adding all elements as vertices to a DirectedGraph also creating edges between them (edges helped me solve another non-related problem as well). And when it's time to remove the elements I use a recursive function with the following pseudo code:

removeElements(element) {

tempEdge = graph.getOutgoingEdgeFrom(element)
if(tempEdge !=null)
   return;
tempVertex = graph.getTargetVertex(tempEdge)
removeElements(tempVertex)
graph.remove(tempVertex)

}

I agree that graph DS is not good for these kind of problems, but under my conditions, this works perfectly... Cheers!

Answer 2

I think you may need to use an iterator to do the removal if you are using a LinkedHashSet. That is to say find the element, then keep removing until you get to the tail. This will be O(n), but even if you wrote your own LinkedHashSet (with a doubly linked list and hashset) you would have access to the raw linking structure so that you could cut the linked list in O(1), but you would still need to remove all elements that you just cut from the linked list from the HashSet which is where the O(n) cost would arise again.

So in summary, remove the element, then keep an iterator to that element and continue to walk down removing elements until you get to the end. I'm not sure if LinkedHashSet exposes the required calls, but you can probably figure that out.

Answer 3

You could write your own version of an ArrayList that doesn't allow for duplicates, by overriding add() and addAll(). To my knowledge, there is no "common" 3rd party version of such, which has always surprised me. Anybody know of one?

Then the remove code is pretty simple (no need to use an ListIterator)

int idx = this.indexOf("D");
if (idx >= 0) {
  for (int goInReverse = this.size()-1; goInReverse > idx; goInReverse--)
    this.remove(goInReverse);
}

However, this is still O(N), cause you loop through every element of the List.

Answer 4

The basic problem here is that you have to maintain two data structures, a "map" one representing the key / value mapping, and a "list" other representing the insertion order.

There are "map" and "list" organizations that offer fast removal of a elements after a given point; e.g. ordered trees of various kinds and both array and chain-based lists (modulo the cost of locating the point.)

However, it seems impossible to remove N elements from the two data structures in better than O(N). You have to visit all of the elements being removed to remove them from the 2nd data structure. (In fact, I suspect one could prove this mathematically ...)

In short, there is no data structure that has better complexity than what you are currently using.

The area where it is possible to improve performance (with a custom collection class!) is in avoiding an explicit use of an iterator. Using an iterator and the standard iterator API, the cost is O(N) on the total number of elements in the data structure. You could make this O(N) on the number of elements removed ... if the hash entry nodes also had next/prev links for the sequence.