Java - вставка элемента в середину или в любое место, кроме начала / конца Deque
Мне кажется, что нет способа вставить элемент где-нибудь посередине класса Deque за время O(1). Я хочу сохранить ссылку на определенный узел в дескрипторе, скажем, в хеш-таблице, и если мне нужно удалить этот узел, я просто перехожу к его prev и устанавливаю prev.next = this.next и аналогично this.next.prev = предыдущий и удалите этот текущий элемент.
Но если у меня есть deque как
Deque<String> myDeque = new ArrayDeque<String>();
or
Deque<String> myDeque = new LinkedList<String>();
ни один из них не обеспечил бы это.
Есть ли альтернатива этому? Если мне нужно реализовать свой собственный список с двойной связью, есть ли способ, которым я могу избавиться, просто расширив то, что ArrayDeque уже делает, чтобы мне не пришлось переписывать код для вставки и т. Д.?... ну, насколько я знаю... я так не думаю: (: (
2 ответа
Это невозможно без написания вашей собственной Deque. Тем не мение:
Если я правильно понимаю, вы хотите O(1) удаления и вставки в одном конкретном месте объекта, который в противном случае имеет интерфейс Deque? Могу ли я предложить вам использовать два Deques?
Вставка и удаление вначале только в одном из Deques, пока вы не наткнетесь на узел, который хотите сохранить. В этот момент, в зависимости от того, вставляете ли вы этот узел спереди или сзади, вы этого не делаете, а вставляете узел в пустой Dequeи что пусто Deque становится целью для всех ваших вставок и удалений спереди или сзади с тех пор, а другой Deque обрабатывает только вставки и удаления сзади или спереди.
Это может быть масштабировано до нескольких ключевых узлов (что приводит к [number of nodes]+1Dequeс), только вставки / удаления происходят в передней части Deque и позади друг друга Deque (все остальные статичны). Вы также должны ввести фиксированное соглашение о том, первый или последний элемент в каждом Deque (кроме первого или последнего Deque) является "ключевым" узлом.
Конечно, если у вас есть случайная вставка и удаление во многих точках, возникает вопрос: почему вы настаиваете на Deque?
Я бы не стал удалять узел. Вместо этого, когда вы берете его из Deque, я проверяю вашу коллекцию элементов, подлежащих удалению / игнорированию, а затем отбрасываю ее, если требуется.