MAT3514 - Abstract Data Type (ADT) and List ADT

#dsa #java #schoolwork

03/10/2024 25 Min.

Written by: Yuk

Abstract Data Type (ADT) and List ADT - Tran Ba Tuan - HUS - VNU

I, Intuition

Students need to grasp abstract data types (ADT).
Students must comprehend List and be able to implement ArrayList and LinkedList.
Students need to understand the definition, operations and the complexity that comes along with common LinkedList like SinglyLinkedList, DoublyLinkedList and CircularLinkedList.

II, Practice

Work 1.

Complete the following class:

public class Fraction {

    private float numerator;
    private float denominator;

    public Fraction(float numerator, float denominator) {
        /*TODO*/
    }

    public Fraction add(Fraction c) {
        /*TODO*/
    }

    public Fraction minus(Fraction c) {
        /*TODO*/
    }

    public Fraction multi(Fraction c) {
        /*TODO*/
    }

    public Fraction divi(Fraction c) {
        /*TODO*/
    }

    public Fraction normalize(Fraction c) {
        /*TODO*/
    }

    public float getNumerator() {
        return numerator;
    }

    public float getDenominator() {
        return denominator;
    }

    @Override
    public String toString() {
        /*TODO*/
    }
}

Complete the following requirements:
- Complete the function bodies.
- Input a sequence of n fractions.
- Print the fraction at the vth position in the sequence.
- Calculate the sum of n fractions, giving the result as a simplified fraction.
- Perform the same for subtraction, multiplication, and division of n fractions.
- (*) Propose at least one use case for the created fraction type, write a function to implement that requirement.

public class Fraction {

    private float numerator;
    private float denominator;

    public Fraction(float numerator, float denominator) {
        if (denominator == 0) {
            throw new IllegalArgumentException("Denominator cannot be zero");
        }
        this.numerator = numerator;
        this.denominator = denominator;
    }

    public Fraction add(Fraction c) {
        float newNumerator = this.numerator * c.denominator + c.numerator * this.denominator;
        float newDenominator = this.denominator * c.denominator;
        return simplify(new Fraction(newNumerator, newDenominator));
    }

    public Fraction minus(Fraction c) {
        float newNumerator = this.numerator * c.denominator - c.numerator * this.denominator;
        float newDenominator = this.denominator * c.denominator;
        return simplify(new Fraction(newNumerator, newDenominator));
    }

    public Fraction multiply(Fraction c) {
        float newNumerator = this.numerator * c.numerator;
        float newDenominator = this.denominator * c.denominator;
        return simplify(new Fraction(newNumerator, newDenominator));
    }

    public Fraction divide(Fraction c) {
        if (c.numerator == 0) {
            throw new IllegalArgumentException("Cannot divide by zero");
        }
        float newNumerator = this.numerator * c.denominator;
        float newDenominator = this.denominator * c.numerator;
        return simplify(new Fraction(newNumerator, newDenominator));
    }

    public Fraction simplify(Fraction c) {
        float gcd = gcd(c.numerator, c.denominator);
        return new Fraction(c.numerator / gcd, c.denominator / gcd);
    }

    private float gcd(float a, float b) {
        while (b != 0) {
            float temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }

    public float getNumerator() {
        return numerator;
    }

    public float getDenominator() {
        return denominator;
    }

    public String toMixedNumber() {
        int wholeNumber = (int) (numerator / denominator);
        float remainder = numerator % denominator;
        if (remainder == 0) {
            return String.valueOf(wholeNumber);
        }
        return wholeNumber + " " + remainder + "/" + denominator;
    }

    @Override
    public String toString() {
        return numerator + "/" + denominator;
    }
}

import java.util.Scanner;

public class Work1 {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // Input n fractions
        System.out.print("Enter the number of fractions: ");
        int n = scanner.nextInt();
        Fraction[] fractions = new Fraction[n];

        for (int i = 0; i < n; i++) {
            System.out.print("Enter numerator and denominator for fraction " + (i + 1) + ": ");
            float numerator = scanner.nextFloat();
            float denominator = scanner.nextFloat();
            fractions[i] = new Fraction(numerator, denominator);
        }

        // Print fraction at v-th position
        System.out.print("Enter the position (v) of the fraction to print: ");
        int v = scanner.nextInt();
        if (v >= 1 && v <= n) {
            System.out.println("Fraction at position " + v + ": " + fractions[v - 1]);
        } else {
            System.out.println("Invalid position");
        }

