How to have a String and an int connected in a Single Linked List

Question

I am creating a program that displays the top ten game scores.

The output displays the game score and a name but in my program the names do not match with the score.

It seems that the numbers get sorted correctly - the names do get sorted with the data. The list sorts from highest to lowest. In the output it shows the highest score is:

23 "stan"

when it should show:

23 "tweak"

public class singlyLinked {

    class Node {
        int data;
        String name;
        Node next;

        public Node(int data, String name) {
            this.data = data;
            this.name = name;
            this.next = null;
        }

        public String getName() {
            return name;
        }

        public void setName(String newName) {
            this.name = newName;
        }
    }

    public Node head = null;
    public Node tail = null;
    int size = 0;

    public void addNode(int data, String name) {
        Node newNode = new Node(data, name);

        if (head == null) {
            head = newNode;
            tail = newNode;
        } else {
            tail.next = newNode;
            tail = newNode;
        }
    }

    public void sortList() {
        Node current = head;
        Node index = null;
        int temp;

        if (head == null) {
            return;
        } else {
            while (current != null) {
                index = current.next;
                while (index != null) {
                    if (current.data < index.data) {
                        temp = current.data;
                        current.data = index.data;
                        index.data = temp;
                        current.getName();
                    }
                    index = index.next;
                }
                current = current.next;
                size++;
            }
        }
    }

    public void topTen() {
        while (size > 10) {
            if (head == null) {
                return;
            } else {
                if (head != tail) {
                    Node current = head;
                    while (current.next != tail) {
                        current = current.next;
                    }
                    tail = current;
                    tail.next = null;
                } else {
                    head = tail = null;
                }
            }
            size--;
        }
    }

    public void getSize() {
        System.out.println(size);
    }

    public void display() {
        Node current = head;
        if (head == null) {
            System.out.println("List is empty");
            return;
        }
        while (current != null) {
            System.out.println(current.data + current.name + " ");
            current = current.next;
        }
    }

    public static void main(String[] args) {
        singlyLinked list = new singlyLinked();

        System.out.println("HighScore:" + " Name:");

        list.addNode(8, " stan");
        list.addNode(7, " kenny");
        list.addNode(13, " eric");
        list.addNode(12, " wendy");
        list.addNode(7, " token");
        list.addNode(9, " craig");
        list.addNode(1, " clyde");
        list.addNode(5, " butters");
        list.addNode(20, " randy");
        list.addNode(1, " sharon");
        list.addNode(22, " timmy");
        list.addNode(23, " tweak");

        list.sortList(); // sorts
        list.topTen();

        list.display(); // displays
    }
}

Janez Kuhar · Answer 1 · 2021-03-02T13:44:10.390

So you shouldn't be comparing ints but Nodes.

The standard way of comparing objects in Java is to have them implement Comparable.

class Node implements Comparable<Node> {
    // ... your current Node implementation
    @Override
    public int compareTo(Node that) {
        return this.data - that.data;
    }
}

Then your sortList should become something like this:

public void sortList() {
    Node original = head;
    /** Result iteration node. */
    Node resultIter = null;
    /** The node that is directly before {@code resultIter}. */
    Node resultIterPrev = null;
    /** A copy of the {@code resultIter} node. */
    Node resultIterCopy = null;
    /** A temporary node, used for swapping. */
    Node temp = null;

    if (head == null) {
        return;
    } else {
        // 1. Initialize an empty linked list holding the result.
        Node result = null;
        // 2.1 Iterate unsorted list
        while (original != null) {
            // 2.1.1 Scan across the result list to find the location where
            // the next element of unsorted list ("original") belongs.
            if (result == null) {
                result = new Node(original.data, original.name);
            } else {
                resultIter = result;
                boolean added = false;
                while (resultIter != null) {
                    if (original.compareTo(resultIter) > 0) {
                        resultIterCopy = new Node(resultIter.data, resultIter.name);
                        temp = resultIter.next;

                        // Set the value to an existing node so that the pointer
                        // to "resultIter" remains unchanged
                        resultIter.data = original.data;
                        resultIter.name = original.name;
                        
                        resultIter.next = resultIterCopy;
                        resultIter.next.next = temp;
                        added = true;
                        break;
                    }
                    resultIterPrev = resultIter;
                    resultIter = resultIter.next;
                }
                // If the next value from the unsorted list belongs at
                // the end of the sorted list
                if (!added) {
                    resultIterPrev.next = new Node(original.data, original.name);
                }
            }
            original = original.next;
        }
        // Swap unsorted list with the sorted one
        head = result;
        // Find new tail
        tail = head;
        while (tail.next != null) {
            tail = tail.next;
        }
    }
}

This implementation tries to follow an insertion sort as per described in this answer.

I have extracted size out of your sorting method because it kept increasing every time I invoked sortList. Instead, I've placed it inside addNode:

public void addNode(int data, String name) {
    // ... your existing Node adding logic
    size++;
}

As you can probably see, creating your own linked list can lead to all sorts of bugs. Consider using the implementation provided by the Java standard library, as suggested by @LitVitNik.

LitVitNik · Answer 2 · 2021-03-01T21:09:38.107

Is it required to use your own implementation of LinkedList? If not, you can use something like this:

import java.util.Comparator;
import java.util.LinkedList;

public class Main {
    public static void main(String[] args) {
        LinkedList<Node> list = new LinkedList<>();
        list.add(new Node(8, "stan"));
        list.add(new Node(7, "kenny"));
        list.add(new Node(13, "eric"));
        list.add(new Node(12, "token"));
        list.add(new Node(7, "craig"));
        list.add(new Node(9, "clyde"));
        list.add(new Node(1, "butters"));
        list.add(new Node(5, "randy"));
        list.add(new Node(20, "sharon"));
        list.add(new Node(1, "timmy"));
        list.add(new Node(22, "stan"));
        list.add(new Node(23, "tweak"));
        Collections.sort(list);
        for(int i = 0; i < 10; i++){
            System.out.println(list.get(i));
        }
    }
}
class Node implements Comparable<Node>{
    String name;
    int score;

    public Node(int score, String name){
        this.score = score;
        this.name = name;
    }
    @Override
    public int compareTo(Node another) {
        return another.score - this.score;
    }

    @Override
    public String toString() {
        return this.name + " : " + this.score;
    }
}

You're importing `Comparator` but using `Comparable`. Which is it?:) — Janez Kuhar, Mar 02 '21 at 21:04

How to have a String and an int connected in a Single Linked List

2 Answers2