Structure that allows duplicates, maintains insertion order and allows removal and insertion

Question

I am looking for a data structure that allows duplicates and maintains insertion order so that if given file input of : a + a + b = c

So that once correctly split, I will get: {a,+,a,+,b,=,c}

This data structure also needs to allow for removal and insertion in the correct order, for example if I replace a with d, I should get {d,+,d,+,b,=,c}.

Finally the structure must also be able to recognize which items are before or after a certain item. E.g. the item directly before = is b and directly after is c.

I am aware that lists allow duplicates and some lists maintain insertion order, but I am unsure as to which will allow me to achieve my goals.

If you are aware of a structure the will achieve all of the above, please provide the syntax for creating such a structure.

Regards

Answer 1

Seems ArrayList with ListIterator would fulfill your requirements, for sample usage, see: http://www.java2s.com/Code/Java/Collections-Data-Structure/BidirectionalTraversalwithListIterator.htm

Answer 2

Assuming performance is enough of a concern, to not use one of the simple Java List implementation (because you want to avoid iterating over the whole list to search for items during replacement), then you would need a maintain two data structures, one to keep track of the order of tokens and one as an index of token positions for replacement.

So, something like (I haven't run this through a compiler, so expect typos):

class TokenList
{
  List<String> tokens;
  Map<String,List<Integer>> tokenIndexes= new HashMap<String,List<Integer>>();

  TokenList(Iterable<String> tokens)
  {
    this.tokens = new ArrayList<String>(tokens);
    for (int i = 0; i < this.tokens.size(); i++)
    {
      String token = this.tokens.get(i);
      List<Integer> indexes = tokenIndexes.get(token);
      if (indexes == null)
      {
        index = new List<Integer>();
        tokenIndexes.put(token, indexes);
      }
      indexes.add(index);
    }
  }

  void replace(String oldToken, String newToken)
  {
    List<Integer> indexes = tokenIndexes.remove(oldToken);
    if (indexes == null)
      throw new IllegalArgumentException("token doesn't exist: " + oldToken);
    for (int index : indexes)
      tokens.set(i, newToken);
    tokenIndexes.put(newToken, indexes);
  }
}

This structure makes the assumption that tokens will not change index once created (the tokenIndex map would need to be recreated, which is a relatively costly operation).