        // Calculate sum, subtraction, multiplication, and division of all fractions
        Fraction sum = fractions[0];
        Fraction difference = fractions[0];
        Fraction product = fractions[0];
        Fraction quotient = fractions[0];

        for (int i = 1; i < n; i++) {
            sum = sum.add(fractions[i]);
            difference = difference.minus(fractions[i]);
            product = product.multiply(fractions[i]);
            quotient = quotient.divide(fractions[i]);
        }

        System.out.println("Sum of fractions: " + sum);
        System.out.println("Difference of fractions: " + difference);
        System.out.println("Product of fractions: " + product);
        System.out.println("Quotient of fractions: " + quotient);

        // Proposed: from fraction to mixed number
        System.out.println("Fraction 18/4 to Mixed Number: " + new Fraction(18, 4).toMixedNumber());

        scanner.close();
    }
}

Enter the number of fractions: 4
Enter numerator and denominator for fraction 1: 1 2
Enter numerator and denominator for fraction 2: 2 3
Enter numerator and denominator for fraction 3: 4 5
Enter numerator and denominator for fraction 4: 6 7
Enter the position (v) of the fraction to print: 2
Fraction at position 2: 2.0/3.0
Sum of fractions: 593.0/210.0
Difference of fractions: 383.0/-210.0
Product of fractions: 8.0/35.0
Quotient of fractions: 35.0/32.0
Fraction 18/4 to Mixed Number: 4 2.0/4.0

Work 2.

Complete the followings:
Interface ListInterface<T> extends Iterable<T>

public interface ListInterface<T> extends Iterable<T> {

    public void add(T data);

    public T get(int i);

    public void set(int i, T data);

    public void remove(T data);

    public boolean isContain(T data);

    public int size();

    public boolean isEmpty();

}

Class SimpleArrayList<T> implements ListInterface<T>

import java.util.Iterator;

@SuppressWarnings("unchecked")
public class SimpleArrayList<T> implements ListInterface<T> {

    private T[] array;
    private int n = 0;
    private int defaultSize = 100;


    public SimpleArrayList() {
        array = (T[]) new Object[defaultSize];
        /*TODO*/
    }

    public SimpleArrayList(int capacity) {
        /*TODO*/
    }

    public void add(T data) {
        /*TODO*/
    }

    public T get(int i) {
        /*TODO*/
    }

    public void set(int i, T data) {
        /*TODO*/
    }

    public void remove(T data) {
        /*TODO*/
    }

    public boolean isContain(T data) {
        /*TODO*/
    }

    public int size() {
        /*TODO*/
    }

    public boolean isEmpty() {
        /*TODO*/
    }

    public Iterator<T> iterator() {
        /*TODO*/
    }

}

import java.util.Iterator;

@SuppressWarnings("unchecked")
public class SimpleArrayList<T> implements ListInterface<T> {

    private T[] array;
    private int n = 0;
    private static final int defaultSize = 100;

    public SimpleArrayList() {
        array = (T[]) new Object[defaultSize];
    }

    public SimpleArrayList(int capacity) {
        if (capacity < 1)
            throw new IllegalArgumentException("Capacity can't be less than 1.");
        array = (T[]) new Object[capacity];
    }

    public void add(T data) {
        if (n >= array.length) enlarge();
        array[n++] = data;
    }

    public T get(int i) {
        if (i >= n)
            throw new IndexOutOfBoundsException("Invalid index.");
        return array[i];
    }

    public void set(int i, T data) {
        if (i >= n)
            throw new IndexOutOfBoundsException("Invalid index.");
        array[i] = data;
    }

    public void remove(T data) {
        for (int i = 0; i < n; i++) {
            if (array[i].equals(data)) {
                remove(i);
                i--;
            }
        }
    }

    public void remove(int index) {
        if (index >= n)
            throw new IndexOutOfBoundsException("Invalid index.");
        System.arraycopy(array, index + 1, array, index, n - index - 1);
        n--;
        correct();
    }

    public boolean isContain(T data) {
        for (int i = 0; i < n; i++) {
            if (array[i].equals(data)) {
                return true;
            }
        }
        return false;
    }

    public int size() {
        return n;
    }

    public boolean isEmpty() {
        return n == 0;
    }

