Структура, которая позволяет дублировать, поддерживает порядок вставки и позволяет удалять и вставлять

Я ищу структуру данных, которая позволяет дублировать и поддерживает порядок вставки, так что, если задан ввод файла: a + a + b = c

Так что один раз правильно разделив, я получу: {a,+,a,+,b,=,c}

Эта структура данных также должна обеспечивать возможность удаления и вставки в правильном порядке, например, если я заменю a на d, я должен получить {d,+,d,+,b,=,c}.

Наконец, структура также должна уметь распознавать, какие элементы находятся до или после определенного элемента. Например. элемент непосредственно перед = – это b, а сразу после – c.

Я знаю, что списки допускают дублирование, а некоторые списки сохраняют порядок вставки, но я не уверен, какой из них позволит мне достичь моих целей.

Если вам известна структура, которая позволит достичь всего вышеперечисленного, предоставьте синтаксис для создания такой структуры.

С Уважением


java list duplicates replace insertion
person Digitalwolf    schedule 23.01.2013    source источник
comment
Еще не пробовал. Никогда не знал, что такое существует. Сможет ли он делать все, что я хочу?   -  person Digitalwolf    schedule 23.01.2013
comment
Я думаю, вам нужна сбалансированная древовидная структура данных.   -  person Subhrajyoti Majumder    schedule 23.01.2013
comment
Я определенно мог бы использовать фактор ветвления. Есть ли ссылка на пример, который вы можете мне предоставить, и каков синтаксис для создания такой структуры?   -  person Digitalwolf    schedule 23.01.2013
comment
Доступна некоторая базовая реализация — ссылка 1 ссылка 2, но вы должны расширить то, что вам нужно больше.   -  person Subhrajyoti Majumder    schedule 23.01.2013

Ответы (2)


arrow_upward
3
arrow_downward

Кажется, что ArrayList с ListIterator удовлетворит ваши требования, пример использования см. в: http://www.java2s.com/Code/Java/Collections-Data-Structure/BidirectionalTraversalwithListIterator.htm

person Peter Butkovic    schedule 23.01.2013
comment
Мой входной файл не всегда будет одинаковым, поэтому элементы, которые мне придется удалить, не всегда будут в одном и том же порядке, поэтому я не уверен, что повторение данных - лучший вариант. В идеале я хотел бы сказать if(list.contains(a){ заменить a на d}, чтобы получить вывод, который я продемонстрировал в своем вопросе. - person Digitalwolf; 23.01.2013
comment
Похоже, ваша проблема заключается в поиске алгоритма, а не в поиске подходящей структуры данных. Реализация List с ListIterator должна соответствовать вашим заявленным требованиям. Если нет, вам следует обновить вопрос. - person Gustav Karlsson; 23.01.2013
comment
Просто искал структуру данных, которая могла бы хранить дубликаты и поддерживать порядок вставки. Раньше я использовал arrayList, и, поскольку мой входной файл очень разнообразен, все, что я мог сделать, это заменить значение, но эти значения продолжали помещаться в конец списка. Можно ли сделать то, что я объяснил в своем вопросе, с помощью listIterator, если ввод сильно различается? - person Digitalwolf; 23.01.2013
comment
Тогда List — это ваша структура. Вы можете использовать Collections для замены вещей: Collections.replaceAll(myArray, 'a', 'd'). - person Gustav Karlsson; 23.01.2013

arrow_upward
1
arrow_downward

Предполагая, что производительность достаточна для беспокойства, чтобы не использовать одну из простых реализаций Java List (поскольку вы хотите избежать итерации по всему списку для поиска элементов во время замены), вам потребуется поддерживать две структуры данных, одну для сохранения отслеживать порядок токенов и один как индекс позиций токенов для замены.

Итак, что-то вроде (я не запускал это через компилятор, поэтому ожидайте опечатки):

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);
  }
}

Эта структура предполагает, что токены не изменят индекс после создания (требуется воссоздание карты tokenIndex, что является относительно дорогостоящей операцией).

person SimonC    schedule 23.01.2013
comment
Это уже пробовали. Необходимо иметь дубликаты ключей. Пересмотрю этот вариант - person Digitalwolf; 23.01.2013
comment
Я не уверен, что понимаю, что вы имеете в виду. Это справляется с несколькими экземплярами токена/ключа в списке ввода. - person SimonC; 24.01.2013