Question

NO ONE HAS PROVIDED THE CORRECT CODE TO PROVIDE THE GIVEN OUTPUT. PLEASE PROVIDE CODE THAT WOULD CAUSE THE HW1.java TO PRINT THE RIGHT DATA.!!!

The LinkedList class implements both the List interface and the Stack interface, but several methods (listed below) are missing bodies. Write the code so it works correctly. You should submit one file, LinkedList.java.

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.

public String toString()
Returns a String representation of the linked list.
Examples of acceptable formats are "[1, 2, 3]", "[1,2,3]", "[ 1 2 3 ]", "1 2 3".

public void clear()
Removes all elements.

public boolean remove(E e)
Removes the first occurrence of the specified element, if it is present. For example, remove(7) removes the first element equal to 7 (use the equals method to compare elements).
Returns true if the list has been modified, or return false if the list has not been modified.
If the node you removed is the last node, don't forget to update last.

public void push(E e)
Adds element e to the top of the stack.
push and pop must happen on the same side.
The "top" to be at the beginning of the linked list, because there's no efficient way to remove the last node of a singly-linked list.

public E pop()
Removes and returns the top element of the stack, or throws a NoSuchElementException if the stack is empty.

public E top()
Returns but does not remove the top element of the stack, or throws a NoSuchElementException if the stack is empty.

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

import java.util.NoSuchElementException;

public class LinkedList<E> implements List<E>, Stack<E> {
   private Node<E> 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<E> 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> {
      E data;
      Node<E> next;
      Node(E data, Node<E> next) {
         this.data = data;
         this.next = next;
      }
   }
}

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

public interface List<E> {
   // 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<E> {
   // 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<Integer> 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<Integer> 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);
   }
}

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

THE CODE SHOULD OUTPUT THIS AND IT SHOULD NOT HAVE ANY ERRORS PLEASE!

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


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

Answer 1

LinkedList.java

import java.util.NoSuchElementException;

public class LinkedList<E> implements List<E>, Stack<E> {
private Node<E> first, last;
private int size = 0;

// Construct a new empty list.
public LinkedList() {
first = last = null; // list is empty
}

// Adds element e to the end of the list.
public void add(E e) {
   if(first==null) { // if list is empty add as first
       first=last=new Node<>(e, null);
   } else { // otherwise add at last
   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<E> t = first; // 0th element
for (int i = 0; i < index; ++i) {
   t = t.next;
}
return t.data;
}

// Returns a string representation of the linked list.
public String toString() {
StringBuilder sb = new StringBuilder();
Node<E> n = first;
while(n!=null) {
   if(sb.length()==0) { // if string is empty add no comma
   } else { // otherwise append comma
       sb.append(",");
   }
       sb.append(n.data);
   n=n.next;
}
return "["+sb.toString()+"]";
}

// Removes all elements.
public void clear() {
first=last=null;//reset first, last and size
size=0;
}

// 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) {
   Node<E> n = first, prev=null;
   if(first.data.equals(e)) { // e is in the first node
       if(first==last) { // if list is having only one node containing e
           first=last=null;
           size=0;
       } else { //otherwise
           first=first.next;
           n.next=null;
           size--;
       }
       return true;
   }
   prev=n;
   n=n.next;
while(n!=null) { // until n reaches to end
   if(n.data.equals(e)) { // if n contains e then unlink e from list
       prev.next=n.next;
       n.next=null;
       if(n==last) { // if n is the last node
           last=prev;
       }
       size--;
       return true;
   }
   prev = n;
   n=n.next;
}
return false;
}

// Returns the number of elements.
public int size() {
return size;
}

// Adds element e to the top of the stack.
public void push(E e) { // add e in head
if(first==null) {
   first=last=new Node<>(e, null);
} else {
   first = new Node<>(e, first);
}
size++;
}

// Removes and returns the top element of the stack,
// or throws a NoSuchElementException if the stack is empty.
public E pop() {
   if(first==null) { // if list is already empty
       throw new NoSuchElementException();
   }
   // unlink and return first node set next node as head
Node<E> n = first;
first=first.next;
n.next=null;
size--;
return n.data;
}

// Returns but does not remove the top element of the stack,
// or throws a NoSuchElementException if the stack is empty.
public E top() {
   if(first==null) {// if list is already empty
       throw new NoSuchElementException();
   }
   //return value of first node;
return first.data;
}

private static class Node<E> {
E data;
Node<E> next;
Node(E data, Node<E> next) {
this.data = data;
this.next = next;
}
}
}

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

I had to change some existing method also

When we using as linkedlist, it is inserting at last and removing from anywhere. But when the same LinkedList class using as Stack, then first node is acting as stack top. we are pushing at first and popping from first.

below are the states after each steps for linkedlist and stack