    @Override
    public Iterator<T> iterator() {
        return new Iterator<>() {
            private int currentIndex = 0;

            @Override
            public boolean hasNext() {
                return currentIndex < n;
            }

            @Override
            public T next() {
                if (!hasNext()) {
                    throw new IndexOutOfBoundsException("No more elements");
                }
                return array[currentIndex++];
            }
        };
    }

    private void enlarge() {
        T[] newArray = (T[]) new Object[array.length * 2];
        System.arraycopy(array, 0, newArray, 0, n);
        array = newArray;
    }

    private void correct() {
        for (int i = n; i < array.length; i++) {
            array[i] = null;
        }
    }

}

import java.util.Iterator;

public class Work2 {

    public static void main(String[] args) {
        SimpleArrayList<Integer> list = new SimpleArrayList<>(10);

        // Adding elements to the list
        list.add(3);
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);
        list.add(3);

        // Printing elements using iterator
        System.out.println("Elements in the list:");
        Iterator<Integer> iterator = list.iterator();
        while (iterator.hasNext()) {
            System.out.print(iterator.next() + " ");
        }
        System.out.println();

        // Checking the size of the list
        System.out.println("Size of the list: " + list.size());

        // Removing an element
        list.remove((Integer) 3);
        System.out.println("Elements after removing 3:");
        iterator = list.iterator();
        while (iterator.hasNext()) {
            System.out.print(iterator.next() + " ");
        }
        System.out.println();

        // Checking if the list contains certain elements
        System.out.println("List contains 2: " + list.isContain(2));
        System.out.println("List contains 3: " + list.isContain(3));

        // Testing the get and set methods
        System.out.println("Element at index 1: " + list.get(1));
        list.set(1, 10);
        System.out.println("Element at index 1 after setting it to 10: " + list.get(1));

        // Testing if the list is empty
        System.out.println("Is the list empty? " + list.isEmpty());

        // Removing all elements
        list.remove((Integer) 1);
        list.remove((Integer) 2);
        list.remove((Integer) 4);
        list.remove((Integer) 5);
        list.remove((Integer) 10);
        System.out.println("Is the list empty after removing all elements? " + list.isEmpty());
    }

}

Elements in the list:
3 1 2 3 4 5 3 
Size of the list: 7
Elements after removing 3:
1 2 4 5 
List contains 2: true
List contains 3: false
Element at index 1: 2
Element at index 1 after setting it to 10: 10
Is the list empty? false
Is the list empty after removing all elements? true

Work 3.

Class SimpleLinkedList<T>

import java.util.Iterator;

public class SimpleLinkedList<T> {

    private Node top = null;
    private Node bot = null;
    private int n = 0;

    class Node {
        T data;
        Node next;
    }

    public void add(T data) {
        /*TODO*/
    }

    public void addBot(T data) {
        /*TODO*/
    }

    public T get(int i) {
        /*TODO*/
    }

    public void set(int i, T data) {
        /*TODO*/
    }

    public boolean isContain(T data) {
        /*TODO*/
    }

    public int size() {
        /*TODO*/
    }

    public boolean isEmpty() {
        /*TODO*/
    }

    public T removeTop() {
        /*TODO*/
    }

    public T removeBot() {
        /*TODO*/
    }

    public void remove(T data) {
        /*TODO*/
    }

    public Iterator<T> iterator() {
        /*TODO*/
    }

}

import java.util.Iterator;

public class SimpleLinkedList<T> {

    private Node top = null;
    private Node bot = null;
    private int n = 0;

    class Node {
        T data;
        Node next;
        Node prev;

        public Node(T data) {
            this.data = data;
        }

        public Node getNext() {
            return next;
        }

        public Node getPrev() {
            return prev;
        }

        public void setNext(Node next) {
            this.next = next;
        }

        public void setPrev(Node prev) {
            this.prev = prev;
        }
    }

    public void add(T data) {
        Node newNode = new Node(data);
        if (isEmpty()) {
            top = bot = newNode;
        } else {
            newNode.setNext(top);
            top.setPrev(newNode);
            top = newNode;
        }
        n++;
    }

    public void addBot(T data) {
        Node newNode = new Node(data);
        if (isEmpty()) {
            top = bot = newNode;
        } else {
            bot.setNext(newNode);
            newNode.setPrev(bot);
            bot = newNode;
        }
        n++;
    }

