Question

Given a singly-linked list interface and linked list node class, implement the singly-linked list which has the following methods in Java:

1. Implement 3 add() methods. One will add to the front (must be O(1)), one will add to the back (must be O(1)), and one will add anywhere in the list according to given index (must be O(1) for index 0 and O(n) for all other indices). They are: void addAtIndex(int index, T data), void addToFront(T data), void addToBack(T data)

2. Implement 4 remove() methods. One that will remove from the front (must be O(1)), one that will remove from the back (must be O(n)), one that will remove all occurences of a specific value from the list (must be O(n)), one that will remove at a particular given index (must be O(1) for index 0 and O(n) for all other indices). They are: T removeAtIndex(int index), T removeFromFront(), T removeFromBack, boolean removeAllOccurrences(T data)

3. Implement a method to get the element at a given index (must be O(1) for index 0 and O(n) for all other indices), return the list in the form of an array (must be O(n)), check if the given list is empty (must be O(1)), size of the list (must be O(1)), and method to clear the list (must be O(1)). They are: T get(int index), Object[] toArray(), boolean isEmpty(), int size(), void clear()

You are profided the interface for the Linked List called LinkedListInterface and the class for Linked List Node called LInkedListNode. The code for those two are below:

public interface LinkedListInterface {

    /**
     * Adds the element to the index specified.
     * Adding to indices 0 and {@code size} should be O(1), all other adds are
     * O(n).
     *
     * @param index The index where you want the new element.
     * @param data Any object of type T.
     * @throws java.lang.IndexOutOfBoundsException if index is negative
     * or index > size.
     * @throws java.lang.IllegalArgumentException if data is null.
     */
    public void addAtIndex(int index, T data);

    /**
     * Add a new node to the front of your linked list that holds the given
     * data. Make sure to update head.
     *
     * Must be O(1).
     *
     * @param data The data that the new node should hold.
     * @throws java.lang.IllegalArgumentException if data is null.
     */
    public void addToFront(T data);

    /**
     * Add a new node to the back of your linked list that holds the given data.
     * Make sure to update tail.
     *
     * Must be O(1).
     *
     * @param data The data that the new node should hold.
     * @throws java.lang.IllegalArgumentException if data is null.
     */
    public void addToBack(T data);

    /**
     * Returns the element at the given index.
     * This method must be O(1) for indices 0 and {@code size - 1}.
     * O(n) is expected for all other indices.
     *
     * @param index The index of the element
     * @return The object stored at that index.
     * @throws java.lang.IndexOutOfBoundsException if index < 0 or
     * index >= size.
     */
    public T get(int index);

    /**
     * Removes and returns the element at index.
     * This method should be O(1) for index 0, and O(n) in
     * all other cases.
     *
     * @param index The index of the element
     * @return The object that was formerly at that index.
     * @throws java.lang.IndexOutOfBoundsException if index < 0 or
     * index >= size.
     */
    public T removeAtIndex(int index);

    /**
     * Remove the front node from the list and return the data from it. If the
     * list is empty, return {@code null}.
     *
     * Must be O(1).
     *
     * @return The data from the front node or null.
     */
    public T removeFromFront();

    /**
     * Remove the back node from the list and return the data from it. If the
     * list is empty, return {@code null}.
     *
     * Must be O(n).
     *
     * @return The data from the last node or null.
     */
    public T removeFromBack();

    /**
     * Remove all occurrences of data in the linked list.
     *
     * Must be O(n).
     *
     * @param data The data to be removed from the list.
     * @return true if something was removed from the list; otherwise, false
     * @throws java.lang.IllegalArgumentException if data is null.
     */
    public boolean removeAllOccurrences(T data);

    /**
     * Return the linked list represented as an array of objects.
     *
     * Must be O(n).
     *
     * @return An array of length {@code size} holding each element in the same
     * order as it is in the linked list.
     */
    public Object[] toArray();

    /**
     * Return a boolean value representing whether or not the list is empty.
     *
     * Must be O(1).
     *
     * @return True if empty. False otherwise.
     */
    public boolean isEmpty();

    /**
     * Return the size of the list as an integer.
     *
     * Must be O(1).
     *
     * @return The size of the list.
     */
    public int size();

    /**
     * Clear the list.
     *
     * Must be O(1).
     */
    public void clear();

    /**
     * Reference to the head node of the linked list.
     * Normally, you would not do this, but we need it for grading your work.
     *
     * DO NOT USE THIS METHOD IN YOUR CODE.
     *
     * @return Node representing the head of the linked list.
     */
    public LinkedListNode getHead();

    /**
     * Reference to the tail node of the linked list.
     * Normally, you would not do this, but we need it for grading your work.
     *
     * DO NOT USE THIS METHOD IN YOUR CODE.
     *
     * @return Node representing the tail of the linked list.
     */
    public LinkedListNode getTail();
}

public class LinkedListNode {

    private T data;
    private LinkedListNode next;

    /**
     * Create a new LinkedListNode with the given data object and next node.
     *
     * @param data data to store in the node
     * @param next next node
     */
    public LinkedListNode(T data, LinkedListNode next) {
        this.data = data;
        this.next = next;
    }

    /**
     * Create a new LinkedListNode with the given data object and no next node.
     *
     * @param data data to store in this node
     */
    public LinkedListNode(T data) {
        this(data, null);
    }

    /**
     * Get the data stored in the node.
     *
     * @return data in this node.
     */
    public T getData() {
        return data;
    }

    /**
     * Get the next node.
     *
     * @return next node.
     */
    public LinkedListNode getNext() {
        return next;
    }

    /**
     * Set the next node.
     *
     * @param next new next node.
     */
    public void setNext(LinkedListNode next) {
        this.next = next;
    }

    @Override
    public String toString() {
        return "Node containing: " + data;
    }

}

Fill in your code in the given class below (this will be the answer):

public class SinglyLinkedList<T> implements LinkedListInterface<T> {

    // Do not add new instance variables.
    private LinkedListNode<T> head;
    private LinkedListNode<T> tail;
    private int size;

    @Override
    public void addAtIndex(int index, T data) {

    }

    @Override
    public T get(int index) {

    }

    @Override
    public T removeAtIndex(int index) {

    }

    @Override
    public void addToFront(T data) {

    }

    @Override
    public void addToBack(T data) {

    }

    @Override
    public T removeFromFront() {

    }

    @Override
    public T removeFromBack() {

    }

    @Override
    public boolean removeAllOccurrences(T data) {

    }

    @Override
    public Object[] toArray() {

    }

    @Override
    public boolean isEmpty() {

    }

    @Override
    public int size() {

    }

    @Override
    public void clear() {

    }

    @Override
    public LinkedListNode<T> getHead() {
        // DO NOT MODIFY!
        return head;
    }

    @Override
    public LinkedListNode<T> getTail() {
        // DO NOT MODIFY!
        return tail;
    }
}