Create a new Java project called Project. To this project you'll be adding several classes:

I. GameCharacter

Create a class GameCharacter that has a single member variable: a String storing the character's name. In this class, you should have the following methods:

A single-parameter constructor which sets the name.

Override the toString() method from the Object class

Override the equals() method from the Object class

IMPORTANT: in order to correctly override this method, you must use the signature "public boolean equals(Object other)"

II. SinglyLinkedList

Add this SinglyLinkedList class and modify it as follows:

Change it to use generics.

Add a method remove(ValueType e), which takes an element e to remove.

It should remove the first node whose value is equal to e. (Hint: use the equals()method)

This method should return true if a node was removed. (e was in the list)

This method should return false if no node was removed. (e was not in the list)

Code:

public class SinglyLinkedList { private Node head; private int size; public SinglyLinkedList() { head = null; size = 0; } public void insertAtHead(int v) { //Step 1: Create a new node //Step 2: set the next of the new node to head Node newNode = new Node(v, head);

//Step 3: Change head reference to new node head = newNode; //Step 4: increase size of list size++; } public String toString() { //Case 1: list is empty if(head == null) { return "The list is Empty!"; } //Case 2: list is not empty String result = ""; Node temp = head; while(temp != null) { result += temp.toString() + " "; temp = temp.next; } return result; } /** * * @return the value at the head of the list which is getting removed */ public int removeHead() { if(head == null) { throw new IllegalStateException("List is empty"); } int value = head.value; head = head.next; size--; return value; } private class Node { private int value; private Node next; public Node(int v, Node n) { value = v; next = n; } public String toString() { return "" + value; } }

}

III. DoublyLinkedList

Add this DoublyLinkedList class to the project. This class already uses generics, so you only need to add the remove method, which is the same as in a singly linked list:

Add a method remove(ValueType e), which takes an element e to remove.

It should remove the first node whose value is equal to e. (Hint: use the equals()method)

This method should return true if a node was removed. (e was in the list)

This method should return false if no node was removed. (e was not in the list)

Code:

public class DoublyLinkedList { private Node header; private Node trailer; private int size; public DoublyLinkedList() { header = new Node<>(null, null, null); trailer = new Node<>(null, null, header); header.next = trailer; size = 0; } /** * This method inserts value v in a new node bteween first and second * @param v value to insert * @param first first node * @param second second node */ private void insertBetween(E v, Node first, Node second) { Node newNode = new Node<>(v, second, first); second.prev = newNode; first.next = newNode; size++; } /** * Removes the node beteween first and second. Throws illegalStateException * if the list is empty * @param first first node * @param second second node * @return the value deleted */ private E removeBetween(Node first, Node second) throws IllegalStateException { if(header.next == trailer) //if(size == 0) { throw new IllegalStateException("Cannot delete from empty list"); } E valueToReturn = first.next.value; first.next = second; second.prev = first; size--; return valueToReturn; } public void insertAtHead(E v) { insertBetween(v, header, header.next); } public void insertAtTail(E v) { insertBetween(v, trailer.prev, trailer); } public E removeHead() throws IllegalStateException { return removeBetween(header, header.next); } public E removeTail() throws IllegalStateException { return removeBetween(trailer.prev, trailer); } public String toString() { if(size == 0) { return "list is empty!"; } String r = ""; Node temp = header.next; while(temp != trailer) { r += temp.toString() + " "; temp = temp.next; } return r; } public void printBackward() { if(size == 0) { System.out.println("list is empty!"); } Node temp = trailer.prev; while(temp != header) { System.out.print(temp + " "); temp = temp.prev; } System.out.println();

} private static class Node { private T value; private Node next; private Node prev; public Node(T v, Node n, Node p) { value = v; next = n; prev = p; } public String toString() { return value.toString(); } }

}

IV. Driver

Create a Driver class with a main method. In main, you should test your remove methods by creating singly and doubly linked lists of GameCharacter objects, and removing objects from them. Make sure to test:

Removing elements from the head, middle, and tail of the list.

Removing elements from a single-element list.

Removing elements from an empty list.

Attempting to remove elements that are not in the list.

Attempting to remove elements that are in the list.

Attempting to remove an element that appears multiple times in the list.