Java - вставка элемента в середине или в любом месте, кроме переднего/конца детекса

Question

Мне кажется, что нет возможности вставить элемент где-нибудь посередине класса Deque в O (1) раз. Я хочу сохранить ссылку на конкретный узел в deque, например, в хеш-таблице, и если мне нужно удалить этот узел, я просто перейду к его превью и поставлю prev.next = this.next и аналогично this.next.prev = prev и удалите этот текущий элемент.

Но если у меня есть Deque, как

Deque<String> myDeque = new ArrayDeque<String>(); 
or 
Deque<String> myDeque = new LinkedList<String>(); 

ни один из них не обеспечил бы это.

Есть ли альтернатива этому? Если мне нужно реализовать свой собственный Doubly-связанный список, есть ли способ, который я могу сделать, просто расширив то, что ArrayDeque уже делает, поэтому мне не нужно переписывать код для вставки и т. Д.? ... ну насколько я знаю ... я так не думаю: (: (

Answer 1

Это невозможно без написания собственного Deque Однако:..

Если я правильно понимаю, что вы хотите O (1) удаление и вставка в одной конкретной точке в объект, который в противном случае имеет интерфейс Deque? Могу ли я предложить использовать два Deque s?

Вставка и удаление сначала onl y в одном из Deque s, пока вы не встретите узел, который хотите сохранить. В этот момент, в зависимости от того, вы вставляете этот узел спереди или сзади, вы этого не делаете, но вставляете узел в пустой Deque, а пустой Deque становится объектом для всех ваших вставок и абзацев на спереди или сзади, а другой Deque обрабатывает только вставки и удаления сзади или спереди.

Это масштаб может быть, несколько ключевых узлов (ведущих к [number of nodes]+1Deque с используемыми), только с вставками/абсорбция происходит на фронте одного Deque и на задней части одной другой Deque (все остальные являются статическими). Вам также необходимо ввести фиксированное соглашение о том, что первый или последний элемент в каждом Deque (кроме первого или последнего Deque) является «ключевым» узлом.

Конечно, если у вас есть случайная установка и удаление во многих точках, вопрос становится следующим: почему вы настаиваете на Deque?

Answer 2

Я бы не удалял узел. Вместо этого, когда вы берете его с Deque, я бы проверил вашу коллекцию элементов на удалить/игнорировал, а затем выбросить его, если требуется