Thread - Data Structure

#dsa #java #old-post

Last updated: 03/11/2024

Written by: Yuk

Thread info: Last updated: 03-11-2024
    - 30-10-2024: Added MyArrayList and MyLinkedList
    - 31-10-2024: Moved Test Classes to a separate section
                  Finished MyLinkedList
                  Added MyDoublyLinkedList
    - 03-11-2024: Finished MyDoublyLinkedList

Data Structure

We implement basic data structures that will only work with int first, evaluate the performance of the operations, and provide test classes using JUnit for each of the data structure.

Linear Data Structure

Interface and Abstract Parent Class for Lists

To truly follow the fashion of Java, we use interface MyList and MyAbstractList. These classes will ensure consistency and handle basic operations like isEmpty(), toString(),…

import java.util.Iterator;
import java.util.List;

public interface MyList {

    int size();

    void append(int x);

    void insertAtIndex(int x, int i);

    void setAtIndex(int x, int i);

    int get(int i);

    void deleteAtIndex(int i);

    void deleteAllOf(int x);

    int[] toArray();

    List<Integer> toList();

    boolean isEmpty();

    Iterator<Integer> iterator();

}

public abstract class MyAbstractList implements MyList {

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

    public void checkBound(int index, int limit) {
        if (index < 0 || index >= limit)
            throw new IndexOutOfBoundsException
            ("Invalid index: " + index + " for length: " + size());
    }

    @Override
    public String toString() {
        StringBuilder list = new StringBuilder("[");
        for (int i = 0; i < size(); i++) {
            if (i == size() - 1) list.append(get(i));
            else list.append(get(i)).append(", ");
        }
        return list.append("]").toString();
    }

}

MyArrayList

A resizable array that can grow or shrink as needed. It offers efficient random access, insertion, and removal of elements. It’s widely used in data structures and algorithms due to its flexibility and ease of use. Below is the full implementation and test class, we will evaluate each operation methods. (You can use the 🔼 button to collapse the codeblocks, the 🔼 button at the header on top of the page will allow you to collapse all codeblocks)

import java.util.Arrays;
import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;

public class MyArrayList extends MyAbstractList {

    private static final int DEFAULT_CAPACITY = 4;
    private int size;
    private int[] data;

