Data Structures in Java

// from RevisionLabTest/LinkedList.java (annotated)
public class LinkedList {
    // head points to the first node in the list; null means empty
    public Node head;

    public LinkedList() {
        this.head = null; // initial empty list
    }

    // add item to front (O(1))
    public void addToHead(String data) {
        // create new node and make it the head, linking old head as next
        Node newHead = new Node(data);
        Node currentHead = this.head;
        this.head = newHead; // new node becomes head
        if (currentHead != null) {
            this.head.setNextNode(currentHead); // link to previous head
        }
    }

    // add item to end (O(n) here because we traverse). If you frequently append,
    // keep a tail reference for O(1) append.
    public void addToTail(String data) {
        Node tail = this.head;
        if (tail == null) {
            // empty list -> new node becomes head
            this.head = new Node(data);
        } else {
            while (tail.getNextNode() != null) {
                tail = tail.getNextNode(); // walk to last
            }
            tail.setNextNode(new Node(data)); // append new node
        }
    }

    // remove and return head data (O(1))
    public String removeHead() {
        Node removedHead = this.head;
        if (removedHead == null) {
            return null; // nothing to remove
        }
        this.head = removedHead.getNextNode(); // drop reference to old head
        return removedHead.data; // return payload
    }
}

// from RevisionLabTest/Queue.java (annotated)
public class Queue {
    // underlying linked list and counters
    public LinkedList queue;
    public int size;         // current size
    public int maxSize;      // optional capacity

    public Queue() { this(DEFAULT_MAX_SIZE); }

    public Queue(int maxSize) {
        this.queue = new LinkedList();
        this.size = 0;
        this.maxSize = maxSize;
    }

    public boolean isEmpty() {
        return this.size == 0;
    }

    // enqueue uses addToTail (O(n) here). To make enqueue O(1), add a tail pointer
    public void enqueue(String data) {
        this.queue.addToTail(data);
        this.size++;
        System.out.println("Added " + data + "! Queue size is now " + this.size);
    }

    // dequeue removes head (O(1)). Use an exception type for normal runtime error cases.
    public String dequeue() {
        if (!this.isEmpty()) {
            String data = this.queue.removeHead();
            this.size--;
            System.out.println("Removed " + data + "! Queue size is now " + this.size);
            return data;
        } else {
            // Prefer throwing java.util.NoSuchElementException for empty queue
            throw new java.util.NoSuchElementException("Queue is empty!");
        }
    }

    public String peek() {
        if (this.isEmpty()) return null;
        // avoid exposing internals; create a safe getter in LinkedList when possible
        return this.queue.head.data;
    }
}

// from Lab16/BST.java (annotated)
public class BST {
    public Node root; // root node of the tree

    public BST() {
        root = null; // empty tree
    }

    public void add(int value) {
        root = add(root, value); // recursive insertion returns subtree root
    }

    private Node add(Node root, int value) {
        if (root == null)
            root = new Node(value); // create node when we reach insertion point

        else if (root.getData() < value)
            root.rightChild = add(root.rightChild, value); // go right for larger values

        else if (root.getData() > value)
            root.leftChild = add(root.leftChild, value); // go left for smaller values

        // duplicates are ignored (no equal branch) — decide a policy if duplicates should be stored
        return root; // return subtree root so callers can attach it
    }
}

// from Assignment2/RandomSumPairs.java (annotated)
public static Queue randomInteger(int n) {
    Queue queue = new LinkedList<>();
    for (int i = 0; i < n; i++) {
        // generate random integer in [1,10]
        int random = (int) (Math.random() * 10) + 1; // Math.random() -> [0,1)
        queue.offer(random);
    }
    return queue;
}

public static void sumPairs(Queue queue) {
    // This method takes pairs of integers from the queue and pushes their sums.
    // It uses a stack temporarily to reverse order; consider simpler approaches if order doesn't matter.
    Stack stack = new Stack<>();
    while (!queue.isEmpty()) {
        if (queue.size() >= 2) {
            int num1 = queue.poll();
            int num2 = queue.poll();
            int sum = num1 + num2;
            stack.push(sum);
        } else {
            // leftover single element gets preserved
            stack.push(queue.poll());
        }
    }
    // push back to queue so results are available for caller
    while (!stack.isEmpty()) queue.offer(stack.pop());
}

// NOTE: Avoid System.console() for input in IDEs; prefer java.util.Scanner(System.in) for portability.

// from Lab00/Employee.java (excerpt)
public class Employee {
    // Fields use upper-case in repo; prefer lowerCamelCase: id, name, position, salary
    private int ID;
    private String Name;
    private String Position;
    private double Salary;

    public int getID() { return ID; }
    // This method should be named getName() to follow JavaBean convention
    public String Name() { return Name; }

    // display prints internal state; consider overriding toString() for easier logging
    public void display() {
        System.out.println("Name: " + Name + "\nID: " + ID + "\nPosition: " + Position + "\nSalary: " + Salary);
    }
}