The LinkedList class implements both the List interface and the Stack interface, but several methods (listed below) are missing bodies.You have to complete the missing bodies in order for it to show the given output. Do not change the interfaces. Do not change the public method headers. Do not rename the LinkedList class. None of your methods should print anything to the console. All of the printing happens in HW1.java. Any method that adds or removes an element should update size appropriately. PLEASE PROVIDE CODE THAT HAS NO ERRORS AND PRODUCES THE OUTPUT AS SAME AS THE ONE PROVIDED. THANK YOU VERY MUCH!

---------------------------------------------------------------------------------------------------------- import java.util.NoSuchElementException; public class LinkedList implements List, Stack { private Node first, last; private int size = 0; // Construct a new empty list. public LinkedList() { first = last = new Node<>(null, null); } // Adds element e to the end of the list. public void add(E e) { last.next = new Node<>(e, null); last = last.next; ++size; } // Returns the element at the specified index, // or throws an IndexOutOfBoundsException if the index is out of range. public E get(int index) { if (index < 0 || index >= size) throw new IndexOutOfBoundsException(); Node t = first.next; for (int i = 0; i < index; ++i) t = t.next; return t.data; } // Returns a string representation of the linked list. public String toString() { // Fill in. } // Removes all elements. public void clear() { // Fill in. } // Removes the first occurrence of the specified element, if it is present. // Returns true if the list has been modified. public boolean remove(E e) { // Fill in. } // Returns the number of elements. public int size() { return size; } // Adds element e to the top of the stack. public void push(E e) { // Fill in. } // Removes and returns the top element of the stack, // or throws a NoSuchElementException if the stack is empty. public E pop() { // Fill in. } // Returns but does not remove the top element of the stack, // or throws a NoSuchElementException if the stack is empty. public E top() { // Fill in. } private static class Node { E data; Node next; Node(E data, Node next) { this.data = data; this.next = next; } } }

-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

public interface List { // Adds the specified element to the end of the list. void add(E e); // Returns the element at the specified index, // or throws an IndexOutOfBoundsException if the index is out of range. E get(int index); // Removes all elements and sets size to 0. public void clear(); // Removes the first occurrence of the specified element, if it is present. // Returns true if the list has been modified. boolean remove(E e); // Returns the number of elements. int size(); }

-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------

public interface Stack { // Adds element e to the top of the stack. void push(E e); // Removes and returns the top element of the stack, // or throws a NoSuchElementException if the stack is empty. E pop(); // Returns but does not remove the top element of the stack, // or throws a NoSuchElementException if the stack is empty. E top(); // Returns the number of elements. int size(); }

-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------

public class HW1 { public static void main(String[] args) { List list = new LinkedList<>(); list.add(3); // [3] list.add(5); // [3, 5] list.add(7); // [3, 5, 7] System.out.println(list); list.remove(new Integer(7)); // [3, 5] list.add(9); // [3, 5, 9] for (int i = 0; i < list.size(); ++i) System.out.print(list.get(i) + " "); System.out.println(); list.clear(); System.out.println(list); System.out.println(); System.out.println(); Stack stack = new LinkedList<>(); stack.push(3); // [3] stack.push(5); // [5, 3] stack.push(7); // [7, 5, 3] System.out.println(stack); System.out.println(stack.top()); stack.pop(); // [5, 3] System.out.println(stack); } }

-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Output:

[3, 5, 7] 3 5 9 [] [7, 5, 3] 7 [5, 3]