    public MyArrayList() {
        data = new int[DEFAULT_CAPACITY];
        size = 0;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public void append(int x) {
        if (size >= data.length) enlarge();
        data[size++] = x;
    }

    @Override
    public void insertAtIndex(int x, int i) {
        checkBound(i, size + 1);
        if (i == size) append(x);
        else {
            if (size >= data.length) enlarge();
            else {
                System.arraycopy(data, i, data, i + 1, size - i);
                data[i] = x;
                size++;
            }
        }
    }

    @Override
    public void setAtIndex(int x, int i) {
        checkBound(i, size);
        data[i] = x;
    }

    @Override
    public int get(int i) {
        checkBound(i, size);
        return data[i];
    }

    @Override
    public void deleteAtIndex(int i) {
        checkBound(i, size);
        System.arraycopy(data, i + 1, data, i, size - i - 1);
        size--;
        correct();
    }

    @Override
    public void deleteAllOf(int x) {
        int shiftCount = 0;

        for (int i = 0; i < size; i++) {
            if (data[i] == x) {
                shiftCount++;
            } else if (shiftCount > 0) {
                data[i - shiftCount] = data[i];
            }
        }

        size -= shiftCount;
        correct();
    }

    @Override
    public int[] toArray() {
        return Arrays.copyOf(data, size);
    }

    @Override
    public List<Integer> toList() {
        return Arrays.stream(toArray()).boxed().toList();
    }

    @Override
    public Iterator<Integer> iterator() {
        return new Iterator<>() {

            int pos = 0;

            @Override
            public boolean hasNext() {
                return pos < size;
            }

            @Override
            public Integer next() {
                if (hasNext()) {
                    return data[pos++];
                } else throw new NoSuchElementException();
            }
        };
    }

    private void enlarge() {
        int[] enlargedData = new int[data.length * 2];
        System.arraycopy(data, 0, enlargedData, 0, size);
        data = enlargedData;
    }

    private void correct() {
        for (int i = size; i < data.length; i++) {
            data[i] = 0;
        }
    }

}

Helper Methods

private void enlarge() {
    int[] enlargedData = new int[data.length * 2];
    System.arraycopy(data, 0, enlargedData, 0, size);
    data = enlargedData;
}

Time complexity: \(O(n) \mid \Omega(n) \mid \Theta(n)\)

private void correct() {
    for (int i = size; i < data.length; i++) {
        data[i] = 0;
    }
}

Time complexity: \(O(n) \mid \Omega(1) \mid \Theta(k)\)
Where \(k\) = data.length - size

Insertion

public void append(int x) {
    if (size >= data.length) enlarge();
    data[size++] = x;
}

Time complexity: \(O(n) \mid \Omega(1) \mid \Theta(1)\)
\(O(n)\) because the method may call enlarge()

public void insertAtIndex(int x, int i) {
    checkBound(i, size + 1);
    if (i == size) append(x);
    else {
        if (size >= data.length) enlarge();
        else {
            System.arraycopy(data, i, data, i + 1, size - i);
            data[i] = x;
            size++;
        }
    }
}

Time complexity: \(O(n) \mid \Omega(1) \mid \Theta(n)\)

Modification and Access

public void setAtIndex(int x, int i) {
    checkBound(i, size);
    data[i] = x;
}

public int get(int i) {
    checkBound(i, size);
    return data[i];
}

Time complexity: \(O(1)\)

Deletion

public void deleteAtIndex(int i) {
    checkBound(i, size);
    System.arraycopy(data, i + 1, data, i, size - i - 1);
    size--;
    correct();
}

Time complexity: \(O(n) \mid \Omega(1) \mid \Theta(n)\)

public void deleteAllOf(int x) {
    int shiftCount = 0;

    for (int i = 0; i < size; i++) {
        if (data[i] == x) {
            shiftCount++;
        } else if (shiftCount > 0) {
            data[i - shiftCount] = data[i];
        }
    }

    size -= shiftCount;
    correct();
}

Time complexity: \(O(n) \mid \Omega(n) \mid \Theta(n)\)

MyLinkedList

A linear data structure where elements are not stored in contiguous memory locations. Instead, each element, called a node, contains data and a reference (link) to the next node in the sequence. This allows for dynamic memory allocation and efficient insertion and deletion of elements, especially at the beginning or middle of the list. Class MyLinkedList implements a singly linked list, utilizing class Node with a single pointer and one-way traversal.

import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.NoSuchElementException;

public class MyLinkedList extends MyAbstractList {

    private Node head;
    private int size;

    static class Node {
        int val;
        Node next;

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

