Create a class that maintains the top scores for a video game, this time using a linked list.

In class we worked on this task using an array of GameEntry objects. We then moved on to learning how to manipulate a linked list of numerical values (longs). For this project, you will create a linked list of GameEntry objects.

The provided classes are: the GameEntry class, and the Node class, both of which we’ve talked about. Read them carefully. Notice that the Node class does not have a long field as its data element, as it did in our notes. Instead, now it contains a GameEntry field!

Singly Linked List. Start by creating a singly linked list to use as your data structure for this task. In addition to the head field that we practiced with in class, you will also maintain a tail field. Include the below standard linked list features/methods in your class, which you should call HiScoresLL. Code up all the method headers exactly as given below.

Basic features of HiScoresLL:

• head and size fields, which we learned about in class and reading
• A tail field that references the last node in the list (akin to the head field)

Keep in mind:
• this field must be used/maintained/updated during operations like removing and adding nodes in case the last (or only) node is removed or a new node is being added to the end of the list. (Keep in mind the end of the list could be the same as the beginning of the list if there is only one item in it.)
• it is initially set to null, when the list is empty, just like the head field

• A constructor method – creates a new empty linked list

/**
* Constructor that creates an empty list
*/
public HiScoresLL()


• A display() method – outputs all the high score entries in the list

Remember, GameEntry objects come with a toString() method (see its definition in the GameEntry class) so you can directly print a GameEntry object e simply with System.out.println(e).

/**
* Prints out all the game entries in the linked list
*/
public void display()

• An addFirst(Node v) method – adds the node v to the front of the list

/**
* Add a node to the head of the list
* @param v
* the Node object to be added
*/

public void addFirst(Node v)

• A removeFirst() method – removes a node from the front of the list

/**
* Removes the first node and returns it,
* this method assumes the list is non-empty
* @return
* the Node that was removed
*/

public Node removeFirst()

• An addLast(Node v) method – adds the node v to the end of the list. Note: now that we have a reference to the tail of the list, this method can be implemented in constant time!

/**
* Add a node to the tail of the list
* @param v
* the Node object to be added
*/

public void addLast(Node v)

Code up all the method headers with preceding comments exactly as given above. For each method, be sure to test your work by adding test code to a main method in a Test class.
From reading the code for GameEntry and Node, you can see that one way to create and add a high score to a test list would be:

HiScoresLL hsList = new HiScoresLL();
GameEntry ge = new GameEntry("Grand Master",1000);
Node v = new Node(ge, null);
hsList.addFirst(v);
hsList.display();

Alternatively, you can combine the middle three lines into one by writing:

hsList.addFirst(new Node(new GameEntry("GM",1000), null));

After you’ve implemented and tested these basic features, you’re ready to add the two methods that allow someone to use your class to maintain a list of high scores for a video game. In implementing these next two methods, you may make calls to the basic list manipulation methods you created above.

• An add(GameEntry e) method, which only needs to work properly when the items in the list are already ordered by high score as expected

/**
* Assuming the list of game entries is in decreasing order by score,
* this method creates a Node with the given GameEntry e, and then
* inserts it in the appropriate spot in the list.
* @param e
* the GameEntry object to be added to the list
*/
public void add(GameEntry e)

• remove(int i) – removes the ith node, returning the corresponding game entry object

/**
* Removes the node at position i in the list
* (emulating an array index)
* @return
* the GameEntry of the removed node
* or null if position i is invalid
*/
public GameEntry remove(int i)