CODEWITHSUNDEEP
java
robev
robev

Reputation: 1949

Fast contains and LIFO data structure

I'm looking for a data structure in java that has a fast contains() method, yet probably needs some sort of ordering because I need to be able to add to it and take from it, but I want it to be like a Stack with LIFO functionality. Is this possible? I thought of a HashSet which has fast contains() but it doesn't have guaranteed ordering, and a LinkedList which has guaranteed ordering but a slow contains().

Upvotes: 1

Views: 484

Answers (2)

Mark Peters
Mark Peters

Reputation: 81124

LinkedHashSet() gets you partially there, but unfortunately doesn't expose a good way to get LIFO removal.

I think what you want is something that wraps a LinkedList<T> (for LIFO removal) and a HashMap<T, Integer> (for tracking cardinality). Then you'd have these methods (very roughly):

public class QuickCheckStack<T> {

   private final Map<T, Integer> elementCardinality = new HashMap<T, Integer>;
   private final Deque<T> stack = new LinkedList<T>();

   public void push(T element) {
      Integer count = elementCardinality.get(element);
      if (count == null) {
          count = 0;
      }
      elementCardinality.put(element, count + 1);
      stack.push(element);
   }

   public T pop() {
      T element = stack.pop();
      elementCardinality.put(element, elementCardinality.get(element) - 1);
      return element;
   }

   public boolean contains(T element) {
      Integer count = elementCardinality.get(element);
      return count != null && !count.equals(0);
   }
}

Upvotes: 2

Jay
Jay

Reputation: 27492

Hmm, if you need to do LIFO stack operations, you can't sort the collection, because then you lose the order in which items were added to the collection.

Frankly, the simplest way to do what you want may be to create two parallel structures, like create both a Stack and a HashMap. Wrap them inside a bigger class that has add and remove functions that always add/remove to both. Then you can use the stack to do your pushes and pops and the HashMap to do your contains.

Normally I hate to create duplicate data, but the only way I see to do what you want is to have an "indexed stack", which is pretty much what the approach I'm suggesting here amounts to.

I emphasize wrapping this in a class that does the adds and removes, and making sure that all adds and removes go through that class. Otherwise, if you have code that does the adds/removes scattered all over, you create the possibility that the two structures will get out of sync. Force it all through one class and you only have to debug that part once.

Upvotes: 3

Related Questions