    public MyLinkedList() {
        head = null;
        size = 0;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public void append(int x) {
        if (head == null) {
            head = new Node(x);
        } else {
            Node current = head;
            while (current.next != null) {
                current = current.next;
            }
            current.next = new Node(x);
        }
        size++;
    }

    @Override
    public void insertAtIndex(int x, int i) {
        checkBound(i, size + 1);
        if (i == 0) {
            Node newNode = new Node(x);
            newNode.next = head;
            head = newNode;
        } else {
            Node current = head;
            for (int j = 0; j < i - 1; j++) {
                current = current.next;
            }
            Node newNode = new Node(x);
            newNode.next = current.next;
            current.next = newNode;
        }
        size++;
    }

    public void insertAtHead(int x) {
        insertAtIndex(x, 0);
    }

    public void insertAtTail(int x) {
        insertAtIndex(x, size);
    }

    @Override
    public void setAtIndex(int x, int i) {
        checkBound(i, size);
        Node current = head;
        for (int j = 0; j < i; j++) {
            current = current.next;
        }
        current.val = x;
    }

    @Override
    public int get(int i) {
        checkBound(i, size);
        Node current = head;
        for (int j = 0; j < i; j++) {
            current = current.next;
        }
        return current.val;
    }

    @Override
    public void deleteAtIndex(int i) {
        checkBound(i, size);
        if (i == 0) {
            head = head.next;
        } else {
            Node current = head;
            for (int j = 0; j < i - 1; j++) {
                current = current.next;
            }
            current.next = current.next.next;
        }
        size--;
    }

    public void deleteAtHead() {
        deleteAtIndex(0);
    }

    public void deleteAtTail() {
        deleteAtIndex(size - 1);
    }

    @Override
    public void deleteAllOf(int x) {
        Node dummy = new Node(0);
        dummy.next = head;
        Node current = dummy;
        while (current.next != null) {
            if (current.next.val == x) {
                current.next = current.next.next;
                size--;
            } else {
                current = current.next;
            }
        }
        head = dummy.next;
    }

    @Override
    public int[] toArray() {
        int[] array = new int[size];
        Node current = head;
        for (int i = 0; i < size; i++) {
            array[i] = current.val;
            current = current.next;
        }
        return array;
    }

    @Override
    public List<Integer> toList() {
        List<Integer> list = new LinkedList<>();
        Node current = head;
        while (current != null) {
            list.add(current.val);
            current = current.next;
        }
        return list;
    }

    @Override
    public Iterator<Integer> iterator() {
        return new Iterator<>() {

            Node current = head;

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

            @Override
            public Integer next() {
                if (hasNext()) {
                    int val = current.val;
                    current = current.next;
                    return val;
                } else throw new NoSuchElementException();
            }
        };
    }
}

Insertion

public void append(int x) {
    if (head == null) {
        head = new Node(x);
    } else {
        Node current = head;
        while (current.next != null) {
            current = current.next;
        }
        current.next = new Node(x);
    }
    size++;
}

Time complexity: \(O(n) \mid \Omega(1) \mid \Theta(n)\)

public void insertAtIndex(int x, int i) {
    checkBound(i, size + 1);
    if (i == 0) {
        Node newNode = new Node(x);
        newNode.next = head;
        head = newNode;
    } else {
        Node current = head;
        for (int j = 0; j < i - 1; j++) {
            current = current.next;
        }
        Node newNode = new Node(x);
        newNode.next = current.next;
        current.next = newNode;
    }
    size++;
}

Time complexity: \(O(n) \mid \Omega(1) \mid \Theta(n)\)

public void insertAtHead(int x) {
    insertAtIndex(x, 0);
}

public void insertAtTail(int x) {
    insertAtIndex(x, size);
}

insertAtHead(int x) Time complexity: \(O(1) \mid \Omega(1) \mid \Theta(1)\)
insertAtTail(int x) Time complexity: \(O(n) \mid \Omega(1) \mid \Theta(n)\)

Modification and Access

public void setAtIndex(int x, int i) {
    checkBound(i, size);
    Node current = head;
    for (int j = 0; j < i; j++) {
        current = current.next;
    }
    current.val = x;
}

public int get(int i) {
    checkBound(i, size);
    Node current = head;
    for (int j = 0; j < i; j++) {
        current = current.next;
    }
    return current.val;
}

setAtIndex(int x, int i) Time complexity: \(O(n) \mid \Omega(1) \mid \Theta(n)\)
get(int i) Time complexity: \(O(n) \mid \Omega(1) \mid \Theta(n)\)

Deletion

public void deleteAtIndex(int i) {
    checkBound(i, size);
    if (i == 0) {
        head = head.next;
    } else {
        Node current = head;
        for (int j = 0; j < i - 1; j++) {
            current = current.next;
        }
        current.next = current.next.next;
    }
    size--;
}

Time complexity: \(O(n) \mid \Omega(1) \mid \Theta(n)\)

public void deleteAtHead() {
    deleteAtIndex(0);
}

public void deleteAtTail() {
    deleteAtIndex(size - 1);
}

deleteAtHead() Time complexity: \(O(1) \mid \Omega(1) \mid \Theta(1)\)
deleteAtTail() Time complexity: \(O(n) \mid \Omega(1) \mid \Theta(n)\)

public void deleteAllOf(int x) {
    Node dummy = new Node(0);
    dummy.next = head;
    Node current = dummy;
    while (current.next != null) {
        if (current.next.val == x) {
            current.next = current.next.next;
            size--;
        } else {
            current = current.next;
        }
    }
    head = dummy.next;
}

Time complexity: \(O(n) \mid \Omega(n) \mid \Theta(n)\)

MyDoublyLinkedList

Class MyDoublyLinkedList implements a doubly linked list, where each node contains data and references to both the next and previous nodes. This bidirectional linking enables efficient insertion, deletion, and traversal in both forward and backward directions, making it a versatile data structure for various applications.

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;

public class MyDoublyLinkedList extends MyAbstractList {

    private Node head;
    private Node tail;
    private int size;

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

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

