In Java 1. Write a class that maintains the top ten scores for a game applicatio
ID: 3752692 • Letter: I
Question
In Java
1. Write a class that maintains the top ten scores for a game application, implementing the add and remove methods using a singly linked list instead of an array
- for the add method please sort the list while adding.
2. Perform the previous project, but use a doubly linked list. Moreover, your implementation of remove(i) should make the fewest number of pointer hops to get to the game entry at index i. Please write the code in a beginner level, so that i can understand the code. Thank You
Explanation / Answer
Hi,
Please follow below steps to run the code:
Step 1: Create a java project with suitable name.
Step 2: Create a package named singlyLinkedList.
Step 3: Create a class named SinglyLinkedList in the package singlyLinkedList.
Step 4: Copy and paste below lines of code:
package singlyLinkedList;
/*
*Node class defines data and pointer(link) to next element
*/
class Node {
protected int data;
protected Node link;
public Node()
{
link = null;
data = 0;
}
public Node(int d,Node n)
{
data = d;
link = n;
}
public void setData(int d)
{
data = d;
}
public int getData()
{
return data;
}
}
/*
* SinglyLinkedList consists of implementation according to the question
*/
public class SinglyLinkedList {
protected Node start;//points to the start of the list
protected Node end ;//points to the end of the list
public int size ;// Size of the list
public static final int limit = 10; //limit of the list as mentioned in the question
public SinglyLinkedList()
{
start = null;
end = null;
size = 0;
}
public boolean isEmpty()
{
return start == null;
}
public int getSize()
{
return size;
}
public void insertData(int val)
{
Node nptr = new Node(val, null);
if(this.isEmpty())//if empty list
{
start = nptr;
end = nptr;
size++;
}
else
if(start.getData()<val)////to insert in the beginning of the list
{
nptr.link = start;
start = nptr;
size++;
}
else
{
Node preData = start;
Node parser = start.link;
while(preData.link!=null)
{
if(parser == null && size < limit)//to insert at the end of the list
{
nptr.link = parser;
preData.link = nptr;
end = nptr;
size++;
break;
}
/*to insert in the middle of the list
* (parse till the element with smaller data
* is found then insert new node in front of it)
*/
if(parser.getData()<val)
{
nptr.link = parser;
preData.link = nptr;
size++;
break;
}
parser = parser.link;
preData = preData.link;
}
}
if(size > limit)//If size exceeds the limit remove the last element
{
deleteSmallestData();
}
}
/*
* Smallest data will end up in the end of the list
* so delete the last element
*/
public void deleteSmallestData()
{
Node preData = start;
Node parser = start.link;
while(parser.link!=null)
{
parser = parser.link;
preData = preData.link;
}
preData.link = null;
end = preData;
--size;
}
public void displayData()
{
Node parser = start;
while(parser != null)
{
System.out.println(parser.getData());
parser = parser.link;
}
}
}
Step 5: Create a class named MainClass in the package singlyLinkedList and paste below code.
package singlyLinkedList;
import java.io.IOException;
import java.util.Scanner;
public class MainClass {
public static void main(String[] args) throws IOException {
Scanner in = new Scanner(System.in);
int n = 0;
n = Integer.parseInt(in.nextLine().trim());
/*
* Input Format
7 --> number of elements
5
7
6
9
8
10
4
*/
int[] elements = new int[n];
int element;
for (int i = 0; i < n; i++) {
element = Integer.parseInt(in.nextLine().trim());
elements[i] = element;
}
SinglyLinkedList sng = new SinglyLinkedList();
for(int i = 0; i < n; i++)
{
sng.insertData(elements[i]);
}
sng.displayData();
}
}
Step 6: Create a package named doublyLinkedListPackage.
Step 7: Create a class named DoublyLinkedList in doublyLinkedListPackage and copy below lines of code.
package doublyLinkedListPackage;
/*
*Node class defines data and pointer to next and previous elements
*/
class Node
{
protected int data;
protected Node next, prev;
public Node()
{
next = null;
prev = null;
data = 0;
}
public Node(int d, Node n, Node p)
{
data = d;
next = n;
prev = p;
}
public void setData(int d)
{
data = d;
}
public int getData()
{
return data;
}
}
/*
* DoublyLinkedList consists of implementation according to the question
*/
public class DoublyLinkedList {
protected Node start;//points to the start of the list
protected Node end ; //points to the end of the list
public int size; // Size of the list
public static final int limit = 10; //limit of the list as mentioned in the question
public DoublyLinkedList()
{
start = null;
end = null;
size = 0;
}
public boolean isEmpty()
{
return start == null;
}
public void insertData(int val)
{
Node newNode = new Node();
newNode.setData(val);
if(this.isEmpty())//if empty list
{
start = newNode;
end = newNode;
size++;
}
else
if(start.getData() < val)//to insert in the beginning of the list
{
newNode.next = start;
start.prev = newNode;
start = newNode;
size++;
}
else
{
Node parser = start;
while(parser != null)
{
/*to insert in the middle of the list
* (parse till the element with smaller data
* is found then insert new node in front of it)
*/
if(parser.getData()<val)
{
newNode.next = parser;
newNode.prev = parser.prev;
parser.prev.next = newNode;
parser.prev = newNode;
size++;
break;
}
parser = parser.next;
}
if(parser == null && size < limit)//to insert at the end of the list
{
newNode.prev = end;
end.next = newNode;
end = newNode;
}
}
if(size > limit)//If size exceeds the limit remove the last element
{
deleteSmallestData();
}
}
/*
* Smallest data will end up in the end of the list
* so delete the last element
*/
public void deleteSmallestData()
{
end.prev.next = null;
end = end.prev;
end.next = null;
--size;
}
public void displayData()
{
Node parser = start;
while(parser != null)
{
System.out.println(parser.getData());
parser = parser.next;
}
}
}
Step 8: Create a class named MainClass in doublyLinkedListPackage and paste below code:
package doublyLinkedListPackage;
import java.io.IOException;
import java.util.Scanner;
public class MainClass {
public static void main(String[] args) throws IOException {
Scanner in = new Scanner(System.in);
int n = 0;
n = Integer.parseInt(in.nextLine().trim());
/*
* Input Format
7 --> number of elements
5
7
6
9
8
10
4
*/
int[] elements = new int[n];
int element;
for (int i = 0; i < n; i++) {
element = Integer.parseInt(in.nextLine().trim());
elements[i] = element;
}
DoublyLinkedList dbl = new DoublyLinkedList();
for(int i = 0; i < n; i++)
{
dbl.insertData(elements[i]);
}
dbl.displayData();
}
}
Step 9: Run both Main() independantly and give inputs as mentioned in the comments in main method. the main method will display final result.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.