Program.

-Create a new Java project called Assignment01. 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 classIMPORTANT: in order to correctly override this method, you must use the signature "public boolean equals(Object other)"

If you do not recall how to implement an equals method, either see section 7.3 of Absolute Java (the textbook for Intro. II), or look at this page (Links to an external site.)Links to an external site. (the third result when Googling for this) which provides a very good explanation of what to do and why to do it.

II. SinglyLinkedList

Add the SinglyLinkedList class we wrote in class to the project, 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)

III. DoublyLinkedList

Add the DoublyLinkedList class we wrote in 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)

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.

reference

SinglyLinkedList

public class SinglyLinkedList {

// private variables

// -- stores a reference to the first node in the list

// -- 'null' if the list is empty

private Node head;

private Node tail;

// constructor

public SinglyLinkedList() {

// make an empty list

head = null;

tail = null;

}

// methods to add elements to the list

public void addToFront(int value) {

// create a node, and place it before the current head

Node newNode = new Node(value);

// set the next of this new node to the current head

newNode.setNext(head);

// if the list was empty, we need to update the tail

// otherwise, the tail doesn't change

if(head == null)

tail = newNode;

// reset the head to the new node, which is now the first node

head = newNode;

// these are alternatively expressed in a single line as

// head = new Node(value, head);

}

public void addToBack(int value) {

// special case for an empty list

if(head == null) {

// the list is empty

head = new Node(value);

tail = head;

return;

}

// for this, we have to search for the end

// inefficient approach: searches for the end

// Node end = head;

// while(end.getNext() != null) {

// end = end.getNext();

// }

// efficient approach: uses the saved value

Node end = tail;

// what do we do with the last node?

// add another node afterwards

Node newLast = new Node(value);

end.setNext(newLast);

// this new node is now the end of the list, so we should

// update the tail

tail = newLast;

}

public int removeFront() {

// check if this is possible

if(head == null) {

// the list is empty, crash it! (with a better error message)

throw new IllegalStateException("cannot remove from an empty list");

}

// save the value from the first node

int ret = head.getValue();

// simply skip the first node

head = head.getNext();

// if the list becomes empty, we need to update the tail,

// otherwise, the tail stays the same

if(head == null) {

tail = null;

}

// return the value that was removed

return ret;

}

public int removeBack() {

// 0.) a few special cases to check for

if(head == null) {

throw new IllegalStateException("cannot remove from an empty list");

}

// if we have a single-node list, there is no second-to-last node

// therefore, we need a special case

if(head.getNext() == null) {

// there is a single node, it just needs to be removed

int oldValue = head.getValue();

head = null;

tail = null;

return oldValue;

}

// 1.) search for the second-to-last node in the list

Node newLast = head;

// note: because we want a node whose next is the tail

// and the tail is node whose next is null

while(newLast.getNext().getNext() != null) {

newLast = newLast.getNext();

}

// 2.) save the old value

int oldValue = newLast.getNext().getValue();

// 3.) update newLast to be the tail

newLast.setNext(null);

tail = newLast;

// 4.) return the old value

return oldValue;

}

public int min() {

// 0.) check if a minimum could even exist

if(head == null) {

// list is empty

throw new IllegalStateException("cannot find the min of an empty list");

}

// 1.) start off a value, that will store the minimum

int value = head.getValue();

// 2.) iterate through the list, and update the minimum as needed

for(Node tmp = head; tmp != null; tmp = tmp.getNext()) {

// update our value, if a new minimum is found

if(tmp.getValue() < value) {

value = tmp.getValue();

}

}

// 3.) return that minimum

return value;

}

public String toString() {

// String ret = "";

StringBuilder sb = new StringBuilder();

// add the elements in order

// if we just wanted to first value:

// ret += head.getValue();

// sb.append(head.getValue());

// // if we just wanted the second value:

// sb.append(head.getNext().getValue());

// let's apply the previous logic in a loop!

// loop over the nodes, appending values

for(Node tmp = head; tmp != null; tmp = tmp.getNext()) {

sb.append(tmp.getValue() + " ");

}

// return the constructed string

// return ret;

return sb.toString();

}

// private inner class for the Node's of the list

private class Node {

// private variables

// 1.) our piece of data

private int value;

// 2.) a reference to the next node

// --- this reference is null if this node has no next

private Node next;

// constructors

public Node(int value, Node next) {

this.value = value;

this.next = next;

}

public Node(int value) {

// this calls the previous constructor with the listed

// arguments

this(value, null);

}

// getters

public int getValue() {

return value;

}

public Node getNext() {

return next;

}

// setters

public void setValue(int value) {

this.value = value;

}

public void setNext(Node next) {

this.next = next;

}

}

}

DoublyLinkedList

public class DoublyLinkedList implements List {

// private member variables

// note: 'head' and 'tail' are sentinels

private Node head;

private Node tail;

private int size;

// constructor

public DoublyLinkedList() {

// create an empty list

size = 0;

// we have to create these sentinels, and link them to each other

head = new Node(null);

tail = new Node(null);

// link them to each other

head.setNext(tail);

tail.setPrev(head);

}

// helper size methods

public boolean isEmpty() {

return (size == 0);

}

public int size() {

return size;

}

// helper method to insert between two nodes

private void addBetween(ValueType value, Node pred, Node succ) {

// first, create a new node for value

Node newNode = new Node(value);

// second, link value to its predecessor and successor

newNode.setPrev(pred);

newNode.setNext(succ);

// third, link the predecessor and successor to the new node

pred.setNext(newNode);

succ.setPrev(newNode);

// fourth, we created a new node, so we should increase the size

// variable on our list

size++;

}

public void addFront(ValueType value) {

addBetween(value, head, head.getNext());

}

public void addBack(ValueType value) {

addBetween(value, tail.getPrev(), tail);

}

private ValueType removeNode(Node node) {

// 1.) we store its value

ValueType ret = node.getValue();

// 2.) update the references before and after the node

Node prev = node.getPrev();

Node next = node.getNext();

prev.setNext(next);

next.setPrev(prev);

//node.getPrev().setNext(node.getNext());

// 3.) decrement the size, because we just removed a node

size--;

// 4.) return the old value

return ret;

}

public ValueType removeFront() {

if(isEmpty())

throw new IllegalStateException("cannot remove from an empty list");

return removeNode(head.getNext());

}

public ValueType removeBack() {

if(isEmpty())

throw new IllegalStateException("cannot remove from an empty list");

return removeNode(tail.getPrev());

}

// to string method

public String toString() {

// build a string as we go

StringBuilder sb = new StringBuilder();

// first, print out the size

sb.append("(size=" + size + ")");

// optional: if we want a newline, there is a special char for this

// sb.append(" ");

// second, append all values in the list

for(Node tmp = head.getNext(); tmp != tail; tmp = tmp.getNext()) {

sb.append(" " + tmp.getValue());

}

// return full string

return sb.toString();

}

// private inner class for nodes

private class Node {

// private variables

private ValueType value;

private Node next;

private Node prev;

// constructors

public Node(ValueType value, Node prev, Node next) {

this.value = value;

this.prev = prev;

this.next = next;

}

public Node(ValueType value) {

// this calls the previous constructor with the listed

// arguments

this(value, null, null);

}

// getters

public ValueType getValue() { return value; }

public Node getNext() { return next; }

public Node getPrev() { return prev; }

// setters

public void setValue(ValueType value) { this.value = value; }

public void setNext(Node next) { this.next = next; }

public void setPrev(Node prev) { this.prev = prev; }

}

}