Java Data Structures: Sorted Lists and Hash Tables

Sorted Linked List Insertion

The following method, insertAtSorted(T x), demonstrates how to insert an element into a sorted linked list while maintaining the correct order.

public void insertAtSorted(T x) {
    if (this.length == 0) {
        this.firstNode = nn;
        this.lastNode = nn;
    } else if (((Comparable)x).compareTo(this.firstNode.data) < 0) {
        nn.next = this.firstNode;
        this.firstNode = nn;
    } else {
        SNode<T> curr = this.firstNode;
        while (((Comparable)x).compareTo(curr.next.data) >= 0) {
            curr = curr.next;
        }
        nn.next = curr.next;
        curr.next = nn;
    }
    this.length++;
}

Priority Queue Enqueue Implementation

The enqueuer method handles inserting items into a priority-based array structure by finding the appropriate index for the new Item.

public void enqueuer(int info, int p) {
    Item x = new Item(info, p);
    if (this.tailidx == -1) {
        this.arr[0] = x;
        this.tailidx++;
    } else if (x.compareTo(this.arr[this.tailidx]) <= 0) {
        this.arr[this.tailidx + 1] = x;
        this.tailidx++;
    } else {
        int ins_idx = 0;
        while (this.arr[ins_idx].compareTo(x) >= 0) {
            ins_idx++;
        }
        for (int i = this.tailidx; i >= ins_idx; i--) {
            this.arr[i + 1] = this.arr[i];
        }
        this.arr[ins_idx] = x;
        this.tailidx++;
    }
}

Custom Hash Table with Chaining

Constructor and Initialization

The CustomHT constructor initializes an array of ArrayLists to handle collisions via chaining. Note that the array itself is initialized without generic brackets, while each element is set with them.

public CustomHT(int sz) {
    this.arr = new ArrayList[sz]; // Array of generics: initialize array without generic brackets
    for (int i = 0; i < sz; i++) {
        this.arr[i] = new ArrayList<Item<T1, T2>>(); // Setting each element with generic brackets
    }
}

The Put Method

The put method inserts or updates a key-value pair in the hash table using the key's hashCode.

public void put(T1 key, T2 info) {
    int hc = key.hashCode();
    hc = Math.abs(hc % this.arr.length);
    ArrayList<Item<T1, T2>> list1hc = this.arr[hc];
    for (int i = 0; i < list1hc.size(); i++) {
        Item<T1, T2> curritem = list1hc.get(i);
        if (curritem.key.equals(key)) {
            curritem.value = info;
            return; // Exit
        }
    }
    Item<T1, T2> it = new Item<T1, T2>(key, info);
    list1hc.add(it);
}

The Remove Method

The remove method deletes an entry by its key and returns the associated value if found.

public T2 remove(T1 key) {
    int hc = key.hashCode();
    hc = Math.abs(hc % this.arr.length);
    ArrayList<Item<T1, T2>> list1 = this.arr[hc];
    for (int i = 0; i < list1.size(); i++) {
        Item<T1, T2> curritem = list1.get(i);
        if (curritem.key.equals(key)) {
            Item<T1, T2> x = list1.remove(i);
            return x.value; // Exit
        }
    }
    return null;
}