Linked List/Algorithmic Code Prep • 28 min read

My Linked List. Used Star wars Collectables

I developed a personalized LinkedList class below, with guidance from individuals on StackOverflow and ChatGPT, to elucidate its functionality. Throughout the code, I’ve included comments detailing each step and approach, providing clear explanations of the implementation process.

Initially, I designated the current node as the head once I confirmed that the LinkedList contained more than one item. For each item in the LinkedList:

• a. I assigned the minimum value to the current node.
• b. Iterating through each linked node using the Node’s .next, I checked if it was less than the current minimum.
• c. If a node was found to be less than the current minimum, I updated the minimum.
• d. If necessary, I swapped the recorded minimum value with the “current” node.
• e. The “current” node was then adjusted to its .next, considering that all preceding nodes were already sorted.
• This process continued until the LinkedList was completely sorted

// defining a LinkedList class that can hold elements (T)
// ChatGPT: "T can be any data type that extends Comparable"
public class LinkedList<T extends Comparable<T>> {
    // Node class represents individual list elements
    private static class Node<T> {
        T data; // the element's actual data
        Node<T> next; // referencing (linking to *winky face*) to the next node in the list

        // constructor to create a node with given data
        Node(T data) {
            this.data = data;
            this.next = null; // no next node exists initially
        }
    }

    private Node<T> head; // references the first node in the list
    private int size; // represents the size/length of the list

    // constructor to initialize the LinkedList
    public LinkedList() {
        head = null; // it's empty at first, so there's NOTHING
        size = 0; // the size starts out as 0, as there is NOTHING
    }

    // like .add() for ArrayList, this adds an element to the end of the list
    public void add(T element) {
        if (head == null) {
            head = new Node<>(element); // if the list is empty, this creates the first node
            // when I gave my concept, chatGPT said to add this condition here, credit <-
        } else {
            Node<T> current = head;
            while (current.next != null) {
                current = current.next; // using a while loop to approach the last node
            }
            current.next = new Node<>(element); // adding the new node at the end
        }
        size++; // increasing size of the list
    }

    // HERE'S MY CUSTOM SELECTION SORT
    public void selectionSort() {
        if (head == null || head.next == null) {
            return; // if the list is empty or has only one element, it's already sorted
            // again, this is an inclusion courtesy of ChatGPT and its incredible forethought
        }
        Node<T> current = head;
        while (current != null) {
            Node<T> min = current;
            Node<T> temp = current.next;
            while (temp != null) {
                if (temp.data.compareTo(min.data) < 0) {
                    min = temp; // finding the minimum element
                }
                temp = temp.next;
            }
            T tmpData = current.data; // swapping the current unsorted place with the minimum
            current.data = min.data;
            min.data = tmpData;
            current = current.next; // moving to the next element
        }
    }

    // this method overrides toString
    // it's used for printing the list
    // this was my reference: https://stackoverflow.com/questions/42676579/tostring-method-for-a-linkedlist
    // i shouldn't have needed a reference, but I wanted to make sure there wasn't anything special to do
    @Override
    public String toString() {
        String string = "["; // starting the list format
        Node<T> current = head; // start with head
        while (current != null) {
            string += current.data; // appending the current data to the string
            if (current.next != null) {
                string += ", "; // good punctuation = professionalism
            }
            current = current.next; // moving on
        }
        string += "]"; // capping off the list format
        return string;
    }

    // this is to return a JSON representation of the list
    // i basically did the same thign as I did for the toString() one
    public String toJSON() {
        String json = "{"; // starting format
        Node<T> current = head; // start with head
        while (current != null) {
            json += "\"" + current.data + "\""; // adding current data in quotations for JSON
            if (current.next != null) {
                json += ", "; // good punctuation again, this time very important
            }
            current = current.next; // moving on
        }
        json += "}"; // capping off
        return json;
    }

    // may be implemented? still researching
    public void changeSortKey() {
        // yet to come...
    }