    public T get(int i) {
        Node targetNode = getNodeByIndex(i);
        return targetNode != null ? targetNode.data : null;
    }

    public void set(int i, T data) {
        Node targetNode = getNodeByIndex(i);
        if (targetNode != null) {
            targetNode.data = data;
        }
    }

    public boolean isContain(T data) {
        Node current = top;
        while (current != null) {
            if (current.data.equals(data)) {
                return true;
            }
            current = current.getNext();
        }
        return false;
    }

    public int size() {
        return n;
    }

    public boolean isEmpty() {
        return n == 0;
    }

    public T removeTop() {
        if (isEmpty()) {
            return null;
        }
        T data = top.data;
        if (top == bot) {
            top = bot = null;
        } else {
            top = top.getNext();
            top.setPrev(null);
        }
        n--;
        return data;
    }

    public T removeBot() {
        if (isEmpty()) {
            return null;
        }
        T data = bot.data;
        if (top == bot) {
            top = bot = null;
        } else {
            bot = bot.getPrev();
            bot.setNext(null);
        }
        n--;
        return data;
    }

    public void remove(T data) {
        Node current = top;

        while (current != null) {
            if (current.data.equals(data)) {
                Node nextNode = current.getNext();

                if (current == top) {
                    removeTop();
                } else if (current == bot) {
                    removeBot();
                } else {
                    Node prevNode = current.getPrev();
                    prevNode.setNext(nextNode);
                    if (nextNode != null) {
                        nextNode.setPrev(prevNode);
                    }
                    n--;
                }

                current = nextNode;
            } else {
                current = current.getNext();
            }
        }
    }

    public Iterator<T> iterator() {
        return new Iterator<T>() {
            private Node current = top;

            @Override
            public boolean hasNext() {
                return current != null;
            }

            @Override
            public T next() {
                T data = current.data;
                current = current.getNext();
                return data;
            }
        };
    }

    private Node getNodeByIndex(int index) {
        if (index < 0 || index >= n) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + n);
        }

        Node current;
        if (index < n / 2) {
            current = top;
            for (int i = 0; i < index; i++) {
                current = current.getNext();
            }
        } else {
            current = bot;
            for (int i = n - 1; i > index; i--) {
                current = current.getPrev();
            }
        }
        return current;
    }

}

import java.util.Iterator;

public class Work3 {

    public static void main(String[] args) {
        // Create an instance of SimpleLinkedList
        SimpleLinkedList<Integer> list = new SimpleLinkedList<>();

        // Test isEmpty and size
        System.out.println("Is the list empty? " + list.isEmpty()); // Expected: true
        System.out.println("Size of the list: " + list.size()); // Expected: 0

        // Test add() - Add elements to the top
        list.add(10);
        list.add(20);
        list.add(30);
        System.out.println("After adding 30, 20, 10 at the top:");
        System.out.println("Size of the list: " + list.size()); // Expected: 3
        printList(list); // Expected: 30 -> 20 -> 10

        // Test addBot() - Add elements to the bottom
        list.addBot(5);
        list.addBot(1);
        System.out.println("After adding 5, 1 at the bottom:");
        System.out.println("Size of the list: " + list.size()); // Expected: 5
        printList(list); // Expected: 30 -> 20 -> 10 -> 5 -> 1

        // Test get() method
        System.out.println("Element at index 2: " + list.get(2)); // Expected: 10
        System.out.println("Element at index 4: " + list.get(4)); // Expected: 1

        // Test set() method
        list.set(2, 15);
        System.out.println("After setting index 2 to 15:");
        printList(list); // Expected: 30 -> 20 -> 15 -> 5 -> 1

        // Test isContain() method
        System.out.println("Is the list containing 20? " + list.isContain(20)); // Expected: true
        System.out.println("Is the list containing 100? " + list.isContain(100)); // Expected: false

        // Test removeTop() method
        System.out.println("Removing the top element: " + list.removeTop()); // Expected: 30
        printList(list); // Expected: 20 -> 15 -> 5 -> 1

        // Test removeBot() method
        System.out.println("Removing the bottom element: " + list.removeBot()); // Expected: 1
        printList(list); // Expected: 20 -> 15 -> 5

        // Test remove() method (remove all occurrences)
        list.add(15); // Add another 15 for testing removal of all occurrences
        System.out.println("After adding another 15:");
        printList(list); // Expected: 20 -> 15 -> 5 -> 15
        list.remove(15);
        System.out.println("After removing all occurrences of 15:");
        printList(list); // Expected: 20 -> 5

        // Final size check
        System.out.println("Final size of the list: " + list.size()); // Expected: 2
    }

