Custom LinkedList and In-Depth Selection Sort Implementation
Doing some more difficult implementation with Selection Sort to show mastery.
- My Custom Linked List Class
- Custom Comparable
- Working with Sort Keys
- Implementing All Sorts
- Reflection on Algorhythmic
My Custom Linked List Class
I implemented a custom LinkedList class below with the help of people on StackOverflow and of ChatGPT to explain exactly how it works. I left comments throughout to explain exactly what I was doing and how it was done
Selection Sort Implementation
Selection Sort ended up working essentially the same as when implemented with an Array. Step-by-step:
- I defined the current node as the head after determining that there was more than one item in the LinkedList
- For each item in the LinkedList:
- I set the minimum to the current node
- I jump using the Node’s .next to each linked Node, checking if it’s less than the current minimum
- If less than current minimum, the minimum is replaced
- If applicable, the recorded minimum is swapped with the “current” node
- The “current” node is adjusted to its .next, as all previous have already been sorted
- This is repeated until the LinkedList has been fully 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"}
Custom Comparable
I decided to do it with Pokemon, returning to my roots og this year. I figured they’d have a lot of data that could be compared, but I decided to specifically focus on comparing Pokedex numbers. In the franchise, I feel like that would be the most sensible way for a researcher to compare them.
// defining the Collectable interface
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 Pokemon class implementing Collectable interface
class Pokemon implements Collectable<Pokemon> {
private String name;
private String[] types;
private int dexNumber;
// basic constructor
public Pokemon(String name, String[] types, int dexNumber) {
this.name = name;
this.types = types;
this.dexNumber = dexNumber;
}
// getters methods
public String getName() {return name;}
public String[] getTypes() {return types;}
public int getDexNumber() {return dexNumber;}
// implementing the interface compareTo method
// i definde natural ordering based on pokedex number
@Override
public int compareTo(Pokemon other) {
return Integer.compare(this.dexNumber, other.dexNumber);
}
// overriding toString method for better representation of the Pokemon
@Override
public String toString() {
return name + " (#" + dexNumber + ")";
}
}
Using Custom Comparable With Custom LinkedList
See the commented code cell below:
public class Main {
public static void main(String[] args) {
// creating the linkedlist of pokemon
LinkedList<Pokemon> pokemonList = new LinkedList<>();
// adding some well-known Pokemon to the list
pokemonList.add(new Pokemon("Pikachu", new String[]{"Electric"}, 25));
pokemonList.add(new Pokemon("Walking Wake", new String[]{"Water", "Dragon"}, 1009));
pokemonList.add(new Pokemon("Charmander", new String[]{"Fire"}, 4));
pokemonList.add(new Pokemon("Minior", new String[]{"Rock", "Flying"}, 774));
pokemonList.add(new Pokemon("Bulbasaur", new String[]{"Grass", "Poison"}, 1));
pokemonList.add(new Pokemon("Ambipom", new String[]{"Normal"}, 424));
pokemonList.add(new Pokemon("Squirtle", new String[]{"Water"}, 7));
// I shortened the pokemon toString() for this reason
System.out.println("Original list:\n\t" + pokemonList);
// sorting the list based on Pokedex numbers, using SELECTION SORT!!!
pokemonList.selectionSort();
// displaying the sorted list (SELECTION SORT!!!)
System.out.println("Sorted list by Pokedex number:\n\t" + pokemonList);
}
}
Main.main(null);
Original list:
[Pikachu (#25), Walking Wake (#1009), Charmander (#4), Minior (#774), Bulbasaur (#1), Ambipom (#424), Squirtle (#7)]
Sorted list by Pokedex number:
[Bulbasaur (#1), Charmander (#4), Squirtle (#7), Pikachu (#25), Ambipom (#424), Minior (#774), Walking Wake (#1009)]
Working with Sort Keys
I wanted to implement SortKeys in the LinkedList class, specifically because I thought the concept of using enum in Java would be good for me to strengthen. (I’ve used it once in Java, and all other exposure has been in GML, a code language specific to GameMaker Studio.)
Modified Pokemon Collectable
I wanted to make it so that a LinkedList object can look at the class in question, determine its sort key options, and then be able to utilize them. The Pokemon side of this modification is shown below:
// defining the Pokemon class implementing Collectable interface
class Pokemon implements Collectable<Pokemon> {
private String name;
private String[] types;
private int dexNumber;
private int level;
// Define the map to assign numerical values to Pokemon types
public final Map<String, Integer> typeKey = new HashMap<>();
// initializing typeKey map
{
// assigning numerical values to Pokemon types
typeKey.put("Normal", 0);
typeKey.put("Fire", 1);
typeKey.put("Water", 2);
typeKey.put("Electric", 3);
typeKey.put("Grass", 4);
typeKey.put("Ice", 5);
typeKey.put("Fighting", 6);
typeKey.put("Poison", 7);
typeKey.put("Ground", 8);
typeKey.put("Flying", 9);
typeKey.put("Psychic", 10);
typeKey.put("Bug", 11);
typeKey.put("Rock", 12);
typeKey.put("Ghost", 13);
typeKey.put("Dragon", 14);
typeKey.put("Dark", 15);
typeKey.put("Steel", 16);
typeKey.put("Fairy", 17);
}
// my attempt at SortKey implementation
enum SortKey {
NAME,
TYPES,
DEX_NUMBER,
LEVEL
}
private static SortKey currentSortKey = SortKey.DEX_NUMBER; // default sort key is dex number
// basic constructor
public Pokemon(String name, String[] types, int dexNumber, int level) {
this.name = name;
this.types = types;
this.dexNumber = dexNumber;
if (level > 100) { // handler for invalid levels
this.level = 100;
} else if (level < 1) {
this.level = 1;
} else {
this.level = level;
}
}
// getters methods
public String getName() {return name;}
public String[] getTypes() {return types;}
public int getDexNumber() {return dexNumber;}
// special sortkey 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 Pokemon class's defined current sort key
// sorts have been implemented for all types
@Override
public int compareTo(Pokemon other) {
switch (currentSortKey) {
case NAME: // sorts alphabetically by name
return this.name.compareTo(other.name);
case TYPES: // sorts based on values of typeKey, see typeKey above
return Integer.compare(typeKey.get(this.types[0]), typeKey.get(other.types[0]));
case DEX_NUMBER: // sorts by increasing pokedex number
return Integer.compare(this.dexNumber, other.dexNumber);
case LEVEL: // sorts by increasing level
return Integer.compare(this.level, other.level);
default:
throw new IllegalArgumentException("Invalid sort key");
}
}
// overriding toString method for better representation of the Pokemon
@Override
public String toString() {
return name + " (lvl. " + level + ")";
}
public static void main(String[] args) {
// creating an array of Pokemon
Pokemon[] pokemonArray = new Pokemon[] {
new Pokemon("Machop", new String[]{"Fighting"}, 66, 14),
new Pokemon("Arrokuda", new String[]{"Water"}, 846, 23),
new Pokemon("Rattata", new String[]{"Normal"}, 19, 4),
new Pokemon("Cranidos", new String[]{"Rock"}, 408, 25),
new Pokemon("Scolipede", new String[]{"Poison", "Bug"}, 545, 34),
new Pokemon("Avalugg", new String[]{"Ice"}, 713, 43),
new Pokemon("Camerupt", new String[]{"Fire", "Ground"}, 323, 39),
new Pokemon("Bastiodon", new String[]{"Rock", "Steel"}, 411, 36)
};
// creating a LinkedList of Pokemon
LinkedList<Pokemon> pokemonList = new LinkedList<>();
// adding Pokemon to the LinkedList
for (Pokemon pokemon : pokemonArray) {
pokemonList.add(pokemon);
}
// sorting and displaying with all different sort keys
for (Pokemon.SortKey sortKey : Pokemon.SortKey.values()) {
// setting the current sort key
Pokemon.setCurrentSortKey(sortKey);
// selection sort called for the LinkedList class
pokemonList.selectionSort();
// displaying the sorted LinkedList
System.out.println("Sorted by " + sortKey + ": " + pokemonList);
}
}
}
Pokemon.main(null);
Sorted by NAME: [Arrokuda (lvl. 23), Avalugg (lvl. 43), Bastiodon (lvl. 36), Camerupt (lvl. 39), Cranidos (lvl. 25), Machop (lvl. 14), Rattata (lvl. 4), Scolipede (lvl. 34)]
Sorted by TYPES: [Rattata (lvl. 4), Camerupt (lvl. 39), Arrokuda (lvl. 23), Avalugg (lvl. 43), Machop (lvl. 14), Scolipede (lvl. 34), Bastiodon (lvl. 36), Cranidos (lvl. 25)]
Sorted by DEX_NUMBER: [Rattata (lvl. 4), Machop (lvl. 14), Camerupt (lvl. 39), Cranidos (lvl. 25), Bastiodon (lvl. 36), Scolipede (lvl. 34), Avalugg (lvl. 43), Arrokuda (lvl. 23)]
Sorted by LEVEL: [Rattata (lvl. 4), Machop (lvl. 14), Arrokuda (lvl. 23), Cranidos (lvl. 25), Scolipede (lvl. 34), Bastiodon (lvl. 36), Camerupt (lvl. 39), Avalugg (lvl. 43)]
Implementing All Sorts
To meet requirements, after practicing with the sorts checkpoint, I added new sort methods to the LinkedList class.
public class LinkedList<T extends Comparable<T>> {
private static class Node<T> {
T data;
Node<T> next;
// constructor to create a node
Node(T data) {
this.data = data;
this.next = null;
}
}
private Node<T> head; // first in linkedlist
private int size;
// constructor to initialize the LinkedList
public LinkedList() {
head = null;
size = 0;
}
// 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
} 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
}
// see earlier for citations
@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
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;
}
// new BUBBLE SORT method
public void bubbleSort() {
if (head == null || head.next == null) {
return; // List is empty or has only one node, no need to sort
}
boolean swapped;
Node<T> last = null;
// this saves some steps, thank you ChatGPT
// just learned how and why to use do {} while (condition); :O
do {
swapped = false;
Node<T> current = head;
while (current.next != last) {
if (current.data.compareTo(current.next.data) > 0) {
// swapping data of current and next nodes
T temp = current.data;
current.data = current.next.data;
current.next.data = temp;
swapped = true;
}
current = current.next;
}
last = current;
} while (swapped);
}
// existing 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
}
}
// new INSERTION SORT method
public void insertionSort() {
if (head == null || head.next == null) {
return; // List is empty or has only one node, no need to sort
}
Node<T> sorted = null; // initializing sorted list as empty
Node<T> current = head;
while (current != null) {
Node<T> next = current.next;
sorted = sortedInsert(sorted, current); // inserting current node into sorted list
current = next;
}
head = sorted; // Update head to point to the sorted list
}
// this inserts a node into a sorted list and returns the head of the sorted list
// thank you for the help, CHat
private Node<T> sortedInsert(Node<T> sorted, Node<T> newNode) {
if (sorted == null || sorted.data.compareTo(newNode.data) > 0) {
newNode.next = sorted;
return newNode;
}
Node<T> current = sorted;
while (current.next != null && current.next.data.compareTo(newNode.data) < 0) {
current = current.next;
}
newNode.next = current.next;
current.next = newNode;
return sorted;
}
// new MERGE SORT method
// chatGpt played a big role in this one
public void mergeSort() {
head = mergeSort(head); // call goes straight to this
}
// this method will help to call the merge sort recursively
private Node<T> mergeSort(Node<T> node) {
if (node == null || node.next == null) {
return node; // if the list is empty/only has one node, it's sorted
}
// splitting the list into two halves
Node<T> mid = getMiddleFromNode(node); // see this method below
Node<T> nextOfMid = mid.next;
mid.next = null;
// recursively sorting the two halves
Node<T> left = mergeSort(node); // starts at head, see argumnent above
Node<T> right = mergeSort(nextOfMid); // starts just past halfway point
// Merge the sorted halves
return merge(left, right);
}
// Helper method to merge two sorted lists
private Node<T> merge(Node<T> left, Node<T> right) {
Node<T> result = null;
// testing for possible cases with single lists, thanks ChatGPT
if (left == null) {
return right;
}
if (right == null) {
return left;
}
// choosing the smaller value
// once chosen, the recursion is called again
if (left.data.compareTo(right.data) <= 0) {
result = left;
result.next = merge(left.next, right);
} else {
result = right;
result.next = merge(left, right.next);
}
return result;
}
// this finds the middle node of a linked list from a given node
private Node<T> getMiddleFromNode(Node<T> node) {
if (node == null) {
return node;
}
Node<T> slow = node;
Node<T> fast = node.next;
while (fast != null) {
fast = fast.next;
if (fast != null) {
slow = slow.next;
fast = fast.next;
}
}
return slow;
}
// new QUICK SORT method
// thanks again, chatGPT
public void quickSort() {
Node<T> end = head;
// getting the end node
for (int i = 0; i < this.size; i++) {
end = end.next;
}
// calling the other quicksort method
this.quickSort(head, end);
}
// COURTESY OF GEEKS4GEEKS
// Takes first and last node,
// but do not break any links in
// the whole linked list
private Node<T> partitionLast(Node<T> start, Node<T> end)
{
if (start == end || start == null || end == null)
return start;
Node<T> pivot_prev = start;
Node<T> curr = start;
Node<T> pivot = end;
// iterate till one before the end,
// no need to iterate till the end
// because end is pivot
while (start != end) {
if (curr.data.compareTo(pivot.data) < 0) {
// keep tracks of last modified item
pivot_prev = curr;
T temp = curr.data;
curr.data = start.data;
start.data = temp;
curr = curr.next;
}
start = start.next;
}
// Swap the position of curr i.e.
// next suitable index and pivot
T temp = curr.data;
curr.data = pivot.data;
end.data = temp;
// Return one previous to current
// because current is now pointing to pivot
return pivot_prev;
}
private void quickSort(Node<T> start, Node<T> end)
{
if (start == null || start == end
|| start == end.next)
return;
// Split list and partition recurse
Node<T> pivot_prev = partitionLast(start, end);
quickSort(start, pivot_prev);
// If pivot is picked and moved to the start,
// that means start and pivot is same
// so pick from next of pivot
if (pivot_prev != null && pivot_prev == start)
quickSort(pivot_prev.next, end);
// If pivot is in between of the list,
// start from next of pivot,
// since we have pivot_prev, so we move two nodes
else if (pivot_prev != null
&& pivot_prev.next != null)
quickSort(pivot_prev.next.next, end);
}
}
public class Main {
// new main method for testing all sorts with Pokemon
public static void main(String[] args) {
// creating an array of Pokemon
Pokemon[] pokemonArray = new Pokemon[] {
new Pokemon("Machop", new String[]{"Fighting"}, 66, 14),
new Pokemon("Arrokuda", new String[]{"Water"}, 846, 23),
new Pokemon("Rattata", new String[]{"Normal"}, 19, 4),
new Pokemon("Cranidos", new String[]{"Rock"}, 408, 25),
new Pokemon("Scolipede", new String[]{"Poison", "Bug"}, 545, 34),
new Pokemon("Avalugg", new String[]{"Ice"}, 713, 43),
new Pokemon("Camerupt", new String[]{"Fire", "Ground"}, 323, 39),
new Pokemon("Bastiodon", new String[]{"Rock", "Steel"}, 411, 36)
};
// creating a LinkedList of Pokemon
LinkedList<Pokemon> pokemonList = new LinkedList<>();
// adding Pokemon to the LinkedList
for (Pokemon pokemon : pokemonArray) {
pokemonList.add(pokemon);
}
// sorting and displaying with all different sort keys
int i = 0;
for (Pokemon.SortKey sortKey : Pokemon.SortKey.values()) {
// incrementing i, which determines sort type
i++;
// setting the current sort key
Pokemon.setCurrentSortKey(sortKey);
// calling sort for the LinkedList class depending on i
switch (i) {
case 1:
pokemonList.bubbleSort();
break;
case 2:
pokemonList.insertionSort();
break;
case 3:
pokemonList.mergeSort();
break;
case 4:
pokemonList.quickSort();
break;
}
// displaying the sorted LinkedList
System.out.println("Sorted by " + sortKey + ": " + pokemonList);
}
}
}
Main.main(null);
Sorted by NAME: [Arrokuda (lvl. 23), Avalugg (lvl. 43), Bastiodon (lvl. 36), Camerupt (lvl. 39), Cranidos (lvl. 25), Machop (lvl. 14), Rattata (lvl. 4), Scolipede (lvl. 34)]
Sorted by TYPES: [Rattata (lvl. 4), Camerupt (lvl. 39), Arrokuda (lvl. 23), Avalugg (lvl. 43), Machop (lvl. 14), Scolipede (lvl. 34), Cranidos (lvl. 25), Bastiodon (lvl. 36)]
Sorted by DEX_NUMBER: [Rattata (lvl. 4), Machop (lvl. 14), Camerupt (lvl. 39), Cranidos (lvl. 25), Bastiodon (lvl. 36), Scolipede (lvl. 34), Avalugg (lvl. 43), Arrokuda (lvl. 23)]
Sorted by LEVEL: [Rattata (lvl. 4), Machop (lvl. 14), Arrokuda (lvl. 23), Cranidos (lvl. 25), Scolipede (lvl. 34), Bastiodon (lvl. 36), Camerupt (lvl. 39), Avalugg (lvl. 43)]
Reflection on Algorhythmic
I was robbed. Mr. Mortensen, I was robbed. In broad daylight, too. Can you believe it? I certainly can’t. I just cannot. It was a blowout—we swept the competition with ease. And yet, what happened? What happened to us, Mr. Mortensen? We had our joy, our lives, our souls TAKEN from us. I will not stand for this.
My contributions to this event were writing the script with Aiden and act act acting! I also helped send out examples for this very review to other group members to help meet requirements. (Don’t worry, nobody copied.)
Anyway, that was a lot of fun. We want to do it again at night at the museum. Raah!