    public MyDoublyLinkedList() {
        head = null;
        tail = null;
        size = 0;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public void append(int x) {
        Node newNode = new Node(x);
        if (head == null) {
            head = newNode;
            tail = head;
        } else {
            newNode.prev = tail;
            tail.next = newNode;
            tail = newNode;
        }
        size++;
    }

    @Override
    public void insertAtIndex(int x, int i) {
        checkBound(i, size + 1);

        if (i == 0) {
            insertAtHead(x);
            return;
        }

        if (i == size) {
            append(x);
            return;
        }

        Node newNode = new Node(x);
        Node current = dynamicTraversal(i);

        newNode.prev = current.prev;
        newNode.next = current;
        current.prev.next = newNode;
        current.prev = newNode;

        size++;
    }

    public void insertAtHead(int x) {
        Node newNode = new Node(x);
        if (head == null) {
            head = newNode;
            tail = head;
        } else {
            newNode.next = head;
            head.prev = newNode;
            head = newNode;
        }
        size++;
    }

    public void insertAtTail(int x) {
        append(x);
    }

    @Override
    public void setAtIndex(int x, int i) {
        checkBound(i, size);
        dynamicTraversal(i).val = x;
    }

    @Override
    public int get(int i) {
        checkBound(i, size);
        return dynamicTraversal(i).val;
    }

    @Override
    public void deleteAtIndex(int i) {
        checkBound(i, size);

        if (size == 1) {
            head = null;
            tail = null;
        } else if (i == 0) {
            deleteAtHead();
            return;
        } else if (i == size - 1) {
            deleteAtTail();
            return;
        } else {
            Node current = dynamicTraversal(i);
            current.prev.next = current.next;
            current.next.prev = current.prev;
        }

        size--;
    }

    public void deleteAtHead() {
        if (size == 0) return;

        if (size == 1) {
            head = null;
            tail = null;
        } else {
            head = head.next;
            head.prev = null;
        }

        size--;
    }

    public void deleteAtTail() {
        if (size == 0) return;

        if (size == 1) {
            head = null;
            tail = null;
        } else {
            tail = tail.prev;
            tail.next = null;
        }

        size--;
    }

    @Override
    public void deleteAllOf(int x) {
        Node current = head;
        while (current != null) {
            if (current.val == x) {
                if (current == head) {
                    deleteAtHead();
                    current = head;
                } else if (current == tail) {
                    deleteAtTail();
                    break;
                } else {
                    current.prev.next = current.next;
                    current.next.prev = current.prev;
                    current = current.next;
                    size--;
                }
            } else {
                current = current.next;
            }
        }
    }

    @Override
    public int[] toArray() {
        int[] arr = new int[size];
        Node current = head;
        for (int i = 0; current != null; i++) {
            arr[i] = current.val;
            current = current.next;
        }
        return arr;
    }

    @Override
    public List<Integer> toList() {
        List<Integer> list = new ArrayList<>();
        Node current = head;
        while (current != null) {
            list.add(current.val);
            current = current.next;
        }
        return list;
    }

    @Override
    public Iterator<Integer> iterator() {
        return new Iterator<>() {
            private Node current = head;

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

            @Override
            public Integer next() {
                if (!hasNext()) {
                    throw new NoSuchElementException();
                }
                int val = current.val;
                current = current.next;
                return val;
            }
        };
    }

    private Node dynamicTraversal(int i) {
        Node current;
        if (i < size / 2) {
            current = head;
            for (int j = 0; j < i; j++) {
                current = current.next;
            }
        } else {
            current = tail;
            for (int j = size - 1; j > i; j--) {
                current = current.prev;
            }
        }
        return current;
    }

}

Helper Method

private Node dynamicTraversal(int i) {
    Node current;
    if (i < size / 2) {
        current = head;
        for (int j = 0; j < i; j++) {
            current = current.next;
        }
    } else {
        current = tail;
        for (int j = size - 1; j > i; j--) {
            current = current.prev;
        }
    }
    return current;
}

Time complexity: \(O(n) \mid \Omega(1) \mid \Theta(n)\)

Insertion

public void append(int x) {
    Node newNode = new Node(x);
    if (head == null) {
        head = newNode;
        tail = head;
    } else {
        newNode.prev = tail;
        tail.next = newNode;
        tail = newNode;
    }
    size++;
}

Time complexity: \(O(1) \mid \Omega(1) \mid \Theta(1)\)

public void insertAtIndex(int x, int i) {
    checkBound(i, size + 1);

    if (i == 0) {
        insertAtHead(x);
        return;
    }

    if (i == size) {
        append(x);
        return;
    }

    Node newNode = new Node(x);
    Node current = dynamicTraversal(i);

    newNode.prev = current.prev;
    newNode.next = current;
    current.prev.next = newNode;
    current.prev = newNode;

    size++;
}

Time complexity: \(O(n) \mid \Omega(1) \mid \Theta(n)\)

public void insertAtHead(int x) {
    Node newNode = new Node(x);
    if (head == null) {
        head = newNode;
        tail = head;
    } else {
        newNode.next = head;
        head.prev = newNode;
        head = newNode;
    }
    size++;
}

Time complexity: \(O(1) \mid \Omega(1) \mid \Theta(1)\)

public void insertAtTail(int x) {
    append(x);
}

Time complexity: \(O(1) \mid \Omega(1) \mid \Theta(1)\)

Modification and Access

public void setAtIndex(int x, int i) {
    checkBound(i, size);
    dynamicTraversal(i).val = x;
}

public int get(int i) {
    checkBound(i, size);
    return dynamicTraversal(i).val;
}

setAtIndex(int x, int i) Time complexity: \(O(n) \mid \Omega(1) \mid \Theta(n)\)
get(int i) Time complexity: \(O(n) \mid \Omega(1) \mid \Theta(n)\)

Deletion

public void deleteAtIndex(int i) {
    checkBound(i, size);

    if (size == 1) {
        head = null;
        tail = null;
    } else if (i == 0) {
        deleteAtHead();
        return;
    } else if (i == size - 1) {
        deleteAtTail();
        return;
    } else {
        Node current = dynamicTraversal(i);
        current.prev.next = current.next;
        current.next.prev = current.prev;
    }

    size--;
}

Time complexity: \(O(n) \mid \Omega(1) \mid \Theta(n)\)

public void deleteAtHead() {
    if (size == 0) return;

    if (size == 1) {
            head = null;
            tail = null;
    } else {
        head = head.next;
        head.prev = null;
    }

    size--;
}

Time complexity: \(O(1) \mid \Omega(1) \mid \Theta(1)\)

public void deleteAtTail() {
    if (size == 0) return;

    if (size == 1) {
        head = null;
        tail = null;
    } else {
        tail = tail.prev;
        tail.next = null;
    }

    size--;
}

Time complexity: \(O(1) \mid \Omega(1) \mid \Theta(1)\)

public void deleteAllOf(int x) {
    Node current = head;
    while (current != null) {
        if (current.val == x) {
            if (current == head) {
                deleteAtHead();
                current = head;
            } else if (current == tail) {
                deleteAtTail();
                break;
            } else {
                current.prev.next = current.next;
                current.next.prev = current.prev;
                current = current.next;
                size--;
            }
        } else {
            current = current.next;
        }
    }
}

Time complexity: \(O(n) \mid \Omega(n) \mid \Theta(n)\)

MyStack

Hash-Based Data Structure

Tree Data Structure

Test Classes

MyArrayList

package test;

import data_structure.non_generic.MyArrayList;
import data_structure.non_generic.MyList;
import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.Test;

import java.util.Iterator;
import java.util.List;

import static org.junit.jupiter.api.Assertions.*;

public class TestMyArrayList {

