Design and implement a LinkedList that can be served as a Double ended Queue
Author: Mohammad J Iqbal
The LinkedList at java.util implements Deque interface and it is a Double ended Queue. Then why are we going to write our simple LinkedList? Apart from poll/removeFirst and push/addLast in O(1) time complexity, we need to be able to delete a node anywhere in the list in O(1) time when passing the node inside the remove method as parameter.
#Double Ended Queue: A double-ended queue (abbreviated to deque) is an abstract data type that generalizes a queue, for which elements can be added to or removed from either the front (head) or back (tail)
In the diagram above, we can add new elements in the front/head of the list, we can add element in the rear/tail of the list or we can add in the middle, for our implementation we don’t need to add in the middle but we need to be able to remove node from middle apart from front and rear and the time complexity should be O(1) for that remove operation. For queue(First In First Out) operation we have two choices, since its double ended queue. Either we can use removeFirst for pop operation and addLast for push operation or we can use addFirst and removeLast.
Let’s consider we are using removeFirst as poll and addLast as Push.
The queue will then grow like this: 1–> 2–> 3–> 4–>5
Calling Poll() will remove 1 from the list, which makes sense as 1 came first in the queue.
Calling Poll() will remove 2 from the list.
After these two poll operation, our queue will look like this: 3–> 4–>5
Calling Push(6) will add 6 in the end of the queue: 3–> 4–>5–>6
If we call poll it will remove 3 from the queue: 4–>5–>6
Let’s start the design by writing a Deque interface
package com.spsoft.list;
/* FIFO Double Ended Queue */
public interface Deque<E> {
public Node<E> addLast(E e);
public Node<E> addLast(Node<E> node);
public E removeFirst();
public void remove(Node<E> node);
public boolean offer(E e);
public E poll();
public E peek();
public int size();
public boolean isEmpty();
public Node<E> addFirst(E e);
public E removeLast();
}
We will be using the below linked list Node for our implementation:
package com.spsoft.list;
public class Node<E> {
public E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E item,Node<E> next) {
this.item = item;
this.next = next;
this.prev = prev;
}
}
Now we can write our LinkedList class that implements Deque Interface.
package com.spsoft.list;
import java.util.NoSuchElementException;
public class LinkedList<E> implements Deque<E> {
int size = 0;
Node<E> first;
Node<E> last;
@Override
public Node<E> addLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
System.out.println("added Node valued: "+e+" at the end of list");
return newNode;
}
@Override
public Node<E> addLast(Node<E> node) {
final Node<E> l = last;
last = node;
if (l == null)
first = node;
else
l.next = node;
size++;
System.out.println("added Node valued: "+node.item +" at the end of list");
return node;
}
public E removeFirst(){
final Node<E> f = first;
if(f == null)
throw new NoSuchElementException();
return removeFirst(f);
}
@Override
public void remove(Node<E> node) {
Node<E> prev = node.prev;
Node<E> next = node.next;
if(prev != null)
prev.next = node.next;
if(next != null)
next.prev = prev;
if(node == last)
last = node.prev;
if(node == first)
first = node.next;
size--;
System.out.println("removed node valued: "+node.item);
}
@Override
public boolean offer(E e) {
addLast(e);
return true;
}
@Override
public E poll() {
final Node<E> f = first;
return (f == null) ? null : removeFirst(f);
}
@Override
public E peek() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
@Override
public int size() {
return size;
}
@Override
public boolean isEmpty() {
return size==0;
}
@Override
//needs to implement
public Node<E> addFirst(E e) {
return null;
}
@Override
//needs to implement
public E removeLast() {
return null;
}
private E removeFirst(Node<E> f) {
assert f == first && f != null;
final E element = f.item;
final Node<E> next = f.next;
first = next;
if (next == null)
last = null;
else
next.prev = null;
size--;
System.out.println("removed node valued: "+f.item +" from the start of the list");
return element;
}
}
Finally a Driver class that will test the LinkedList:
package com.spsoft.list;
public class LinkedListTest {
private static LinkedList<Character> linkedList = new LinkedList<Character>();
public static void main(String args[]){
linkedList.addLast('a');
Node<Character> nodeB = linkedList.addLast('b');
System.out.println("size of linked list: "+linkedList.size());
linkedList.removeFirst();
System.out.println("size of linked list: "+linkedList.size());
linkedList.remove(nodeB);
System.out.println("size of linked list: "+linkedList.size());
linkedList.addLast('c');
System.out.println("size of linked list: "+linkedList.size());
}
}
