I am trying to do a Leaderboard for a game by using a Sorted Linked List. I was able to do so by sorting the point in descending order which mean higher point to lower point. Moreover, I will also need to put player name together with the point. The problem comes here. The SLL(Sorted Linked List) I implemented is an Integer data type, it works perfectly with the Integer data type as it sorted the numbers.
SortedListInterface<Integer> Player = new LeaderboardSortedLinkedList<Integer>();
But when I trying to put the player name which used String, it won’t be able to do so because the point data type will need to follow the player name’s data type. Below are the codes of the driver class:
public class testLeaderboard {
public static void main(String[] args) {
SortedListInterface<Integer> Player = new LeaderboardSortedLinkedList<Integer>();
Player.add(1000000);
Player.add(500000);
Player.add(250000);
Player.add(125000);
Player.add(64000);
Player.add(32000);
Player.add(16000);
Player.add(8000);
Player.add(4000);
Player.add(2000);
Player.add(1000);
Player.add(500);
Player.add(300);
Player.add(200);
Player.add(100);
System.out.printf("=================================n"
+ " Leaderboardn"
+"=================================n");
for(int i=0; i< Player.size();i++){
System.out.printf("%3d. %sn",(i+1), Player.get(i+1));
}
}
}
Here is the Entity class
public class Player {
private String name;
private int prize;
public Player(String name, int prize) {
this.name = name;
this.prize = prize;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getPrize() {
return prize;
}
public void setPrize(int prize) {
this.prize = prize;
}
@Override
public String toString() {
return "Player{" + "name=" + name + ", prize=" + prize + '}';
}
}
Here’s the custom Sorted Lineked List
public class LeaderboardSortedLinkedList<T extends Comparable<T>> implements SortedListInterface<T> {
private Node firstNode;
private int length;
public LeaderboardSortedLinkedList() {
firstNode = null;
length = 0;
}
public boolean add(T newEntry) {
Node newNode = new Node(newEntry);
Node nodeBefore = null;
Node currentNode = firstNode;
while (currentNode != null && newEntry.compareTo(currentNode.data) < 0) {
nodeBefore = currentNode;
currentNode = currentNode.next;
}
if (isEmpty() || (nodeBefore == null)) { // CASE 1: add at beginning
newNode.next = firstNode;
firstNode = newNode;
} else { // CASE 2: add in the middle or at the end, i.e. after nodeBefore
newNode.next = currentNode;
nodeBefore.next = newNode;
}
length++;
return true;
}
public boolean contains(T anEntry) {
boolean found = false;
Node tempNode = firstNode;
int pos = 1;
while (!found && (tempNode != null)) {
if (anEntry.compareTo(tempNode.data) <= 0) {
found = true;
} else {
tempNode = tempNode.next;
pos++;
}
}
if (tempNode != null && tempNode.data.equals(anEntry)) {
return true;
} else {
return false;
}
}
public int size(){
int count = 0;
//Node current will point to head
Node current = firstNode;
while(current != null) {
//Increment the count by 1 for each node
count++;
current = current.next;
}
return count;
}
public T get(int position){
T result = null;
if ((position >= 1) && (position <= length)) {
Node currentNode = firstNode;
for (int i = 0; i < position - 1; ++i) {
currentNode = currentNode.next; // advance currentNode to next node
}
result = currentNode.data; // currentNode is pointing to the node at givenPosition
}
return result;
}
public final void clear() {
firstNode = null;
length = 0;
}
public int getLength() {
return length;
}
public boolean isEmpty() {
return (length == 0);
}
public String toString() {
String outputStr = "";
Node currentNode = firstNode;
while (currentNode != null) {
outputStr += currentNode.data + "n";;
currentNode = currentNode.next;
}
return outputStr;
}
private class Node {
private T data;
private Node next;
private Node(T data) {
this.data = data;
next = null;
}
private Node(T data, Node next) {
this.data = data;
this.next = next;
}
}
}
And the results is here
=================================
Leaderboard
=================================
1. 1000000
2. 500000
3. 250000
4. 125000
5. 64000
6. 32000
7. 16000
8. 8000
9. 4000
10. 2000
11. 1000
12. 500
13. 300
14. 200
15. 100
Here’s my testing on the point with string data type because I can’t think a way to use player name and point with 2 different data types at the same time in my custom ADT.
public class testLeaderboard {
public static void main(String[] args) {
SortedListInterface<String> Player = new LeaderboardSortedLinkedList<String>()
Player.add("1000000");
Player.add("500000");
Player.add("250000");
Player.add("125000");
Player.add("64000");
Player.add("32000");
Player.add("16000");
Player.add("8000");
Player.add("4000");
Player.add("2000");
Player.add("1000");
Player.add("500");
Player.add("300");
Player.add("200");
Player.add("100");
System.out.println(Player);
}
And here’s the result that it compare the first letter of the string.
8000 64000 500000 500 4000 32000 300 250000 2000 200 16000 125000 1000000 1000 100
Is there anyway to use both String and Integer in one ADT because if i couldn’t do so, I won’t be able sort the point. I’m so sorry for the long question. I am very new to data structures and algorithms so I really need some help on this. Much appreciate.
Advertisement
Answer
To keep the points and names together, you need to add Player objects into the list as they are, not just their points or their names:
SortedListInterface<Player> players = new LeaderboardSortedLinkedList<>();
players.add(new Player("Alpha", 1000000));
players.add(new Player("Beta", 500000));
players.add(new Player("Gamma", 250000));
For this to work, you will need to be able to compare Player objects by their point numbers. You do that by implementing the Comparable interface and adding a compareTo method.
You’ll also want to add a toString() method, so that you can print a Player object.
public class Player implements Comparable<Player> {
private String name;
private int prize;
@Override
public int compareTo(Player other) {
return Integer.compare(this.prize, other.prize);
}
@Override
public String toString() {
return String.format("name='%s' prize=%d", name, prize);
}
}