Java - inserting an element in the middle or anywhere other than front/end of a Deque

Question

It looks to me that there is no way to insert an element somewhere in the middle of a Deque class in O(1) time. I want to maintain a reference to a particular node in the deque in say a hash table and if I need to remove this node, I just go to its prev and set the prev.next=this.next and similarly this.next.prev=prev and remove this current elem.

But if I have a deque as

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

none of these would provide this.

Is there an alternative to this? If I have to implement my own Doubly linked list, is there a way that I can do away by just extending what ArrayDeque already does so I don't have to rewrite the code for insert etc? ...well as far as i know...i don't think so : ( : (

Answer 1

This is not possible without writing your own Deque. However:

If I understand correctly you want O(1) removal and insertion at one specific point in an object that otherwise has the interface of a Deque? May I suggest that you use two Deques?

Insertion and removal are at first only in one of the Deques, untill you come across the node you want to save. At that point, depending on wether you insert this node at the front or at the back you don't do that, but insert the node in the empty Deque, and that empty Deque becomes the target for either all your insertions and removals at the front or the back from then on, and the other Deque only handles insertions and removals at the back or front.

This would scale maybe to a few key nodes (leading to [number of nodes]+1 Deques used), with only insertions/removals happening at the front of one Deque and at the back of one other Deque (all others are static). You would also have to introduce a fixed convention of wether the first or the last item in each Deque (except the first or the last Deque) is a "key" node.

Of course if you have random insertion and removal at many points the question becomes: Why do you insist on a Deque?

Answer 2

I wouldn't remove the node. Instead when you take it from the Deque I would check your collection of elements to be removed/ignored and then discard it if required.