How to write an implementation of a deque using doubly linked list?

I have the API and the requirements attached

I am also attaching the code I've written for reference, but it is getting NullPointerException for the removeLast Method.

import java.util.Iterator; import java.util.NoSuchElementException;

import stdlib.StdOut; import stdlib.StdRandom;

// A data type to represent a double-ended queue (aka deque), implemented using a doubly-linked // list as the underlying data structure. public class LinkedDeque implements Iterable { private Node first; private Node last; private int n; // Constructs an empty deque. public LinkedDeque() { first = null; last = null; n = 0; }

// Returns true if this deque is empty, and false otherwise. public boolean isEmpty() { return first == null; }

// Returns the number of items in this deque. public int size() { return n; }

// Adds item to the front of this deque. public void addFirst(Item item) { if (item == null) { throw new NullPointerException("item is null"); } Node oldfirst = first; first = new Node(); first.item = item; first.next = oldfirst; first.prev = null; if (last == null) { last = first; } n++; }

// Adds item to the back of this deque. public void addLast(Item item) { if (item == null) { throw new NullPointerException("item is null"); } Node oldlast = last; last = new Node(); last.item = item; last.prev = oldlast; last.next = null; if (first == null) { first = last; } n++; }

// Returns the item at the front of this deque. public Item peekFirst() { if(isEmpty()) { throw new NoSuchElementException("Deque is empty"); } return first.item; }

// Removes and returns the item at the front of this deque. public Item removeFirst() { Item item = first.item; if (isEmpty()) { throw new NoSuchElementException("Deque is empty"); } if (first.next == null) { first = null; last = null; } else { first = first.next; first.prev = null; } n--; return item; }

// Returns the item at the back of this deque. public Item peekLast() { if(isEmpty()) { throw new NoSuchElementException("Deque is empty"); } return last.item; }

// Removes and returns the item at the back of this deque. public Item removeLast() { Item item = last.item; if (isEmpty()) { throw new NoSuchElementException("Deque is empty"); } if (first.next == null) { first = null; last = null; } else { last = last.prev; last.next = null; } n--; return item; }

// Returns an iterator to iterate over the items in this deque from front to back. public Iterator iterator() { return new DequeIterator(); }

// Returns a string representation of this deque. public String toString() { StringBuilder sb = new StringBuilder(); for (Item item : this) { sb.append(item); sb.append(", "); } return n > 0 ? "[" + sb.substring(0, sb.length() - 2) + "]" : "[]"; }

// A deque iterator. private class DequeIterator implements Iterator { private Node current;

// Constructs an iterator. public DequeIterator() { current = first; }

// Returns true if there are more items to iterate, and false otherwise. public boolean hasNext() { return current != null; }

// Returns the next item. public Item next() { if (!hasNext()) { throw new NoSuchElementException("Iterator is empty"); } Item item = current.item; current = current.next; return item; }

// Unsupported method. public void remove() { throw new UnsupportedOperationException("remove() is not supported"); } }

// A data type to represent a doubly-linked list. Each node in the list stores a generic item // and references to the next and previous nodes in the list. private class Node { private Item item; // the item private Node next; // the next node private Node prev; // the previous node }

// Unit tests the data type. [DO NOT EDIT] public static void main(String[] args) { LinkedDeque deque = new LinkedDeque(); String quote = "There is grandeur in this view of life, with its several powers, having " + "been originally breathed into a few forms or into one; and that, whilst this " + "planet has gone cycling on according to the fixed law of gravity, from so simple" + " a beginning endless forms most beautiful and most wonderful have been, and are " + "being, evolved. ~ Charles Darwin, The Origin of Species"; int r = StdRandom.uniform(0, quote.length()); StdOut.println("Filling the deque..."); for (int i = quote.substring(0, r).length() - 1; i >= 0; i--) { deque.addFirst(quote.charAt(i)); } for (int i = 0; i Problem 1. (Deque) A double-ended queue or deque (pronounced "deck) is a generalization of a stack and a queue that supports adding and removing items from either the front or the back of the data structure. Create a generic, iterable data type called LinkedDeque that uses a doubly-linked list to implement the following deque API: E LinkedDeque LinkedDeque() boolean isEmpty() int size) void addFirst(Item item) void addLast(Item item) Item peekFirst() Item removeFirst() Item peeklast() Item removeLast() Iterator iterator) String toString() constructs an empty deque returns true if this deque empty, and false otherwise returns the number of items on this deque adds item to the front of this deque adds item to the back of this deque returns the item at the front of this deque removes and returns the item at the front of this deque returns the item at the back of this deque removes and returns the item at the back of this deque returns an iterator to iterate over the items in this deque from front to back returns a string representation of this deque Corner Cases The add*() methods should throw a NullPointerException("item is null") if item is null. The peek*() and remove*() methods should throw a NoSuchElementException("Deque is empty") if the deque is empty. The next() method in the deque iterator shoud throw a NoSuchelementException("Iterator is empty") if there are no more items to iterate. Performance Requirements The constructor and methods in LinkedDeque and DequeIterator should run in time T(n) ~ 1. its >- */workspace/project2 $ java LinkedDeque Filling the deque ... The de que (364 characters): There is grandeur in this view of life, with several powers, having been originally breathed into a few forms or into one; and that, whilst this planet has gone cycling on according to the fixed law of gravity, from so simple a beginning endless forms most beautiful and most wonderful have been, and are being, evolved. Charles Darwin, The Origin of Species Emptying the deque ... de que.isEmpty()? true Problem 1. (Deque) Hints: Use a doubly-linked list Node to implement the API each node in the list stores a generic item, and references next and prey to the next and previous nodes in the list null itemi item2 item3 item null Instance variables Reference to the front of the deque, Node first Reference to the back of the deque, Node last Size of the deque, int n LinkedDeque() Initialize instance variables to appropriate values boolean isEmpty Return whether the deque is empty or not . int size Return the size of the deque Problems void addFirst(Item item) Add the given item to the front of the deque Increment n by one void addLast(Item item) Add the given item to the back of the deque Increment n by one Item peekFirst Return the item at the front of the deque Item removeFirst Remove and return the item at the front of the deque Decrement n by one Item peek Last Return the item at the back of the deque . Problems Item removeLaat Remove and return the item at the back of the deque Decrement by one Iterator iterator() Return an object of type DequeIterator LinkedDeque :: DequeIterator Instance variable Reference to current node in the iterator, Node current DequeIterator) Initialize instance variable appropriately boolean hasNext() Return whether the iterator has more items to iterate or not Item next() Return the item in current and advance current to the next node