    // Helper method to print the list
    public static <T> void printList(SimpleLinkedList<T> list) {
        Iterator<T> iterator = list.iterator();
        while (iterator.hasNext()) {
            System.out.print(iterator.next() + " -> ");
        }
        System.out.println("endlist");
    }

}

Is the list empty? true
Size of the list: 0
After adding 30, 20, 10 at the top:
Size of the list: 3
30 -> 20 -> 10 -> endlist
After adding 5, 1 at the bottom:
Size of the list: 5
30 -> 20 -> 10 -> 5 -> 1 -> endlist
Element at index 2: 10
Element at index 4: 1
After setting index 2 to 15:
30 -> 20 -> 15 -> 5 -> 1 -> endlist
Is the list containing 20? true
Is the list containing 100? false
Removing the top element: 30
20 -> 15 -> 5 -> 1 -> endlist
Removing the bottom element: 1
20 -> 15 -> 5 -> endlist
After adding another 15:
15 -> 20 -> 15 -> 5 -> endlist
After removing all occurrences of 15:
20 -> 5 -> endlist
Final size of the list: 2

Work 4.

Using the data structures from exercises 2 and 3, write a program to count the frequency of words in a given text input from the keyboard or a text file.
Create a WordCount object with two attributes: word and count. Override the equals(Object o) method for the WordCount object so that you can use the isContain method implemented in the data structures from previous exercises, or alternatively use the indexOf method of objects that implement the List interface.

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.Iterator;

public class WordCount {

    DoublyLinkedList<String> word = new DoublyLinkedList<>(); // Still the same class as SimpleLinkedList
    DoublyLinkedList<Integer> count = new DoublyLinkedList<>();

    public void countFromFile(String path) {
        try (BufferedReader reader = new BufferedReader(new FileReader(path))) {
            String line;
            while ((line = reader.readLine()) != null) {
                countFromInput(line);
            }
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    public void countFromInput(String input) {
        String[] words = input.split("\\s+");
        for (String w : words) {
            int index = indexOfWord(w);
            if (index == -1) {
                word.addBot(w);
                count.addBot(1);
            } else {
                count.set(index, count.get(index) + 1);
            }
        }
    }

    private int indexOfWord(String w) {
        Iterator<String> wordIterator = word.iterator();
        int index = 0;
        while (wordIterator.hasNext()) {
            if (wordIterator.next().equals(w)) {
                return index;
            }
            index++;
        }
        return -1;
    }

    public void printWordFrequency() {
        Iterator<String> wordIterator = word.iterator();
        Iterator<Integer> countIterator = count.iterator();

        StringBuilder result = new StringBuilder();
        while (wordIterator.hasNext() && countIterator.hasNext()) {
            String currentWord = wordIterator.next();
            Integer currentCount = countIterator.next();
            result.append(currentWord).append(": ").append(currentCount).append("; ");
        }

        if (result.length() > 0) {
            result.setLength(result.length() - 2);
        }

        System.out.println(result.toString());
    }

    public void clearData() {
        word = new DoublyLinkedList<>();
        count = new DoublyLinkedList<>();
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj) {
            return true;
        }
        if (obj == null || getClass() != obj.getClass()) {
            return false;
        }

        WordCount other = (WordCount) obj;

        if (word.size() != other.word.size() || count.size() != other.count.size()) {
            return false;
        }

        Iterator<String> wordIterator1 = word.iterator();
        Iterator<String> wordIterator2 = other.word.iterator();
        Iterator<Integer> countIterator1 = count.iterator();
        Iterator<Integer> countIterator2 = other.count.iterator();

        while (wordIterator1.hasNext() && wordIterator2.hasNext() && countIterator1.hasNext() && countIterator2.hasNext()) {
            String word1 = wordIterator1.next();
            String word2 = wordIterator2.next();
            Integer count1 = countIterator1.next();
            Integer count2 = countIterator2.next();

            if (!word1.equals(word2) || !count1.equals(count2)) {
                return false;
            }
        }

        return true;
    }

}

Sample data data.txt:

OVERWORLD
Mossy Cobblestone white check mark
Cobblestone white check mark 
Stone white check mark
Smooth Stone white check mark
Stone Brickwhite check mark
Brick Block white check mark
Andesitewhite check mark
Polished Andesite white check mark
Granite white check mark
Polished Granite white check mark
Dioritewhite check mark
Polished Dioritewhite check mark
Dripstone Block
Pointed Dripstone
Tuffwhite check mark
Calcite 
Cobbled Deepslatewhite check mark
Deepslatewhite check mark
Polished Deepslatewhite check mark
Deepslate Brickwhite check mark
Deepslate Tilewhite check mark
Obsidian
Crying Obsidian
NETHER
Blackstone
Polished Blackstone 
Polished Blackstone Brick
Basalt
Polished Basalt
Smooth Basalt
Netherrack white check mark
Nether Brick Block
Red Nether Brick Block
Magma Block
Glowstone Block
Shroomlight
MONUMENT
Sea Lantern 
Prismarine
Prismarine Brick
Dark Prismarine 
THE END
Endstone

import java.util.Scanner;

public class Work4 {