    // main method for testing
    public static void main(String[] args) {
        LinkedList<Integer> list = new LinkedList<>();
        list.add(5);
        list.add(3);
        list.add(8);
        list.add(1);
        System.out.println("Original list: " + list);
        list.selectionSort();
        System.out.println("Sorted list: " + list);
        System.out.println("JSON representation: " + list.toJSON());
    }
}

LinkedList.main(null);

Original list: [5, 3, 8, 1]
Sorted list: [1, 3, 5, 8]
JSON representation: {"1", "3", "5", "8"}

interface Collectable<T> extends Comparable<T> {
    // implementing compareTo method to define natural ordering
    @Override
    int compareTo(T other);

    String toString(); // needed for LL printing
}
// defining the StarWarsCharacter class implementing Collectable interface
class StarWarsCharacter implements Collectable<StarWarsCharacter> {
    private String name;
    private String species;
    private int powerLevel;

    // basic constructor
    public StarWarsCharacter(String name, String species, int powerLevel) {
        this.name = name;
        this.species = species;
        this.powerLevel = powerLevel;
    }

    // getters methods
    public String getName() { return name; }
    public String getSpecies() { return species; }
    public int getPowerLevel() { return powerLevel; }

    // implementing the interface compareTo method
    // i definde natural ordering based on power level
    @Override
    public int compareTo(StarWarsCharacter other) {
        return Integer.compare(this.powerLevel, other.powerLevel);
    }

    // overriding toString method for better representation of the Star Wars character
    @Override
    public String toString() {
        return name + " (" + species + ") - Power Level: " + powerLevel;
    }

    public static void main(String[] args) {
        // Create an array of Star Wars characters
        StarWarsCharacter[] charactersArray = new StarWarsCharacter[] {
            new StarWarsCharacter("Luke Skywalker", "Human", 9000),
            new StarWarsCharacter("Darth Vader", "Human", 9500),
            new StarWarsCharacter("Yoda", "Unknown", 10000),
            new StarWarsCharacter("Han Solo", "Human", 8500)
        };

        // Create a LinkedList of Star Wars characters
        LinkedList<StarWarsCharacter> charactersList = new LinkedList<>();

        // Add characters to the LinkedList
        for (StarWarsCharacter character : charactersArray) {
            charactersList.add(character);
        }

        // Sort and display the LinkedList
        charactersList.selectionSort();
        System.out.println("Sorted list: " + charactersList);
        System.out.println("JSON representation: " + charactersList.toJSON());
    }
}

StarWarsCharacter.main(null);

Sorted list: [Han Solo (Human) - Power Level: 8500, Luke Skywalker (Human) - Power Level: 9000, Darth Vader (Human) - Power Level: 9500, Yoda (Unknown) - Power Level: 10000]
JSON representation: {"Han Solo (Human) - Power Level: 8500", "Luke Skywalker (Human) - Power Level: 9000", "Darth Vader (Human) - Power Level: 9500", "Yoda (Unknown) - Power Level: 10000"}

public class Main {
    public static void main(String[] args) {
        LinkedList<StarWarsCharacter> characters = new LinkedList<>();
        characters.add(new StarWarsCharacter("Luke Skywalker", "Human", 9000));
        characters.add(new StarWarsCharacter("Darth Vader", "Human", 9500));
        characters.add(new StarWarsCharacter("Yoda", "Unknown", 10000));
        characters.add(new StarWarsCharacter("Han Solo", "Human", 8500));

        System.out.println("Original list: " + characters);
        characters.selectionSort();
        System.out.println("Sorted list: " + characters);
        System.out.println("JSON representation: " + characters.toJSON());
    }
}
Main.main(null);

Original list: [Luke Skywalker (Human) - Power Level: 9000, Darth Vader (Human) - Power Level: 9500, Yoda (Unknown) - Power Level: 10000, Han Solo (Human) - Power Level: 8500]
Sorted list: [Han Solo (Human) - Power Level: 8500, Luke Skywalker (Human) - Power Level: 9000, Darth Vader (Human) - Power Level: 9500, Yoda (Unknown) - Power Level: 10000]
JSON representation: {"Han Solo (Human) - Power Level: 8500", "Luke Skywalker (Human) - Power Level: 9000", "Darth Vader (Human) - Power Level: 9500", "Yoda (Unknown) - Power Level: 10000"}

