LinkedDeque.java

package edu.caltech.cs2.datastructures;


import edu.caltech.cs2.interfaces.IDeque;
import edu.caltech.cs2.interfaces.IQueue;
import edu.caltech.cs2.interfaces.IStack;

import java.util.Iterator;

public class LinkedDeque<E> implements IDeque<E>, IQueue<E>, IStack<E> {
    private Node<E> head;
    private int size;
    private Node<E> tail;

    public LinkedDeque(){
        this.head = null;
        this.tail = null;
        this.size = 0;
    }

    private static class Node<E> {
        public final E data;
        public Node<E> next;
        public Node<E> prev;

        public Node(E data) {
            this(data, null, null);
        }

        public Node(E data, Node<E> next, Node<E> prev) {
            this.data = data;
            this.next = next;
            this.prev = prev;
        }
    }

    @Override
    public void addFront(E e) {
        if (this.size == 0){
            Node<E> tempNode = new Node<>(e);
            this.tail = tempNode;
            this.head = tempNode;
        } else {
            Node<E> tempHead = new Node<>(e, this.head, null);
            // previous is this head
            this.head.prev = tempHead;
            //switch node
            this.head = tempHead;
        }
        this.size++;
    }

    @Override
    public void addBack(E e) {
        if (this.size == 0){
            this.head = new Node<>(e);
            this.tail = this.head;
        } else {
            Node<E> tempTail = new Node<>(e, null, this.tail);
            this.tail.next = tempTail;
            this.tail = tempTail;
        }
        this.size++;
    }

    @Override
    public E removeFront() {
        if (this.size == 0) {
            return null;
        }
        E tempHead = this.head.data;
        this.head = this.head.next;
        if (this.head != null) {
            this.head.prev = null;
        }
        this.size--;
        if (this.size == 0) {
            this.tail = this.head;
        }
        return tempHead;
    }

    @Override
    public E removeBack() {
        if (this.size == 0) {
            return null;
        }
        E tempHead = this.tail.data;
        this.tail = this.tail.prev;
        if (this.tail != null) {
            this.tail.next = null;
        }
        this.size--;
        if (this.size == 0) {
            this.head = this.tail;
        }
        return tempHead;
    }

    @Override
    public boolean enqueue(E e) {
        addFront(e);
        return true;
    }

    @Override
    public E dequeue() {
        if (this.head == null || this.tail == null){
            return null;
        } else {
            return removeBack();
        }
    }

    @Override
    public boolean push(E e) {
        addBack(e);
        return true;
    }

    @Override
    public E pop() {
        if (this.head == null || this.tail == null){
            return null;
        } else {
            return removeBack();
        }
    }

    @Override
    public E peekFront() {
        if (this.size == 0){
            return null;
        }
        return this.head.data;
    }

    @Override
    public E peekBack() {
        if (this.size == 0) {
            return null;
        }
        return this.tail.data;
    }

    @Override
    public E peek() {
        return peekBack();
    }

    @Override
    public Iterator<E> iterator() {
        return new LinkedDequeIterator();
    }

    @Override
    public int size() {
        return this.size;
    }

    @Override
    public String toString(){
        String returnStatement = "";
        if (this.size == 0) {
            return "[]";
        }
        else {
            returnStatement += "[";
            Node<E> tempNode = this.head;
            for (int i = 0; i < this.size; i++){
                returnStatement += tempNode.data.toString();
                returnStatement += ", ";
                tempNode = tempNode.next;
            }
            returnStatement = returnStatement.substring(0, returnStatement.length() - 2);
            returnStatement += "]";
            return returnStatement;
        }


    }

    private class LinkedDequeIterator implements Iterator<E> {
        private Node<E> currNode = null;

        public LinkedDequeIterator(){
            this.currNode = LinkedDeque.this.head;
        }

        @Override
        public boolean hasNext() {
            return this.currNode != null;
        }

        @Override
        public E next() {
            E element = currNode.data;
            this.currNode = currNode.next;
            return element;
        }
    }
}