    public static void main(String[] args) {
        WordCount counter = new WordCount();

        // Count word frequencies from input
        Scanner scanner = new Scanner(System.in);
        System.out.println("Enter your input to count:");
        String input = scanner.nextLine();

        counter.countFromInput(input);
        System.out.println("Word frequencies in given input:");
        counter.printWordFrequency();
        // Clear current data
        counter.clearData();
        System.out.println("Counter's data after clearing data:");
        counter.printWordFrequency();

        // Create second counter
        WordCount secondCounter = new WordCount();

        // Count word frequencies from file
        System.out.println("Counting from file...");
        counter.countFromFile("data/data.txt");
        secondCounter.countFromFile("data/data.txt");

        // Test equals()
        System.out.println("Is the 2 counter equals after reading from the same file? " + counter.equals(secondCounter));
    }

}

Enter your input to count:
apple banana apple orange apple banana
Word frequencies in given input:
apple: 3; banana: 2; orange: 1
Counter's data after clearing data:

Counting from file...
Is the 2 counter equals after reading from the same file? true

III, Extra

Provide students with additional exercises to practice their programming skills.
Ensure a thorough understanding and proficient implementation of SinglyLinkedList, DoublyLinkedList and CircularLinkedList.

A. Singly Linked List

Work 5.

Solve at least 3 problems on LinkedList at codelearn.io
Singly Linked List - Intro

import java.util.Scanner;

public class ThisSiteHaveTerribleJavaSupportYetTheyStillAskForJavaLmaoooo {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] dataset = new int[n];
        for (int i = 0; i < n; i++) {
            dataset[i] = sc.nextInt();
        }
        LinkedList list = new LinkedList();
        for (int value : dataset) {
            list.append(value);
        }
        list.printList();
    }

    static class LinkedList {

        private Node head;
        private int size = 0;

        public void append(int data) {
            Node newNode = new Node(data);
            if (head == null) {
                head = newNode;
            } else {
                getNodeAtIndex(size - 1).next = newNode;
            }
            size++;
        }

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

        private Node getNodeAtIndex(int index) {
            if (index < 0 || index >= size) {
                throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
            }
            Node current = head;
            for (int i = 0; i < index; i++) {
                current = current.next;
            }
            return current;
        }

    }

    static class Node {
        int data;
        Node next;

        Node(int data) {
            this.data = data;
        }
    }
}

Singly Linked List - Appending

import java.util.Scanner;

public class LinkedListAppending {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] dataset = new int[n];
        for (int i = 0; i < n; i++) {
            dataset[i] = sc.nextInt();
        }
        LinkedList list = new LinkedList();

        for (int value : dataset) {
            list.append(value);
        }

        int at = sc.nextInt();
        int newData = sc.nextInt();

        list.insert(at, newData);

        list.printList();
    }

    // Add this method to LinkedList, rest of the code stays the same
    public void insert(int index, int data) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
        Node newNode = new Node(data);

        if (index == 0) {
            newNode.next = head;
            head = newNode;
        } else {
            Node current = getNodeAtIndex(index - 1);
            newNode.next = current.next;
            current.next = newNode;
        }
        size++;
    }
}

Singly Linked List - Deletion

import java.util.Scanner;

