Creating a Linked List

This creates a simple linked list with type . This ensures we only have the right data in our data types. We then define a class within a class (nested class) to compartmentalize

public class LinkedList<T> {
    
    private class Node {
        T data;
        Node next;

        Node(T data) {
            this.data = data;
            this.next = null;
        }
    }

    private Node head;

    public LinkedList() {
        this.head = null;
    }

    public void add(T data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            return;
        }
        Node lastNode = head;
        while (lastNode.next != null) {
            lastNode = lastNode.next;
        }
        lastNode.next = newNode;
    }

    public void display() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        // Example usage:
        // Creating a linked list of integers
        LinkedList<Integer> intList = new LinkedList<>();
        intList.add(1);
        intList.add(2);
        intList.add(3);
        intList.display();

        // Creating a linked list of strings
        LinkedList<String> strList = new LinkedList<>();
        strList.add("Hello");
        strList.add("World");
        strList.display();
    }
}

LinkedList.main(null)

1 2 3 
Hello World

Sorting at Scale with Linked Lists

This is using the book class, however I will also sort one using our specific sort, insertion sort.

Class Below

class Book implements Comparable<Book> {
    private String name;
    private double deweyDecimalNumber;
    private String author;
    private String genre;

    public Book(String name, double deweyDecimalNumber, String author, String genre) {
        this.name = name;
        this.deweyDecimalNumber = deweyDecimalNumber;
        this.author = author;
        this.genre = genre;
    }
    
    public Book(String name, double deweyDecimalNumber){
        this.deweyDecimalNumber = deweyDecimalNumber;
        this.name = name;
        this.author = "";
        this.genre = "";
    }

    public String getName() {
        return name;
    }

    public double getDeweyDecimalNumber() {
        return deweyDecimalNumber;
    }

    public String getAuthor() {
        return author;
    }

    public String getGenre() {
        return genre;
    }
    public static double generateRandomDeweyDecimal() {
        Random rand = new Random();
        int classNumber = rand.nextInt(1000);
        int decimalNumber = rand.nextInt(1000);
        int cutterNumber = rand.nextInt(1000);
        return Double.parseDouble(String.format("%03d.%03d%03d", classNumber, decimalNumber, cutterNumber));
    }

    public static ArrayList<Book> createArray(int num){
        ArrayList<Book> arr = new ArrayList<Book>();
        for (int i = 0; i < num; i++){
            arr.add(new Book("Name " + i, generateRandomDeweyDecimal()));
        }
        return arr;
    }

    @Override 
    public int compareTo(Book target) {
        if (this.deweyDecimalNumber < target.deweyDecimalNumber) {
            return -1;
        } else if (this.deweyDecimalNumber > target.deweyDecimalNumber) {
            return 1;
        } else {
            int authorComparison = this.author.compareTo(target.author);
            if (authorComparison != 0) {
                return authorComparison;
            } else {
                return this.name.compareTo(target.name);
            }
        }
    }


    @Override
    public String toString() {
        return name + " by " + author + " - DDN: " + deweyDecimalNumber;
    }

    public static void main(String[] args) {
        Book[] books = {
            new Book("Book C", 123.45, "Author C", "Fiction"),
            new Book("Book A", 234.56, "Author A", "Fantasy"),
            new Book("Book B", 345.67, "Author B", "Science Fiction")
        };

        System.out.println("Books before sorting:");
        for (Book book : books) {
            System.out.println(book);
        }

        Arrays.sort(books);

        System.out.println("\nBooks after sorting:");
        for (Book book : books) {
            System.out.println(book);
        }
    }
}
Book.main(null);

Books before sorting:
Book C by Author C - DDN: 123.45
Book A by Author A - DDN: 234.56
Book B by Author B - DDN: 345.67

Books after sorting:
Book C by Author C - DDN: 123.45
Book A by Author A - DDN: 234.56
Book B by Author B - DDN: 345.67

class CollectableLibrary<Book>{
    private ArrayList<Book> books;

    public CollectableLibrary(ArrayList<Book> books) {
        this.books = books;
    }

    public ArrayList<Book> getBooks() {
        return books;
    }
}

import java.util.ArrayList;
import java.util.HashMap;

public class DeweyDecimalLibrary extends CollectableLibrary<Book> {
    private HashMap<Double, ArrayList<Book>> deweyCategories;

    public DeweyDecimalLibrary(ArrayList<Book> books) {
        super(books);
        deweyCategories = new HashMap<>();
        organizeByDeweyDecimal();
    }

    private void organizeByDeweyDecimal() {
        for (Book book : getBooks()) {
            double deweyDecimal = book.getDeweyDecimalNumber();
            // Round down to the nearest hundred
            double category = Math.floor(deweyDecimal / 100) * 100;
            if (!deweyCategories.containsKey(category)) {
                deweyCategories.put(category, new ArrayList<>());
            }
            deweyCategories.get(category).add(book);
        }

        // Sort books within each category
        for (ArrayList<Book> books : deweyCategories.values()) {
            Collections.sort(books);
        }
    }
    