    private MyList myList;

    @BeforeEach
    void setup() {
        myList = new MyArrayList();
    }

    @Test
    void testSize() {
        assertEquals(0, myList.size());
        myList.append(1);
        assertEquals(1, myList.size());
        myList.append(2);
        assertEquals(2, myList.size());
    }

    @Test
    void testAppend() {
        myList.append(1);
        myList.append(2);
        myList.append(3);
        assertEquals(1, myList.get(0));
        assertEquals(2, myList.get(1));
        assertEquals(3, myList.get(2));
    }

    @Test
    void testInsertAtIndex() {
        myList.append(1);
        myList.append(3);
        myList.insertAtIndex(2, 1);
        assertEquals(1, myList.get(0));
        assertEquals(2, myList.get(1));
        assertEquals(3, myList.get(2));
    }

    @Test
    void testSetAtIndex() {
        myList.append(1);
        myList.append(2);
        myList.setAtIndex(3, 1);
        assertEquals(1, myList.get(0));
        assertEquals(3, myList.get(1));
    }

    @Test
    void testGet() {
        myList.append(1);
        myList.append(2);
        myList.append(3);
        assertEquals(1, myList.get(0));
        assertEquals(2, myList.get(1));
        assertEquals(3, myList.get(2));
    }

    @Test
    void testDeleteAtIndex() {
        myList.append(1);
        myList.append(2);
        myList.append(3);
        myList.deleteAtIndex(1);
        assertEquals(1, myList.get(0));
        assertEquals(3, myList.get(1));
        assertEquals(2, myList.size());
    }