public class LinkedListDeletion {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] dataset = new int[n];
        for (int i = 0; i < n; i++) {
            dataset[i] = sc.nextInt();
        }
        LinkedList list = new LinkedList();

        for (int value : dataset) {
            list.append(value);
        }

        int at = sc.nextInt();
        list.delete(at);

        list.printList();
    }
    
    // Add this method to LinkedList, rest of the code stays the same
    public void delete(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }

        if (index == 0) {
            head = head.next;
        } else {
            Node current = getNodeAtIndex(index - 1);
            current.next = current.next.next;
        }

        size--;
    }
}

Singly Linked List - Search
Singly Linked List - Update
Singly Linked List - Delete Multiple
Doubly Linked List - Intro
Doubly Linked List - Appending
Doubly Linked List - Deletion
Circular Linked List - Intro
The site is so bad for Java I don’t even want to finish the rest lmao.

Work 6.

Solve LeetCode - Design Linked List

class MyLinkedList {

    static class Node {
        int data;
        Node next;
        Node prev;

        public Node(int data) {
            this.data = data;
        }

        public void setNext(Node next) {
            this.next = next;
        }

        public void setPrev(Node prev) {
            this.prev = prev;
        }

        public Node getNext() {
            return next;
        }

        public Node getPrev() {
            return prev;
        }
    }

    Node head;
    Node tail;
    int size;

    public MyLinkedList() {
        size = 0;
    }

    public int get(int index) {
        if (index < 0 || index >= size) return -1;
        return getNodeByIndex(index).data;
    }

    public void addAtHead(int val) {
        addAtIndex(0, val);
    }

    public void addAtTail(int val) {
        addAtIndex(size, val);
    }

    public void addAtIndex(int index, int val) {
        if (index < 0 || index > size) return;
        Node newNode = new Node(val);
        if (index == 0) {
            if (size == 0) head = tail = new Node(val);
            else {
                newNode.setNext(head);
                head.setPrev(newNode);
                head = newNode;
            }
        } else {
            if (index == size) {
                tail.setNext(newNode);
                newNode.setPrev(tail);
                tail = newNode;
            } else {
                Node prevNode = getNodeByIndex(index - 1);
                Node nextNode = getNodeByIndex(index);
                prevNode.setNext(newNode);
                newNode.setPrev(prevNode);
                newNode.setNext(nextNode);
                nextNode.setPrev(newNode);
            }
        }
        size++;
    }

    public void deleteAtIndex(int index) {
        if (index < 0 || index >= size) return;
        Node current = getNodeByIndex(index);
        Node prev = current.getPrev();
        Node next = current.getNext();
        if (prev != null) {
            prev.setNext(next);
        } else {
            head = next;
        }
        if (next != null) {
            next.setPrev(prev);
        } else {
            tail = prev;
        }
        size--;
    }

    private Node getNodeByIndex(int index) {
        Node current;
        if (index < size / 2) {
            current = head;
            for (int i = 0; i < index; i++) {
                current = current.getNext();
            }
        } else {
            current = tail;
            for (int i = size - 1; i > index; i--) {
                current = current.getPrev();
            }
        }
        return current;
    }

}

Work 7.

G4G - Count nodes of Linked List
Reference: G4G - Find Length of a Linked List: Iterative and Recursive
Iterative approach (Recommended):

public int getCount(Node head) {
    int count = 0;
    Node current = head;
    while(current.next != null) {
        current = current.next;
        count++;
    }
    return count;
}

Recursive approach (Not recommended - Prone to Stack Overflow):

public int getCount(Node head) {
    if (head == null) {
        return 0;
    }
    return 1 + getCount(head.next);
}

Work 8.

int getKthFromLast(Node head, int k) {
    int len = getCount(head);
    if (k - 1 > len) return -1;
    Node current = head;
    for (int i = 0; i < len - k + 1; i++) {
        current = current.next;
    }
    return current.data;
}

Work 9.

public static int count(Node head, int key) {
    Node current = head;
    int count = head.data == key ? 1 : 0;
    while(current.next != null) {
        current = current.next;
        if (current.data == key) count++;
    }
    return count;
}

Work 10.

public void printReverse(Node head) {
    Stack<Integer> stack = new Stack<>();
    Node current = head;

    while (current != null) {
        stack.push(current.data);
        current = current.next;
    }
    
    while (!stack.isEmpty()) {
        System.out.print(stack.pop() + " ");
    }
}

