A linked list is a collection of nodes, where each node containssome data and a reference (or
Question:
A linked list is a collection of nodes, where each node containssome data and a reference (or link) to the next node. Unlikearrays, linked lists can easily grow and shrink by simply addingand deleting nodes as needed. You can simply add or delete nodes bychanging which node links point to. For this reason, there are manyapplications in which linked lists are easier to implement over anarray.
Below is a snippet of a linked list. It shows three nodes, eachcontaining an integer and a link to the next node:
If we want to remove the node holding integer 11(node.next), we simply change node to point to node.next.next:
And the linked list now looks like this:
If we want to add the integer value 7 between 5 and 22, we cansimply insert a new node. node will point to new node and new nodewill point to node.next:
And the linked list now looks like this:
Notice in the above images that we have an arrow pointingtowards the first node of our linked list snippet. Imagine therebeing a starting node, called the head node, that is linked(pointing towards) node. Every linked list has a head. Head is areference to the first node. Even if the linked list is empty,there must be a head. An empty linked list looks asfollows:
If you were to remove all elements from a linked list,it will look like the image above.
Let’s backtrack to before removing items from our linkedlist. The complete linked list can be seen below, with tail beingthe last node. We know it’s the last node because it does not pointto any other nodes. The size of the linked list is 4 (head isnot counted when calculating size because head is simply areference to the first node). If you want to get a node, you cansimply refer to it by its index. For example, getting node.nextwould be equivalent to getting index 1.
In this lab, you will implement an old fashion arcade high scorelist. You are given 5 java files: Main, Node, Score, ArcadeList,and HighScoreList. Main consists of a menu system for you to testyour high score list (i.e. the linked list). Node contains theattributes, accessors, and mutators for a
node. Note that a node has a score and pointer to the next node.Similarly, score contains the attributes, accessors, and mutatorsof a score. A score has an integer value and an associated name(more like a 3 character length string - so initials). ArcadeListprovides the interface for the linked list. The remaining class,HighScoreList, will be the class you are working on!
Open eclipse and create a new project called Lab8. Copy the 5classes provided in myCourses into the project.
Explore the code provided. Notice the statements used throughoutthe program and how all the classes interact. You should befamiliar with all the programming conventions used in the filesprovided (while loops, switch statements, scanners, try-catches,method calls, instances of classes, constructors,...). If you have any questions about the code provided, raiseyour hand so that a TA or mentor can clarify any confusion.
You will be focusing on HighScoreList. The methods included areadd, removeItemAt, removeAll, isEmpty, getScore, getSize, andprintList. These methods should sound familiar to you as youimplemented most of them in lab 7. The key difference is that youwere working with an array last time. Now you are working with alinked list. This time around, you will need to complete add,removeItemAt, removeAll, isEmpty, getScore, and getSize (printListis completed for you). Add and removeItemAt are partially filledout. Look carefully at the comments to understand where you need toadd code. For the other four methods, look at the comments to knowexactly how they should execute.
A sample output looks like this:
Select an option (q to quit):
1). Add to list.
2.) Remove 1 item from an index of your choice. 3.) Removeeverthing from list.
4.) Get item at index.
5.) Print list.
1
Enter a score to add:
760
Enter a name to add:
aap
Select an option (q to quit):
1). Add to list.
2.) Remove 1 item from an index of your choice. 3.) Removeeverthing from list.
4.) Get item at index.
5.) Print list.
1
Enter a score to add:
230
Enter a name to add:
mgl
Select an option (q to quit):
1). Add to list.
2.) Remove 1 item from an index 3.) Remove everthing from list.4.) Get item at index.
5.) Print list.
1
Enter a score to add:
1080
Enter a name to add:
dac
Select an option (q to quit): 1). Add to list.
2.) Remove 1 item from an index 3.) Remove everthing from list. 4.)Get item at index.
5.) Print list.
5
High Scores Rank Score Name
1 1080 dac
2 760 aap
3 230 mgl
Select an option (q to quit): 1). Add to list.
2.) Remove 1 item from an index 3.) Remove everthing from list. 4.)Get item at index.
5.) Print list.
2
of your choice.
Enter a position to remove (There are 3 names on the list!):
3
Select an option (q to quit): 1). Add to list.
2.) Remove 1 item from an index 3.) Remove everthing from list. 4.)Get item at index.
5.) Print list.
2
of your choice.
Enter a position to remove (There are 2 names on the list!):
2
Select an option (q to quit): 1). Add to list.
2.) Remove 1 item from an index 3.) Remove everthing from list. 4.)Get item at index.
5.) Print list.
1
Enter a score to add:
9000
Enter a name to add:
bob
Select an option (q to quit): 1). Add to list.
2.) Remove 1 item from an index 3.) Remove everthing from list.
of your choice.
of your choice.
of your choice.
of your choice.
4.) Get item at index. 5.) Print list.
5
High Scores Rank Score Name
1 9000 bob 2 1080 dac
Select an option (q to quit):
1). Add to list.
2.) Remove 1 item from an index of your choice. 3.) Remove everything from list.
4.) Get item at index.
5.) Print list.
4
Enter a position to see (1-2):
1
9000
Select an option (q to quit):
1). Add to list.
2.) Remove 1 item from an index of your choice. 3.) Removeeverthing from list.
4.) Get item at index.
5.) Print list.
3
Cleared high score list!
Select an option (q to quit):
1). Add to list.
2.) Remove 1 item from an index of your choice. 3.) Removeeverthing from list.
4.) Get item at index.
5.) Print list.
5
High Scores Rank Score Name
Select an option (q to quit):
1). Add to list.
2.) Remove 1 item from an index of your choice. 3.) Removeeverthing from list.
4.) Get item at index.
5.) Print list.
q
Quitting...
Expert Answer:
import javautil public class linklist Singly linked node which stores a reference to it element and ... View the full answer