    @Test
    void testDeleteAllOf() {
        myList.append(1);
        myList.append(2);
        myList.append(1);
        myList.append(3);
        myList.deleteAllOf(1);
        assertEquals(2, myList.get(0));
        assertEquals(3, myList.get(1));
        assertEquals(2, myList.size());
    }

    @Test
    void testToArray() {
        myList.append(1);
        myList.append(2);
        myList.append(3);
        int[] arr = myList.toArray();
        assertArrayEquals(new int[]{1, 2, 3}, arr);
    }

    @Test
    void testToList() {
        myList.append(1);
        myList.append(2);
        myList.append(3);
        List<Integer> list = myList.toList();
        assertEquals(List.of(1, 2, 3), list);
    }

    @Test
    void testIterator() {
        myList.append(1);
        myList.append(2);
        myList.append(3);
        Iterator<Integer> iterator = myList.iterator();
        assertTrue(iterator.hasNext());
        assertEquals(1, iterator.next());
        assertTrue(iterator.hasNext());
        assertEquals(2, iterator.next());
        assertTrue(iterator.hasNext());
        assertEquals(3, iterator.next());
        assertFalse(iterator.hasNext());
    }

    @Test
    void testEdgeCases() {
        // Test inserting at the beginning
        myList.insertAtIndex(1, 0);
        assertEquals(1, myList.get(0));
        assertEquals(1, myList.size());

        // Test appending at the end
        myList.append(2);
        assertEquals(2, myList.get(1));
        assertEquals(2, myList.size());

        // Test setting at the beginning
        myList.setAtIndex(3, 0);
        assertEquals(3, myList.get(0));

        // Test setting at the end
        myList.setAtIndex(4, 1);
        assertEquals(4, myList.get(1));

        // Test deleting at the beginning
        myList.deleteAtIndex(0);
        assertEquals(4, myList.get(0));
        assertEquals(1, myList.size());

        // Test deleting at the end
        myList.deleteAtIndex(0);
        assertEquals(0, myList.size());

        // Test inserting out of bounds (should throw exception)
        assertThrows(IndexOutOfBoundsException.class, () -> myList.insertAtIndex(5, 5));

        // Test getting out of bounds
        assertThrows(IndexOutOfBoundsException.class, () -> myList.get(2));

        // Test setting out of bounds
        assertThrows(IndexOutOfBoundsException.class, () -> myList.setAtIndex(10, 1));
    }

    @Test
    void testEmptyListOperations() {
        // Ensure delete operation on empty list doesn't throw unexpected errors
        assertThrows(IndexOutOfBoundsException.class, () -> myList.deleteAtIndex(0));

        // Ensure get operation on empty list throws an exception
        assertThrows(IndexOutOfBoundsException.class, () -> myList.get(0));

        // Ensure set operation on empty list throws an exception
        assertThrows(IndexOutOfBoundsException.class, () -> myList.setAtIndex(1, 0));
    }

    @Test
    void testToString() {
        assertEquals("[]", myList.toString());
        myList.append(1);
        assertEquals("[1]", myList.toString());
        myList.append(2);
        assertEquals("[1, 2]", myList.toString());
        myList.append(3);
        assertEquals("[1, 2, 3]", myList.toString());
    }

    @Test
    void testLargeNumberOfElements() {
        // Append a large number of elements to test list expansion
        for (int i = 0; i < 1000; i++) {
            myList.append(i);
        }
        assertEquals(1000, myList.size());
        assertEquals(999, myList.get(999));

        // Delete some elements and check if the list is updated correctly
        myList.deleteAtIndex(500);
        assertEquals(999, myList.size());
        assertEquals(501, myList.get(500));
    }