public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode current = head;
    
    while (current != null) {
        ListNode nextNode = current.next;
        current.next = prev;
        prev = current;
        current = nextNode;
    }

    return prev;
}

Work 11.

LeetCode - Palindrome Linked List
Reference: G4G - Function to check if a Singly Linked List is Palindrome
Convert to string two pointers approach

public boolean isPalindrome(ListNode head) {
    StringBuilder list = new StringBuilder();
    ListNode current = head;
    while (current != null) {
        list.append(current.val);
        current = current.next;
    }
    int start = 0;
    int end = list.toString().length() - 1;
    while (start < end) {
        if (list.toString().charAt(start) != list.toString().charAt(end)) {
            return false;
        }
        start++;
        end--;
    }
    return true;
}

Reverse second half approach

public boolean isPalindrome(ListNode head) {
    if (head == null || head.next == null) {
        return true;
    }
    ListNode slow = head;
    ListNode fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    ListNode p1 = head;
    ListNode p2 = reverseList(slow);
    boolean isPalindrome = true;
    while (p2 != null) {
        if (p1.val != p2.val) {
            isPalindrome = false;
            break;
        }
        p1 = p1.next;
        p2 = p2.next;
    }
    return isPalindrome;
}

private ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode current = head;
    while (current != null) {
        ListNode nextNode = current.next;
        current.next = prev;
        prev = current;
        current = nextNode;
    }
    return prev;
}

Work 12.

Solve LeetCode - Remove duplicates from sorted list

public ListNode deleteDuplicates(ListNode head) {
    if (head == null) return null;
    ListNode current = head;

    while (current.next != null) {
        if (current.val == current.next.val) {
            current.next = current.next.next;
        } else {
            current = current.next;
        }
    }
    return head;
}

Work 13.

G4G - Polynomial Addition
Reference: G4G - Adding two Polynomials using Linked List

public static Node addPolynomial(Node head1, Node head2) {
    if (head1 == null) return head2;
    if (head2 == null) return head1;
       
    Node dummy = new Node(0, 0);
    Node tail = dummy;

    Node current1 = head1;
    Node current2 = head2;

    while (current1 != null && current2 != null) {
        if (current1.pow > current2.pow) {
            tail.next = current1;
            tail = tail.next;
            current1 = current1.next;
        } else if (current1.pow < current2.pow) {
            tail.next = new Node(current2.coeff, current2.pow);
            tail = tail.next;
            current2 = current2.next;
        } else {
            int newCoeff = current1.coeff + current2.coeff;
            if (newCoeff != 0) {
                tail.next = new Node(newCoeff, current1.pow);
                tail = tail.next;
            }
            current1 = current1.next;
            current2 = current2.next;
        }
    }

    if (current1 != null) {
        tail.next = current1;
    }
    
    if (current2 != null) {
        while (current2 != null) {
            tail.next = new Node(current2.coeff, current2.pow);
            tail = tail.next;
            current2 = current2.next;
        }
    }
    return dummy.next;
}

B. Doubly Linked List

Work 14.

G4G - Insert a Node in Doubly Linked List
Reference: G4G - Doubly Linked List

Node addNode(Node head, int p, int x) {
    if (p == 0) {
        Node newNode = new Node(x);
        newNode.next = head;
        head = newNode;
        return head;
    }
    
    Node current = head;
    int i = -1;
    while (current != null) {
        i++;
        if (i == p) {
            break;
        }
        current = current.next;
    }

    if (current != null) {
        Node back = current.next;
        Node newNode = new Node(x);
        newNode.prev = current;
        newNode.next = back;
        if (back != null) {
            back.prev = newNode;
        }
        current.next = newNode;
    }

    return head;
}

Additional Requirements:

Work 15.

C. Circular Linked List

Work 16.

Additional Requirements:

G4G - Circular Linked List
Reference: G4G - Check if a Linked List is Circular Linked List
G4G - Sorted Insert for Circular Linked List
Reference: G4G - Sorted Insert for Circular Linked List
G4G - Deletion and Reverse in Linked List
Reference: G4G - Deletion Circular Linked List

Work 17.

I drop, these are miserable lmao, I really don’t hold this way of teaching highly. Simply put, if I don’t believe that I’m learning, then I won’t bother. The department’s teaching is still as insufferable as I remember, I just hope I can be free of this hell hole soon.