Is it possible to use 2 Data Type in an Custom ADT(Sorted Linked List)?

Tags: , , , ,



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.

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);
    }
}


Source: stackoverflow