    @Test
    void testEdgeCasesEnhanced() {
        // Test appending minimum and maximum integer values
        myList.append(Integer.MIN_VALUE);
        myList.append(Integer.MAX_VALUE);
        assertEquals(Integer.MIN_VALUE, myList.get(0));
        assertEquals(Integer.MAX_VALUE, myList.get(1));

        // Test inserting in the middle of a list with minimum and maximum values
        myList.insertAtIndex(0, 1);
        assertEquals(Integer.MIN_VALUE, myList.get(0));
        assertEquals(0, myList.get(1));
        assertEquals(Integer.MAX_VALUE, myList.get(2));

        // Test deleting non-existent element
        myList.deleteAllOf(999); // Element 999 is not in the list
        assertEquals(3, myList.size());

        // Test appending and deleting duplicate values
        myList.append(5);
        myList.append(5);
        myList.deleteAllOf(5);
        assertEquals(3, myList.size()); // Only the original three elements should remain

        // Test consecutive deletions
        myList.deleteAtIndex(0);
        myList.deleteAtIndex(0);
        myList.deleteAtIndex(0);
        assertTrue(myList.isEmpty());

        // Test appending and getting a very large number of duplicates
        for (int i = 0; i < 100; i++) {
            myList.append(42);
        }
        assertEquals(100, myList.size());
        assertEquals(42, myList.get(99));
        myList.deleteAllOf(42);
        assertTrue(myList.isEmpty());
    }

}

MyLinkedList

Note: All linked list implementation in this thread uses this test class.

package test;

import data_structure.non_generic.MyLinkedList;
import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.Test;

import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;

import static org.junit.jupiter.api.Assertions.*;

public class TestMyLinkedList {

    private MyLinkedList myList;

    @BeforeEach
    void setup() {
        myList = new MyLinkedList();
    }

    @Test
    void testSize() {
        assertEquals(0, myList.size());
        myList.append(1);
        assertEquals(1, myList.size());
        myList.append(2);
        assertEquals(2, myList.size());
    }

    @Test
    void testAppend() {
        myList.append(1);
        myList.append(2);
        myList.append(3);
        assertEquals(1, myList.get(0));
        assertEquals(2, myList.get(1));
        assertEquals(3, myList.get(2));
    }

    @Test
    void testInsertAtIndex() {
        myList.append(1);
        myList.append(3);
        myList.insertAtIndex(2, 1);
        assertEquals(1, myList.get(0));
        assertEquals(2, myList.get(1));
        assertEquals(3, myList.get(2));
    }

    @Test
    void testInsertAtHead() {
        myList.insertAtHead(1);
        myList.insertAtHead(2);
        assertEquals(2, myList.get(0));
        assertEquals(1, myList.get(1));
        assertEquals(2, myList.size());
    }

    @Test
    void testInsertAtTail() {
        myList.insertAtTail(1);
        myList.insertAtTail(2);
        assertEquals(1, myList.get(0));
        assertEquals(2, myList.get(1));
        assertEquals(2, myList.size());
    }

    @Test
    void testSetAtIndex() {
        myList.append(1);
        myList.append(2);
        myList.setAtIndex(3, 1);
        assertEquals(1, myList.get(0));
        assertEquals(3, myList.get(1));
    }

    @Test
    void testGet() {
        myList.append(1);
        myList.append(2);
        myList.append(3);
        assertEquals(1, myList.get(0));
        assertEquals(2, myList.get(1));
        assertEquals(3, myList.get(2));
    }

    @Test
    void testDeleteAtIndex() {
        myList.append(1);
        myList.append(2);
        myList.append(3);
        myList.deleteAtIndex(1);
        assertEquals(1, myList.get(0));
        assertEquals(3, myList.get(1));
        assertEquals(2, myList.size());
    }

    @Test
    void testDeleteAtHead() {
        myList.append(1);
        myList.append(2);
        myList.deleteAtHead();
        assertEquals(2, myList.get(0));
        assertEquals(1, myList.size());
    }

    @Test
    void testDeleteAtTail() {
        myList.append(1);
        myList.append(2);
        myList.append(3);
        myList.deleteAtTail();
        assertEquals(2, myList.get(1));
        assertEquals(2, myList.size());
    }

    @Test
    void testDeleteAllOf() {
        myList.append(1);
        myList.append(2);
        myList.append(1);
        myList.append(3);
        myList.deleteAllOf(1);
        assertEquals(2, myList.get(0));
        assertEquals(3, myList.get(1));
        assertEquals(2, myList.size());
        myList.deleteAllOf(1);
        myList.deleteAllOf(0);
        assertEquals(2, myList.size());
    }

    @Test
    void testToArray() {
        myList.append(1);
        myList.append(2);
        myList.append(3);
        int[] arr = myList.toArray();
        assertArrayEquals(new int[]{1, 2, 3}, arr);
    }

    @Test
    void testToList() {
        myList.append(1);
        myList.append(2);
        myList.append(3);
        List<Integer> list = myList.toList();
        assertEquals(List.of(1, 2, 3), list);
    }

