Структура данных, которая вставляет постоянное время в конечные точки и до/после элемента?

Ответ 1

Честно говоря, я думаю, что обычная реализация LinkedList будет способом:

• Имеет неограниченный размер.
  • Да.
• Поддерживает порядок вставки его элементов.
  • Да.
• Вставляет эффективно в начало и конец списка (идеально в постоянное время).
  • Да, и O (1).
• Вставляет эффективно до или после существующего элемента (идеально в постоянное время).
  • Если вы сохраняете Map<?, Node> при вставке/удалении элементов, вы можете получить доступ к Node (и его предыдущим/следующим узлам) в постоянное время и вставить/удалить этот путь.

В зависимости от общего количества событий (и того, как часто события могут обманывать), можно также учитывать линейное время, позволяющее использовать реализацию API LinkedList.

Ответ 2

Как насчет дерева AVL? Поскольку дерево всегда сбалансировано, оно имеет высоту O (log (N)), где N - количество узлов в дереве. Это может привести к тому, что в наихудшем случае будет также O (log (N)).

Я считаю, что как можно ближе к постоянному времени, когда вы можете получить то, что ищете. Извините, если это не ответ, у меня нет достаточной репутации, чтобы оставить комментарий еще:/

Ответ 3

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

Если обман редко встречается, переходите к своей собственной структуре на основе массива. java.util.ArrayDeque обрабатывает оба конца в O (1), но он не может делать вставки в середине. Их можно легко добавить, но сложность O (n).

Обратите внимание, что LinkedList для большинства операций (из-за его ужасной ArrayDeque данных) намного медленнее, чем ArrayList и ArrayDeque.

Предположим, вам очень нужна постоянная вставка времени посередине. Что-то вроде

insertAfter(existingElement, newElement);

Проблема с java.util.LinkedList заключается в том, что она не имеет такой операции. Все, что у него есть, - ListIterator, который позволяет вам вставлять посередине, но это помогает, когда вы сначала позиционируете свой итератор (O (n)).

Поэтому вам нужен ваш собственный список. Основная реализация довольно тривиальна, что вам дополнительно нужно - это прямой доступ к ее узлам (вещи, содержащие next и prev ссылки, а не вещи, которые вы add). Затем поддерживайте Map<MyThing, MyListNode>, который позволяет вам найти узел для existingElement Map<MyThing, MyListNode>. Теперь вы просто создаете новый узел для newElement, связываете его правильно (что в основном тривиально, но имеет некоторые угловые случаи) и обновляют вашу карту.

Чтобы устранить граничные случаи (первый/последний/единственный узел), добавьте два фиктивных узла (prefirst и postlast) в ваш связанный список. Очевидно, что это единственные узлы, которые не будут храниться на вашей карте. Они делают реализацию довольно тривиальной, например,

void insertAfter(MyThing existingElement, MyThing newElement) {
   Node found = map.get(existingElement);
   if (found == null) throw ...
   Node newNode = new Node(newElement);
   map.put(newElement, newNode);

   // Link newNode where it belongs to.
   newNode.next = found.next;
   newNode.prev = found;

   // Fix links.
   newNode.prev.next = newNode;
   newNode.next.prev = newNode;   
}

void insertFirst(MyThing newElement) {
   Node found = prefirst;

   // All the remaining code is simply copied from above.
   // Factor it out.

   Node newNode = new Node(newElement);
   map.put(newElement, newNode);

   // Link newNode where it belongs to.
   newNode.next = found.next;
   newNode.prev = found;

   // Fix links.
   newNode.prev.next = newNode;
   newNode.next.prev = newNode;   
}

Ответ 4

Используйте LinkedHashMap.

• Сохраняет порядок вставки
• Быстро (потому что использует ключ, чтобы найти элемент в основном в O(1)).
• Позволяет вставлять элементы всякий раз, когда вам нравится (но для этого вам нужно подумать о хорошем ключе - разработать hashCode() и equals() что будет иметь смысл для вашей логики заказа).

Хэш-таблица и связанный список реализации интерфейса карты с предсказуемым порядком итерации. Эта реализация отличается от HashMap тем, что она поддерживает двусвязный список, проходящий через все его записи. Этот связанный список определяет порядок итераций, который обычно является порядком, в котором ключи были вставлены в карту (порядок вставки).

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

Обратите внимание, что эта коллекция не является потокобезопасной.

Ответ 5

Обычно я использую forward_list из c++ 11 для операций, которые требуют оптимальных вставок в любых позициях. Он основан на односвязном списке. См. Forward_list.

Перечисленные списки представляют собой контейнеры последовательностей, которые позволяют выполнять операции вставки и стирания времени в любом месте последовательности. См. Первое предложение forward_list

Если оптимизация вызывает вашу озабоченность, почему бы не переключиться на c++. Я не уверен, что такая функция присутствует в java. Обратите внимание, что хотя forward_list предлагает постоянную вставку времени, вы не можете использовать элементы доступа непосредственно по этой позиции.

В общем, для связанного списка, когда вы говорите, вставляете в позицию. Есть два случая:

1. У вас есть ссылка на узел в этой позиции. В этом случае временная сложность O (1)

2. У вас есть только индекс. Сложность времени будет равна O (n)