Implementation of Double-Ended Queue (Deque)

I have already covered Queue Implementation in my previous posts. Let's consider now a queue-like data structure that supports insertion and deletion at both the front and the rear of the queue. Such an extension of queue is called "Double-Ended Queue" or "Deque".

Let's look at the abstraction of Deque:

1. Deque.java

package ora.deque;

public interface Dequeue {

void insertFirst(Object obj);

void insertLast(Object obj);

Object removeFirst();

Object removeLast();

int size();

}

Now let's implement deque functionality using a following linked list data structure.

2. DLNode.java

package ora.linked;

public class DLNode {

private DLNode next, previous;

private Object element;

public DLNode(Object element, DLNode next, DLNode previous) {

this.element = element;

this.next = next;

this.previous = previous;

}

public DLNode() {

this(null, null, null);

}

public DLNode getNext() {

return this.next;

}

public DLNode getPrevious() {

return this.previous;

}

public Object getElement() {

return this.element;

}

public void setNext(DLNode node) {

this.next = node;

}

public void setPrevious(DLNode node) {

this.previous = node;

}

}

3. DequeImpl.java

package ora.deque;

import ora.linked.DLNode;

public class DequeImpl implements Dequeue {

private DLNode header, tail;

private int size=0;

public DequeImpl() {

this.header = new DLNode();

this.tail = new DLNode();

this.size = 0;

header.setNext(tail);

tail.setPrevious(header);

}

@Override

public void insertFirst(Object obj) {

DLNode nextNode = header.getNext();

DLNode node = new DLNode(obj, header, nextNode);

nextNode.setPrevious(node);

header.setNext(node);

size++;

}

@Override

public void insertLast(Object obj) {

DLNode previous = tail.getPrevious();

DLNode node = new DLNode(obj, tail, previous);

previous.setNext(node);

tail.setPrevious(node);

size++;

}

@Override

public Object removeFirst() {

if (size() == 0)

return null;

DLNode first = header.getNext();

Object o = first.getElement();

DLNode node = first.getNext();

header.setNext(node);

node.setPrevious(header);

header = node;

size--;

return o;

}

@Override

public Object removeLast() {

if (size() == 0)

return null;

DLNode lastNode = tail.getPrevious();

Object o = lastNode.getElement();

DLNode node = lastNode.getPrevious();

node.setNext(tail);

tail.setPrevious(node);

size--;

return o;

}

@Override

public int size() {

return this.size;

}

}