    public void displayBooksByDeweyDecimal() {
        System.out.println("Books organized by Dewey Decimal:");
        for (double deweyDecimal : deweyCategories.keySet()) {
            System.out.println("Dewey Decimal: " + deweyDecimal);
            ArrayList<Book> books = deweyCategories.get(deweyDecimal);
            for (Book book : books) {
                System.out.println("  " + book);
            }
        }
    }

    public static void main(String[] args) {
        ArrayList<Book> books = new ArrayList<>();

        // Create 100 Book objects
        for (int i = 0; i < 100; i++) {
            double deweyDecimal = Math.random() * 1000;
            String name = "Book " + (i + 1);
            String author = "Author " + (i + 1);
            String genre = "Genre " + (i % 5 + 1);
            books.add(new Book(name, deweyDecimal, author, genre));
        }

        // Sort the books
        Book[] booksArray = books.toArray(new Book[0]);
        Arrays.sort(booksArray);

        DeweyDecimalLibrary library = new DeweyDecimalLibrary(new ArrayList<>(Arrays.asList(booksArray)));
        library.displayBooksByDeweyDecimal();
    }
}

DeweyDecimalLibrary.main(null);

Books organized by Dewey Decimal:
Dewey Decimal: 0.0
  Book 99 by Author 99 - DDN: 3.230744947271713
  Book 31 by Author 31 - DDN: 8.67988075113335
  Book 60 by Author 60 - DDN: 13.734545173957557
  Book 37 by Author 37 - DDN: 18.759149313214873
  Book 56 by Author 56 - DDN: 20.16501249563507
  Book 54 by Author 54 - DDN: 21.20601592748472
  Book 3 by Author 3 - DDN: 25.805284519291206
  Book 38 by Author 38 - DDN: 29.29762307217154
  Book 93 by Author 93 - DDN: 37.70103829383154
  Book 16 by Author 16 - DDN: 42.922372671229226
  Book 50 by Author 50 - DDN: 54.58295362233756
  Book 32 by Author 32 - DDN: 61.236793184966
  Book 48 by Author 48 - DDN: 65.78191228107045
  Book 79 by Author 79 - DDN: 74.58494454834508
  Book 67 by Author 67 - DDN: 87.0908613022794
  Book 22 by Author 22 - DDN: 93.95355682722739
Dewey Decimal: 300.0
  Book 21 by Author 21 - DDN: 311.2866888313235
  Book 96 by Author 96 - DDN: 335.4763728493042
  Book 58 by Author 58 - DDN: 343.80645218877214
  Book 4 by Author 4 - DDN: 350.41110564810094
  Book 45 by Author 45 - DDN: 352.10027591504513
  Book 91 by Author 91 - DDN: 352.9788665710821
  Book 9 by Author 9 - DDN: 358.60357615878513
  Book 97 by Author 97 - DDN: 388.5260151728295
  Book 23 by Author 23 - DDN: 394.299837338432
Dewey Decimal: 600.0
  Book 71 by Author 71 - DDN: 607.7173467893895
  Book 51 by Author 51 - DDN: 614.5866498026671
  Book 12 by Author 12 - DDN: 619.768315944798
  Book 65 by Author 65 - DDN: 625.3438124082624
  Book 44 by Author 44 - DDN: 636.3090409097948
  Book 43 by Author 43 - DDN: 638.2387057878053
  Book 30 by Author 30 - DDN: 638.963566766506
  Book 78 by Author 78 - DDN: 643.447658214175
  Book 34 by Author 34 - DDN: 646.1607615278242
  Book 95 by Author 95 - DDN: 647.6752867776627
  Book 64 by Author 64 - DDN: 673.6374796416201
  Book 84 by Author 84 - DDN: 677.9749649398117
  Book 89 by Author 89 - DDN: 683.4443178416453
  Book 92 by Author 92 - DDN: 698.1344625954679
Dewey Decimal: 700.0
  Book 62 by Author 62 - DDN: 703.8268066884511
  Book 7 by Author 7 - DDN: 707.6448516999167
  Book 13 by Author 13 - DDN: 721.5705813613358
  Book 39 by Author 39 - DDN: 726.3923116552876
  Book 26 by Author 26 - DDN: 735.9992026373799
  Book 11 by Author 11 - DDN: 741.8184326798139
  Book 81 by Author 81 - DDN: 758.5363566901814
  Book 46 by Author 46 - DDN: 763.7929472901247
Dewey Decimal: 100.0
  Book 83 by Author 83 - DDN: 122.72187325611073
  Book 88 by Author 88 - DDN: 123.03846387568052
  Book 17 by Author 17 - DDN: 124.00527061703248
  Book 2 by Author 2 - DDN: 148.2173151406636
  Book 76 by Author 76 - DDN: 150.87892253181067
  Book 69 by Author 69 - DDN: 156.84565026585318
  Book 1 by Author 1 - DDN: 183.3550262653958
  Book 74 by Author 74 - DDN: 185.73886311916942
