DoublyLinkedList

public class DoublyLinkedList<T> {

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

    // Do not add a constructor.

    /**
     * Adds a node to the front of the list.
     *
     * Time Complexity: O(1).
     *
     * @param data  the data of the new node to add to the front of the list
     * @throws      IllegalArgumentException if data is null
     */
    public void addToFront(T data) {

        if (data == null) {
            throw new IllegalArgumentException("Cannot add null data");
        }

        Node<T> newNode = new Node<>(data);
        if (size == 0) {
            head = tail = newNode;
        }
        else {
            head.setPrevious(newNode);
            newNode.setNext(head);
            head = newNode;
        }
        size++;
    }
    /**
     * Adds a node to the back of the list.
     *
     * Time Complexity: O(1).
     *
     * @param data  the data of the new node to add to the back of the list
     * @throws      IllegalArgumentException if data is null
     */
    public void addToBack(T data) {
        if (data == null) {
            throw new IllegalArgumentException("Cannot add null data");
        }

        Node<T> newNode = new Node<>(data);
        if (size == 0) {
            head = tail = newNode;
        }
        else {
            tail.setNext(newNode);
            newNode.setPrevious(tail);
            tail = newNode;
        }

        size++;
    }

    /**
     * Adds a node to the specified index.
     *
     * Time Complexity: O(n) in general, O(1) when index is 0 or size.
     *
     * @param index  the index at which to add the new node
     * @param data   the data of the new node to add at the specified index
     * @throws       IndexOutOfBoundsException if index < 0 or index > size
     * @throws       IllegalArgumentException  if data is null
     */
    public void addAtIndex(int index, T data) {
        if (index < 0 || index > size) {
            String errMsg = String.format("Cannot add at index %d", index);
            throw new IndexOutOfBoundsException(errMsg);
        }

        if (data == null) {
            throw new IllegalArgumentException("Cannot add null data");
        }

        if (index == 0) {
            addToFront(data);
        }

        else if (index == size) {
            addToBack(data);
        }
        else
        {
            Node<T> newNode = new Node<>(data);
            Node<T>  node = head;
            for (int i = 0; i < index-1; i++) {
                node = node.getNext();
            }
            newNode.setNext(node.getNext());
            node.getNext().setPrevious(newNode);
            node.setNext(newNode);
            newNode.setPrevious(node);
            size++;
        }
    }
    /**
     * Removes the first node of the list and returns its data.
     *
     * Time Complexity: O(1).
     *
     * @return  the data formerly located at the front of the list, null if the list is empty
     */
    public T removeFromFront() {
        if(size == 0)
            return null;
        T data =head.getData();
        if (size==1) {
            head=tail=null;}
        else {
            head=head.getNext();
            head.setPrevious(null); // line added
        }
        size--;
        // Replace this line with your return statement
        return data;
    }


    /**
     * Removes the last node of the list and returns its data.
     *
     * Time Complexity: O(1).
     *
     * @return  the data formerly located at the back of the list, null if the list is empty
     */
    public T removeFromBack() {
        if(size == 0)
            return null;
        T data =tail.getData();


        if (size==1) {
            head=tail=null;}
        else {

            tail=tail.getPrevious();
            tail.setNext(null);
        }
        size--;
        // Replace this line with your return statement
        return data;
    }


    /**
     * Removes the node at the specified index and returns its data.
     *
     * Time Complexity: O(n) in general, O(1) when index is 0 or size-1.
     *
     * @param index  the index of the node to remove
     * @return       the data formerly located at the specified index
     * @throws       IndexOutOfBoundsException if index < 0 or index >= size
     */
    public T removeAtIndex(int index) {
        if (index < 0 || index >= size) {
            String errMsg = String.format("Cannot add at index %d", index);
            throw new IndexOutOfBoundsException(errMsg);
        }

        if (index == 0) {
            return removeFromFront();
        }
        else if (index==size-1) {
            return removeFromBack(); // line added
        }
        else
        {
            Node<T> node = head;

            for (int i = 0; i < index-1; i++) {
                node = node.getNext();
            }
            T data=node.getNext().getData();

            Node<T> temp = node.getNext().getNext();

            node.setNext(temp);
            temp.setPrevious(node);

            size--;
            // Replace this line with your return statement
            return data;
        }
    }


