From charlesreid1

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


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.


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


(code for a unit test)

The Class

(code for the class)