Dewey Decimal: 200.0
  Book 5 by Author 5 - DDN: 212.88130053667598
  Book 63 by Author 63 - DDN: 225.17812270019812
  Book 59 by Author 59 - DDN: 231.62523621167165
  Book 77 by Author 77 - DDN: 237.10275996989094
  Book 66 by Author 66 - DDN: 244.6122460096668
  Book 47 by Author 47 - DDN: 245.06173032170753
  Book 15 by Author 15 - DDN: 247.82346742274854
  Book 98 by Author 98 - DDN: 251.4963223843759
  Book 10 by Author 10 - DDN: 269.43950781157986
  Book 100 by Author 100 - DDN: 270.5474338215861
  Book 36 by Author 36 - DDN: 278.13055032198355
  Book 18 by Author 18 - DDN: 279.0076376306245
  Book 85 by Author 85 - DDN: 287.5977041294294
  Book 52 by Author 52 - DDN: 296.71641269057545
Dewey Decimal: 400.0
  Book 86 by Author 86 - DDN: 413.83357131256525
  Book 82 by Author 82 - DDN: 428.30373127147425
  Book 94 by Author 94 - DDN: 439.91940283546785
  Book 40 by Author 40 - DDN: 447.734395818521
  Book 49 by Author 49 - DDN: 452.22469441468314
  Book 28 by Author 28 - DDN: 457.2406952523337
  Book 72 by Author 72 - DDN: 459.2276871721019
  Book 27 by Author 27 - DDN: 470.5785088613941
  Book 8 by Author 8 - DDN: 478.8350895401002
Dewey Decimal: 800.0
  Book 90 by Author 90 - DDN: 801.1593401998316
  Book 29 by Author 29 - DDN: 826.143737422904
  Book 80 by Author 80 - DDN: 831.0336861289428
  Book 75 by Author 75 - DDN: 831.2621301548512
  Book 25 by Author 25 - DDN: 841.8640462695389
  Book 33 by Author 33 - DDN: 852.1491275367715
  Book 70 by Author 70 - DDN: 852.9805535563224
  Book 24 by Author 24 - DDN: 866.1227047449373
  Book 61 by Author 61 - DDN: 876.5435203513096
  Book 6 by Author 6 - DDN: 879.4268518306764
  Book 57 by Author 57 - DDN: 885.1565050898159
  Book 87 by Author 87 - DDN: 899.3717840581728
Dewey Decimal: 900.0
  Book 53 by Author 53 - DDN: 914.917211984779
  Book 14 by Author 14 - DDN: 946.5911279256482
  Book 35 by Author 35 - DDN: 957.204117723634
  Book 20 by Author 20 - DDN: 960.0714305516096
  Book 55 by Author 55 - DDN: 965.7258477954341
  Book 41 by Author 41 - DDN: 986.5912237330082
  Book 19 by Author 19 - DDN: 993.0608986980834
Dewey Decimal: 500.0
  Book 73 by Author 73 - DDN: 513.1607401779488
  Book 42 by Author 42 - DDN: 528.4409995451263
  Book 68 by Author 68 - DDN: 547.1980741236977

Now Sorting with Insertion Sort

import java.util.ArrayList;

public abstract class Sorting {

    private ArrayList<Book> toSort;

    public Sorting(ArrayList<Book> toSort){
        this.toSort = toSort; // Initializes sorting algorithm
    }

    abstract void Sort(ArrayList<Book> toSort);  // Sorting method to be implemented
 
    abstract double worstCaseTime(); // Worst case (not time, but amount of parsings)

    public double doSort(){ 
        double start = System.currentTimeMillis();
        Sort(this.toSort);
        double end = System.currentTimeMillis();
        return (end - start)*1000;
    }

    public ArrayList<Book> getToSort() {
        return toSort;
    }

    public void setToSort(ArrayList<Book> toSort) {
        this.toSort = toSort;
    }

}

import java.util.ArrayList;

public class InsertionSort extends Sorting{

    public InsertionSort(ArrayList<Book> toSort) {
        super(toSort);
    }
    
    @Override
    void Sort(ArrayList<Book> toSort) {
        int n = toSort.size();
    for (int i = 1; i < n; i++) {
        Book key = toSort.get(i);
        int j = i - 1;

        while (j >= 0 && toSort.get(j).compareTo(key) > 0) {
            toSort.set(j + 1, toSort.get(j));
            j = j - 1;
        }
        toSort.set(j + 1, key);
    }
    }

    @Override
    double worstCaseTime(){
        return (this.getToSort().size())^2;
    }

    public static void main(String args[]){
        ArrayList<Book> books = Book.createArray(1000);

        InsertionSort b = new InsertionSort(books);

        double a = b.doSort();
        System.out.println(a);
    }
}

InsertionSort.main(null);


43000.0