LinkedList.java

interface LinkedList {
    void add(int data);

    void remove(int index);

    int get(int index);

    int length();

    boolean isEmpty();

    void print();

    void reverse();

    int mid();

    void insertMid(int data);

    void debug();
}

class Node {
    int data;
    Node next;

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

}

class DoublyNode {
    int data;
    DoublyNode next;
    DoublyNode prev;

    public DoublyNode(int data) {
        this.data = data;
        this.next = null;
        this.prev = null;
    }
}

class SinglyLinkedList implements LinkedList {

    private int length = 0;
    private Node head = null;
    private Node tail = null;

    @Override
    public void add(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            tail = head;
        } else {
            tail.next = newNode;
            tail = newNode;
        }
        length++;
    }

    @Override
    public void remove(int index) {
        if (index < 0 || index >= length) {
            throw new IndexOutOfBoundsException("Invalid index: " + index);
        }

        if (index == 0) {
            head = head.next;
        } else {
            Node current = head;
            Node prev = null;

            for (int i = 0; i < index; i++) {
                prev = current;
                current = current.next;
            }

            prev.next = current.next;
        }
        length--;
    }

    @Override
    public int get(int index) {
        if (isEmpty()) {
            throw new IllegalStateException("Linked List is empty.");
        }
        Node current = head;
        for (int i = 0; i < index; i++) {
            current = current.next;
        }
        return current.data;
    }

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

    @Override
    public boolean isEmpty() {
        return head == null || length == 0;
    }

    @Override
    public void print() {
        if (isEmpty()) {
            throw new IllegalStateException("Linked List is empty.");
        }
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }

    @Override
    public void reverse() {
        if (isEmpty()) {
            throw new IllegalStateException("Linked List is empty.");
        }
        Node current = head;
        Node prev = null;
        while (current != null) {
            Node next = current.next;
            current.next = prev;
            prev = current;
            current = next;
        }
        head = prev;
    }

    @Override
    public int mid() {
        if (isEmpty()) {
            throw new IllegalStateException("Linked List is empty.");
        }
        int mid = (length - 1) / 2;
        Node current = head;
        for (int i = 0; i < mid; i++) {
            current = current.next;
        }
        return current.data;
    }

    @Override
    public void insertMid(int data) {
        if (isEmpty()) {
            throw new IllegalStateException("Linked List is empty.");
        }
        int mid = (length - 1) / 2;
        Node newNode = new Node(data);
        Node current = head;
        for (int i = 0; i < mid; i++) {
            current = current.next;
        }
        newNode.next = current.next;
        current.next = newNode;
        length++;
    }

    @Override
    public void debug() {
        System.out.println("============ BEGIN DEBUG ============");
        Node current = head;
        while (current != null) {
            Integer next = null;
            if (current.next != null) {
                next = current.next.data;
            }
            System.out.println(current.data + "(next=" + next + ")");
            current = current.next;
        }
        System.out.println("============ END DEBUG ============");
    }

}

class DoublyLinkedList implements LinkedList {

    private DoublyNode head = null;
    private DoublyNode tail = null;
    private int length = 0;

    @Override
    public void add(int data) {
        DoublyNode newNode = new DoublyNode(data);
        if (head == null) {
            head = newNode;
            tail = head;
        } else {
            newNode.prev = tail;
            tail.next = newNode;
            tail = newNode;
        }
        length++;
    }

    @Override
    public void remove(int index) {
        if (index < 0 || index >= length) {
            throw new IndexOutOfBoundsException("Invalid index: " + index);
        }

        if (index == 0) {
            head = head.next;
            head.prev = null;
        } else {
            DoublyNode current = head;
            for (int i = 0; i < index; i++) {
                current = current.next;
            }
            DoublyNode next = current.next;
            current.prev.next = current.next;
            next.prev = current.prev;
        }
        length--;
    }

    @Override
    public int get(int index) {
        if (index < 0 || index >= length) {
            throw new IndexOutOfBoundsException("Invalid index: " + index);
        }
        DoublyNode current = head;
        for (int i = 0; i < index; i++) {
            current = current.next;
        }
        return current.data;
    }

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

    @Override
    public boolean isEmpty() {
        return head == null || length == 0;
    }

    @Override
    public void print() {
        if (isEmpty()) {
            throw new IllegalStateException("Linked List is empty.");
        }
        DoublyNode current = head;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }

    @Override
    public void reverse() {
        if (isEmpty()) {
            throw new IllegalStateException("Linked List is empty.");
        }
        DoublyNode current = head;
        DoublyNode prev = null;
        while (current != null) {
            DoublyNode next = current.next;
            current.next = prev;
            current.prev = next;
            prev = current;
            current = next;
        }
        head = prev;
    }

    @Override
    public int mid() {
        if (isEmpty()) {
            throw new IllegalStateException("Linked List is empty.");
        }
        int mid = (length - 1) / 2;
        DoublyNode current = head;
        for (int i = 0; i < mid; i++) {
            current = current.next;
        }
        return current.data;
    }

