In Java, add the following methods to the Java code below: a. Write a new method
ID: 3604095 • Letter: I
Question
In Java, add the following methods to the Java code below:
a. Write a new method named remove(E item) that removes and returns the first item in the list that is equivalent to the specified object. If the list does not contain such an item, the method should return null.
b. Write a new method named reverse() that reverses the order of the nodes in the calling list. (There are several ways you can do this, some of which are more efficient than others! As long as your solution works, it’s acceptable for this assignment. But if possible, try to make your solution run in O(n) time.)
c. Write a new method named toArrayList() that returns an ArrayList object containing all elements in the calling list, in the same order (i.e., the head node’s data should be stored in index 0 of the returned array list). Use your ArrayList class from the first part of this assignment. If the calling list is empty, just return an ArrayList of size 0.
Java Code:
public class LinkedList implements List {
// Node is written as a private nested class of LinkedList, since we don't
// intend to use Node outside of this class. This way, LinkedList has
// direct access to the instance variables of Node.
private static class Node { // "static" means that Node does *not* have access to the instance variables of LinkedList
private E data;
private Node next;
// Constructor (generated automatically through Eclipse)
public Node(E data, Node next) {
super();
this.data = data;
this.next = next;
}
}
private Node head; // Maintains the location of the head node
private int size = 0; // Number of elements in the list
// Big-O: O(n) due to the call to nodeAt
@Override
public E get(int index) {
return nodeAt(index).data;
}
// Big-O: O(n) due to the call to nodeAt
@Override
public void set(int index, E newValue) {
nodeAt(index).data = newValue;
}
// Big-O: O(1) if adding to the head of the list, O(n) if adding to the tail
@Override
public void add(E newValue) {
if (size == 0)
head = new Node<>(newValue, null);
else
nodeAt(size - 1).next = new Node<>(newValue, null);
size++;
}
// Big-O: O(1) if removing from the head of the list, O(n) for other locations
@Override
public E remove(int index) {
E temp;
if (index == 0) {
temp = head.data;
head = head.next;
} else {
Node nodeBefore = nodeAt(index - 1);
temp = nodeBefore.next.data;
nodeBefore.next = nodeBefore.next.next;
}
size--;
return temp;
}
// Returns the Node object at the specified index in the list.
// Throws an IndexOutOfBoundsException if the index is invalid.
// Big-O: O(n)
private Node nodeAt(int index) {
if (index >= 0 && index < size) {
Node temp = head;
for (int i = 0; i < index; i++)
temp = temp.next;
return temp;
} else
throw new IndexOutOfBoundsException();
}
public String toString() {
String r = "LinkedList (size = " + size + "), containing: head -> ";
for (Node temp = head; temp != null; temp = temp.next)
r += temp.data + " -> ";
r += "null";
return r;
}
public static void main(String[] args) {
LinkedList myList = new LinkedList<>();
System.out.println(myList);
myList.add("stuff");
myList.add("four");
myList.add("for");
myList.add("fore");
myList.add("fo");
myList.add("faux");
myList.add("4");
System.out.println(myList);
myList.remove(4);
myList.remove(0);
myList.remove(1);
System.out.println(myList);
}
}
Explanation / Answer
Java Code:
public class LinkedList implements List {
// Node is written as a private nested class of LinkedList, since we don't
// intend to use Node outside of this class. This way, LinkedList has
// direct access to the instance variables of Node.
private static class Node { // "static" means that Node does *not* have access to the instance variables of LinkedList
private E data;
private Node next;
// Constructor (generated automatically through Eclipse)
public Node(E data, Node next) {
super();
this.data = data;
this.next = next;
}
}
private Node head; // Maintains the location of the head node
private int size = 0; // Number of elements in the list
// Big-O: O(n) due to the call to nodeAt
@Override
public E get(int index) {
return nodeAt(index).data;
}
// Big-O: O(n) due to the call to nodeAt
@Override
public void set(int index, E newValue) {
nodeAt(index).data = newValue;
}
// Big-O: O(1) if adding to the head of the list, O(n) if adding to the tail
@Override
public void add(E newValue) {
if (size == 0)
head = new Node<>(newValue, null);
else
nodeAt(size - 1).next = new Node<>(newValue, null);
size++;
}
// Big-O: O(1) if removing from the head of the list, O(n) for other locations
@Override
public E remove(int index) {
E temp;
if (index == 0) {
temp = head.data;
head = head.next;
} else {
Node nodeBefore = nodeAt(index - 1);
temp = nodeBefore.next.data;
nodeBefore.next = nodeBefore.next.next;
}
size--;
return temp;
}
// Returns the Node object at the specified index in the list.
// Throws an IndexOutOfBoundsException if the index is invalid.
// Big-O: O(n)
private Node nodeAt(int index) {
if (index >= 0 && index < size) {
Node temp = head;
for (int i = 0; i < index; i++)
temp = temp.next;
return temp;
} else
throw new IndexOutOfBoundsException();
}
public String toString() {
String r = "LinkedList (size = " + size + "), containing: head -> ";
for (Node temp = head; temp != null; temp = temp.next)
r += temp.data + " -> ";
r += "null";
return r;
}
public static void main(String[] args) {
LinkedList myList = new LinkedList<>();
System.out.println(myList);
myList.add("stuff");
myList.add("four");
myList.add("for");
myList.add("fore");
myList.add("fo");
myList.add("faux");
myList.add("4");
System.out.println(myList);
myList.remove(4);
myList.remove(0);
myList.remove(1);
System.out.println(myList);
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.