I have a problem with the following code. The remove method in the class LinkedList does not work the way I need it to. When compiled using the HW1 class the output should be:

3 5 7 5 7 7 //the problem is here. 5 9

7 5 3 3 5 7 3 5 7

But instead I get:

3 5 7 5 7 5 // 5 is printed instead of 7 5 9

7 5 3 3 5 7 3 5 7

This is because the code System.out.println(list.remove(1)); is supposed to print the element that is removed, but the method remove does not print the correct element. It does remove the correct element, but it prints some other element. I need help fixing the remove method in class LinkedList. Nothing else from any other class should be changed. This is important. The only class that can be changed is LinkedList to fix the remove method. Thank you for any assistance.

import java.util.ArrayList;

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) {

Node temp = new Node<>(e, null);

if(size == 0) {

first = temp;

last = first;

last.next = null;

++size;

return;

}

last.next = temp;

last = last.next;

last.next = null;

++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;

for (int i = 0; i < index; ++i)

t = t.next;

return t.data;

}

// Removes and returns the element at the specified index,

// or throws an IndexOutOfBoundsException if the index is out of range.

public E remove(int index) {

if(index < 0 || index >= size)

throw new IndexOutOfBoundsException("Index out of bound.");

Node temp = first;

if(index == 0) {

--size;

first = first.next;

return temp.data;

}

// Find previous node of the node to be deleted

for (int i=0; i

temp = temp.next;

// Node temp->next is the node to be deleted

// Store pointer to the next of node to be deleted

Node next = temp.next.next;

temp.next = next; // Unlink the deleted node from list

--size;

Node t = first;

while(t.next != null) {

t = t.next;

}

last = t;

return temp.data;

}

// Adds element e to the top of the stack.

public void push(E e) {

Node temp = new Node<>(e, null);

if(size == 0) {

first = last = temp;

last.next = null;

++size;

return;

}

temp.next = first;

first = temp;

++size;

}

// Removes and returns the top element of the stack, or returns null if the stack is empty.

public E pop() {

if(size == 0) {

return null;

}

Node temp = first;

first = first.next;

--size;

return temp.data;

}

// Returns but does not remove the top element of the stack, or returns null if the stack is empty.

public E top() {

return first.data;

}

// Reverses the order of all the elements of the stack.

public void reverse() {

ArrayList list = new ArrayList<>();

while(size != 0) {

list.add(pop());

}

for(E item : list) {

push(item);

}

}

// Returns a string representation of the linked list.

public String toString() {

String str = "";

Node temp = first;

while(temp != null) {

str += temp.data.toString() + " ";

temp = temp.next;

}

return str;

}

// Returns the number of elements.

public int size() {

return size;

}

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 and returns the element at the specified index, // or throws an IndexOutOfBoundsException if the index is out of range. E remove(int index); // 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 returns null if the stack is empty. E pop(); // Returns but does not remove the top element of the stack, or returns null if the stack is empty. E top(); // Reverses the order of all the elements of the stack. void reverse(); // 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(0); // [5, 7] System.out.println(list); System.out.println(list.remove(1));; // this line is supposed to remove 7, which it does and print it, but 5 is printed. list.add(9); // [5, 9] for (int i = 0; i < list.size(); ++i) System.out.print(list.get(i) + " "); 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); stack.reverse(); // [3, 5, 7] System.out.println(stack); System.out.println(stack.top()); stack.pop(); // [5, 7] System.out.println(stack); } }