StacksQueues/Java/LinkedDeque

LinkedDeque is a class that implements a double ended queue using a linked list data structure.

Code

Implementation notes

To implement a double-ended queue with fast, O(1) addition and removal at the front and back of the data structure, use a doubly-linked list.

To conserve memory overhead, use a circular doubly-linked list.

Interface

The Abstract Data Types#Deques page covers the methods that deques normally implement:

• enqueueFront : add something to the front of the queue (will be the next thing to come out)
• enqueueBack : add something to the back of the queue (normal order)
• dequeueFront : remove something from the front of the queue (normal order)
• dequeueBack : remove something from the back of the queue (cutting in line)
• first : peek at first item
• last : peek at last item
• size : size of deque
• isEmpty : is deque empty
• rotate : rotate deque, move item from front to back

Test

(code for a unit test)

The Class

(code for the class)