Question

Language: Java

Topic: Deques

Using the following variables/class:

public class LinkedDeque<T> {

// Do not add new instance variables or modify existing ones.
private LinkedNode<T> head;
private LinkedNode<T> tail;
private int size;

Q1: Write a method called "public void addFirst(T data)" that does the following:

* Adds the element to the front of the deque.

* Must be O(1)

* @param data the data to add to the front of the deque

* @throws java.lang.IllegalArgumentException if data is null

Q2: Write a method called "public void addLast(T data)" that does the following:

* Adds the element to the back of the deque.

* Must be O(1)

* @param data the data to add to the back of the deque

* @throws java.lang.IllegalArgumentException if data is null

Answer 1

Here is the completed code for this problem. Comments are included, go through it, learn how things work and let me know if you have any doubts or if you need anything to change. If you are satisfied with the solution, please rate the answer. Thanks

Assumptions: This is based on singly linked list and LinkedNode contains a data field and next field, a constructor that takes value for data field and initializes next to null.

//method to add an element to the front

public void addFirst(T data) {

      // throwing exception if data is null

      if (data == null) {

            throw new IllegalArgumentException();

      }

      // creating a new node, assuming there exists a constructor for

      // LinkedNode that takes a value of type T

      LinkedNode<T> newNode = new LinkedNode<T>(data);

      // adding as both head and tail node if dequeue is currently empty

      if (size == 0) {

            head = newNode;

            tail = newNode;

      } else {

            // setting head as next of newNode, assuming there exists a field

            // called next in LinkedNode class which is directly accessible

            newNode.next = head;

            // updating head node

            head = newNode;

      }

      // updating size

      size++;

}

// method to add an element to the tail

public void addLast(T data) {

      // throwing exception if data is null

      if (data == null) {

            throw new IllegalArgumentException();

      }

      LinkedNode<T> newNode = new LinkedNode<T>(data);

      // adding as both head and tail node if dequeue is currently empty

      if (size == 0) {

            head = newNode;

            tail = newNode;

      } else {

            // appending to tail node and updating tail node

            tail.next = newNode;

            tail = newNode;

      }

      // updating size

      size++;

}