I desired to integrate SortKeys within the LinkedList class, primarily because I believed that leveraging enums in Java would be beneficial for my skill development. While I’ve employed enums in Java once before, my exposure to them has mostly been in GML, a coding language exclusive to GameMaker Studio.

Modified Star Wars Collectable

I aimed to enable a LinkedList object to inspect the class it’s working with, identify its sorting criteria, and then utilize them accordingly. The adaptation for Star Wars characters is provided below:

// defining the StarWarsCharacter class implementing Collectable interface
class StarWarsCharacter implements Collectable<StarWarsCharacter> {
    private String name;
    private String species;
    private int powerLevel;

    // my attempt at SortKey implementation
    enum SortKey {
        NAME,
        SPECIES,
        POWER_LEVEL
    }

    private static SortKey currentSortKey = SortKey.POWER_LEVEL; // default sort key is power level

    // basic constructor
    public StarWarsCharacter(String name, String species, int powerLevel) {
        this.name = name;
        this.species = species;
        this.powerLevel = powerLevel;
    }

    // getters methods
    public String getName() { return name; }
    public String getSpecies() { return species; }
    public int getPowerLevel() { return powerLevel; }

    // special sort key setter method for static context
    public static void setCurrentSortKey(SortKey sortKey) {
        currentSortKey = sortKey;
    }

    // implementing the interface compareTo method
    // trying to make it founded on the StarWarsCharacter class's defined current sort key
    @Override
    public int compareTo(StarWarsCharacter other) {
        switch (currentSortKey) {
            case NAME: // sorts alphabetically by name
                return this.name.compareTo(other.name);
            case SPECIES: // sorts alphabetically by species
                return this.species.compareTo(other.species);
            case POWER_LEVEL: // sorts by increasing power level
                return Integer.compare(this.powerLevel, other.powerLevel);
            default:
                throw new IllegalArgumentException("Invalid sort key");
        }
    }

    // overriding toString method for better representation of the Star Wars character
    @Override
    public String toString() {
        return name + " (" + species + ") - Power Level: " + powerLevel;
    }

    public static void main(String[] args) {
        // Create an array of Star Wars characters
        StarWarsCharacter[] charactersArray = new StarWarsCharacter[] {
            new StarWarsCharacter("Luke Skywalker", "Human", 9000),
            new StarWarsCharacter("Darth Vader", "Human", 9500),
            new StarWarsCharacter("Yoda", "Unknown", 10000),
            new StarWarsCharacter("Han Solo", "Human", 8500)
        };

        // Create a LinkedList of Star Wars characters
        LinkedList<StarWarsCharacter> charactersList = new LinkedList<>();

        // Add characters to the LinkedList
        for (StarWarsCharacter character : charactersArray) {
            charactersList.add(character);
        }

        // Sort and display the LinkedList with different sort keys
        for (StarWarsCharacter.SortKey sortKey : StarWarsCharacter.SortKey.values()) {
            // setting the current sort key
            StarWarsCharacter.setCurrentSortKey(sortKey);
            
            // selection sort called for the LinkedList class
            charactersList.selectionSort();
            
            // displaying the sorted LinkedList
            System.out.println("Sorted by " + sortKey + ": " + charactersList);
        }
    }
}

StarWarsCharacter.main(null);

Sorted by NAME: [Darth Vader (Human) - Power Level: 9500, Han Solo (Human) - Power Level: 8500, Luke Skywalker (Human) - Power Level: 9000, Yoda (Unknown) - Power Level: 10000]
Sorted by SPECIES: [Darth Vader (Human) - Power Level: 9500, Han Solo (Human) - Power Level: 8500, Luke Skywalker (Human) - Power Level: 9000, Yoda (Unknown) - Power Level: 10000]
Sorted by POWER_LEVEL: [Han Solo (Human) - Power Level: 8500, Luke Skywalker (Human) - Power Level: 9000, Darth Vader (Human) - Power Level: 9500, Yoda (Unknown) - Power Level: 10000]