    @Test
    void testIterator() {
        myList.append(1);
        myList.append(2);
        myList.append(3);
        Iterator<Integer> iterator = myList.iterator();
        assertTrue(iterator.hasNext());
        assertEquals(1, iterator.next());
        assertTrue(iterator.hasNext());
        assertEquals(2, iterator.next());
        assertTrue(iterator.hasNext());
        assertEquals(3, iterator.next());
        assertFalse(iterator.hasNext());
    }

    @Test
    void testIteratorEdgeCases() {
        Iterator<Integer> iterator = myList.iterator();
        assertFalse(iterator.hasNext());
        assertThrows(NoSuchElementException.class, iterator::next);

        myList.append(1);
        myList.append(2);
        iterator = myList.iterator();
        assertTrue(iterator.hasNext());
        assertEquals(1, iterator.next());
        assertEquals(2, iterator.next());
        assertFalse(iterator.hasNext());
    }

    @Test
    void testToString() {
        assertEquals("[]", myList.toString());
        myList.append(1);
        assertEquals("[1]", myList.toString());
        myList.append(2);
        assertEquals("[1, 2]", myList.toString());
        myList.append(3);
        assertEquals("[1, 2, 3]", myList.toString());
    }

    @Test
    void testBoundaryConditions() {
        // Test inserting and deleting on empty list
        assertThrows(IndexOutOfBoundsException.class, () -> myList.deleteAtIndex(0));
        assertThrows(IndexOutOfBoundsException.class, () -> myList.get(0));

        // Add to head, delete head, check size adjustments
        myList.insertAtHead(10);
        assertEquals(1, myList.size());
        myList.deleteAtHead();
        assertEquals(0, myList.size());
    }

    @Test
    void testInsertAtInvalidIndex() {
        assertThrows(IndexOutOfBoundsException.class, () -> myList.insertAtIndex(1, -1)); // Negative index
        assertThrows(IndexOutOfBoundsException.class, () -> myList.insertAtIndex(1, 1));  // Index > size
    }

    @Test
    void testDeleteAtInvalidIndex() {
        assertThrows(IndexOutOfBoundsException.class, () -> myList.deleteAtIndex(-1)); // Negative index
        assertThrows(IndexOutOfBoundsException.class, () -> myList.deleteAtIndex(0));  // Empty list
        myList.append(1);
        assertThrows(IndexOutOfBoundsException.class, () -> myList.deleteAtIndex(1)); // Index > size
    }

    @Test
    void testSetAtInvalidIndex() {
        assertThrows(IndexOutOfBoundsException.class, () -> myList.setAtIndex(1, -1)); // Negative index
        assertThrows(IndexOutOfBoundsException.class, () -> myList.setAtIndex(1, 0));  // Index > size
    }

    @Test
    void testDeleteAllOfNonExistentValue() {
        myList.append(1);
        myList.append(2);
        myList.deleteAllOf(3); // Value not present
        assertEquals(2, myList.size()); // Size should remain unchanged
    }

    @Test
    void testInsertMultipleElements() {
        myList.append(1);
        myList.append(2);
        myList.append(3);
        myList.insertAtIndex(4, 1);
        assertEquals(4, myList.get(1));
        assertEquals(3, myList.get(3));
    }

    @Test
    void testDeleteAllElements() {
        myList.append(1);
        myList.append(2);
        myList.append(3);
        myList.deleteAllOf(1);
        myList.deleteAllOf(2);
        myList.deleteAllOf(3);
        assertEquals(0, myList.size());
        assertTrue(myList.isEmpty());
    }

    @Test
    void testConsecutiveOperations() {
        myList.append(1);
        myList.append(2);
        myList.insertAtIndex(3, 1); // List should be [1, 3, 2]
        assertEquals(3, myList.get(1));
        myList.deleteAtIndex(0); // List should be [3, 2]
        assertEquals(3, myList.get(0));
    }

    @Test
    void testLargeList() {
        for (int i = 0; i < 10000; i++) {
            myList.append(i);
        }
        assertEquals(10000, myList.size());
        assertEquals(9999, myList.get(9999));
    }

    @Test
    void testIteratorAfterModification() {
        myList.append(1);
        myList.append(2);
        Iterator<Integer> iterator = myList.iterator();
        assertTrue(iterator.hasNext());
        assertEquals(1, iterator.next());
        myList.append(3); // Modify list
        assertTrue(iterator.hasNext());
        assertEquals(2, iterator.next());
        assertTrue(iterator.hasNext());
        assertEquals(3, iterator.next());
        assertFalse(iterator.hasNext());
    }

}