    /**
     * Returns the data of the node at the specified index.
     *
     * Time Complexity: O(n) in general, O(1) when index is 0 or size-1.
     *
     * @param index  the index of the node to get data from
     * @return       the data of the node at the specified index in the list
     * @throws       IndexOutOfBoundsException if index < 0 or index >= size
     */
    public T get(int index) {
        if (index < 0 || index >= size) {
            String errMsg = String.format("Cannot get at index %d", index);
            throw new IndexOutOfBoundsException(errMsg);
        }

        if(index==0) {
            return head.getData();
        }
        else if (index==size-1) {
            return tail.getData();
        }

        if(index < size/2) //Starting from the front
        {
            Node<T> nodeH = head.getNext();
            for(int i = 1; i < index; i++) {
                nodeH = nodeH.getNext();
            }
            return nodeH.getData();
        }
        else //Starting from the back
        {
            Node<T> node = tail;
            for(int i = size-1 ; i > index; i--) {
                node = node.getPrevious();
            }
            return node.getData();
        }
    }





    /**
     * Removes from the list the LAST NODE containing a copy of the given data.
     *
     * Time Complexity: O(n) in general, O(1) if data is in the tail.
     *
     * @param data  the data to be removed from the list
     * @return      true if data is found in the list, false otherwise
     * @throws      IllegalArgumentException if data is null
     */
    public boolean removeLastOccurrence(T data) {
        if(size == 0)
            throw new IllegalArgumentException("Cannot remove null data");
        if(tail.getData().equals(data)) {
            removeFromBack();
            return true;
        }
        else if(head.getData().equals(data)) {
            removeFromFront();
            return true;
        }
        else if (size>1)
        {
            Node<T> temp = head;
            for(int i =0;i<size-1;i++) {

                if(temp.getData().equals(data)) {
                    removeAtIndex(i);
                    return true;
                }
                else
                    temp=temp.getNext();
            }
        }
        // Replace this line with your return statement
        return false;
    }


    /**
     * Checks whether the list contains the given data.
     *
     * Time Complexity: O(n)
     *
     * @param data  the data to search for
     * @return      true if data is found in the list, false otherwise
     */
    public boolean contains(T data) {
        //if(data == null) return false;

        Node<T> node = head;
        if(data.equals(tail.getData())) // when the data is on the tail
            return true;

        while(node.getNext() != null ) {
            if(data.equals(node.getData())) {
                return true;
            }
            else {
                node=node.getNext();
            }
        }
        // Replace this line with your return statement
        return false;
    }


    /**
     * Clears all the data and resets the size of the list.
     *
     * Time Complexity: O(1).
     */
    public void clear() {
        head=null;
        tail=null;
        size=0;
    }
    /**
     * Returns the head node of the list.
     *
     * For grading purposes only. You shouldn't need this method since
     * you have direct access to the variable.
     *
     * @return the node at the head of the list
     */
    public Node<T> getHead() {
        // DO NOT MODIFY!
        return head;
    }

    /**
     * Returns the tail node of the list.
     *
     * For grading purposes only. You shouldn't need this method since
     * you have direct access to the variable.
     *
     * @return the node at the tail of the list
     */
    public Node<T> getTail() {
        // DO NOT MODIFY!
        return tail;
    }

    /**
     * Returns the size of the list.
     *
     * For grading purposes only. You shouldn't need this method since
     * you have direct access to the variable.
     *
     * @return the size of the list
     */
    public int size() {
        // DO NOT MODIFY!
        return size;
    }

    public void print() {
        Node<T> node = head;
        while (node != null) {
            System.out.print(node.getData() + " ");
            node = node.getNext();
        }
        System.out.println();
    }