    @Override
    public void insertMid(int data) {
        if (isEmpty()) {
            throw new IllegalStateException("Linked List is empty.");
        }
        int mid = (length - 1) / 2;
        DoublyNode current = head;
        DoublyNode newNode = new DoublyNode(data);
        for (int i = 0; i < mid; i++) {
            current = current.next;
        }
        newNode.next = current.next;
        if (current.next != null) {
            current.next.prev = newNode;
        }
        newNode.prev = current;
        current.next = newNode;
        length++;
    }

    @Override
    public void debug() {
        System.out.println("============ BEGIN DEBUG ============");
        DoublyNode current = head;
        while (current != null) {
            Integer prev = null;
            Integer next = null;
            if (current.prev != null) {
                prev = current.prev.data;
            }
            if (current.next != null) {
                next = current.next.data;
            }
            System.out.println(current.data + "(next=" + next + ", prev=" + prev + ")");
            current = current.next;
        }
        System.out.println("============ END DEBUG ============");
    }
}

class CircularLinkedList implements LinkedList {

    private DoublyNode head = null;
    private DoublyNode tail = null;
    private int length = 0;

    @Override
    public void add(int data) {
        DoublyNode newNode = new DoublyNode(data);
        if (head == null) {
            head = newNode;
            tail = head;
        } else {
            tail.next = newNode;
            newNode.next = head;
            newNode.prev = tail;
            tail = newNode;
        }
        length++;
    }

    @Override
    public void remove(int index) {
        if (index < 0 || index >= length) {
            throw new IndexOutOfBoundsException("Invalid index: " + index);
        }

        if (index == 0) {
            head = head.next;
            tail = head;
        } else {
            DoublyNode current = head;
            for (int i = 0; i < index; i++) {
                current = current.next;
            }
            current.next.prev = current.prev;
            current.prev.next = current.next;
        }
        length--;
    }

    @Override
    public int get(int index) {
        if (index < 0 || index >= length) {
            throw new IndexOutOfBoundsException("Invalid index: " + index);
        }
        DoublyNode current = head;
        for (int i = 0; i < index; i++) {
            current = current.next;
        }
        return current.data;
    }

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

    @Override
    public boolean isEmpty() {
        return head == null || length == 0;
    }

    @Override
    public void print() {
        if (isEmpty()) {
            throw new IllegalStateException("Linked List is empty.");
        }
        DoublyNode current = head;
        do {
            System.out.print(current.data + " ");
            current = current.next;
        } while (current != head);
        System.out.println();
    }

    @Override
    public void reverse() {
        if (isEmpty()) {
            throw new IllegalStateException("Linked List is empty.");
        }
        DoublyNode current = head;
        DoublyNode prev = null;
        do {
            DoublyNode next = current.next;
            current.next = prev;
            current.prev = next;
            prev = current;
            current = next;
        } while (current != head);
        head.next = prev;
        head = prev;
    }

    @Override
    public int mid() {
        if (isEmpty()) {
            throw new IllegalStateException("Linked List is empty.");
        }
        int mid = (length - 1) / 2;
        DoublyNode current = head;
        for (int i = 0; i < mid; i++) {
            current = current.next;
        }
        return current.data;
    }

    @Override
    public void insertMid(int data) {
        if (isEmpty()) {
            throw new IllegalStateException("Linked List is empty.");
        }
        int mid = (length - 1) / 2;
        DoublyNode newNode = new DoublyNode(data);
        DoublyNode current = head;
        for (int i = 0; i < mid; i++) {
            current = current.next;
        }
        newNode.prev = current;
        current.next.prev = newNode;
        newNode.next = current.next;
        current.next = newNode;
        length++;
    }

    @Override
    public void debug() {
        System.out.println("============ BEGIN DEBUG ============");
        DoublyNode current = head;
        do {
            Integer prev = null;
            Integer next = null;
            if (current.prev != null) {
                prev = current.prev.data;
            }
            if (current.next != null) {
                next = current.next.data;
            }
            System.out.println(current.data + "(next=" + next + ", prev=" + prev + ")");
            current = current.next;
        } while (current != head);
        System.out.println("============ END DEBUG ============");
    }
}

class LinkedListExample {

    public static void main(String[] args) {
        testLinkedList(new SinglyLinkedList());
        testLinkedList(new DoublyLinkedList());
        testLinkedList(new CircularLinkedList());
    }

    private static void testLinkedList(LinkedList linkedList) {
        linkedList.add(1);
        linkedList.add(2);
        linkedList.add(3);

        System.out.print("Linked List: ");
        linkedList.print();

        System.out.println("Length: " + linkedList.length());
        System.out.println("Element at index 1: " + linkedList.get(1));

        linkedList.remove(1);
        System.out.print("Linked List after removal at index 1: ");
        linkedList.print();

        linkedList.reverse();
        System.out.print("Reversed Linked List: ");
        linkedList.print();

        System.out.println("Middle element: " + linkedList.mid());
        linkedList.insertMid(4);
        System.out.print("Linked List after inserting 4 in the middle: ");
        linkedList.print();
        linkedList.insertMid(5);
        System.out.print("Linked List after inserting 5 in the middle: ");
        linkedList.print();

        linkedList.reverse();
        System.out.print("Reversed Linked List: ");
        linkedList.print();

        linkedList.debug();
    }
}