LinkedList.java

/**
 * Doubly Linked List for Song objects.
 * Supports insertion/removal at any position, circular toggling, and node-level access.
 */
public class LinkedList {

    /** A node in the doubly linked list */
    public static class Node {
        private final Song data;
        private Node next;
        private Node prev;

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

        public Song getData() { return data; }
        public Node getNext() { return next; }
        public Node getPrev() { return prev; }
    }

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

    // ======= Basic Accessors =======

    public Node getHead() { return head; }
    public Node getTail() { return tail; }
    public int size() { return size; }
    public boolean isEmpty() { return size == 0; }

    // ======= Core Operations =======

    /**
     * Adds a song to the end of the list.
     * @param song Song to add
     * @return Node created for the song
     */
    public Node add(Song song) {
        Node newNode = new Node(song);
        if (isEmpty()) {
            head = tail = newNode;
        } else {
            tail.next = newNode;
            newNode.prev = tail;
            tail = newNode;
        }
        size++;
        return newNode;
    }

    /**
     * Inserts a song at a given index (inserts before that index).
     * @param index Position to insert at
     * @param song Song to insert
     * @return Node created
     */
    public Node addAt(int index, Song song) {
        if (index <= 0 || isEmpty()) {
            Node newNode = new Node(song);
            newNode.next = head;
            if (head != null) head.prev = newNode;
            head = newNode;
            if (tail == null) tail = newNode;
            size++;
            return newNode;
        }

        Node current = getNode(Math.min(index - 1, size - 1));
        Node newNode = new Node(song);
        newNode.next = current.next;
        if (current.next != null) current.next.prev = newNode;
        current.next = newNode;
        newNode.prev = current;
        if (newNode.next == null) tail = newNode;
        size++;
        return newNode;
    }

    /**
     * Removes and returns the song at the specified index.
     * @param index Position to remove from
     * @return Removed Song, or null if list is empty
     */
    public Song remove(int index) {
        if (isEmpty()) return null;
        if (index < 0 || index >= size)
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);

        Node toRemove = getNode(index);

        if (toRemove == head) {
            head = head.next;
            if (head != null) head.prev = null;
            if (toRemove == tail) tail = null;
        } else {
            Node before = toRemove.prev;
            Node after = toRemove.next;
            if (before != null) before.next = after;
            if (after != null) after.prev = before;
            if (toRemove == tail) tail = before;
        }

        size--;
        return toRemove.data;
    }

    /**
     * Retrieves the song at a given index.
     * @param index Index to retrieve
     * @return Song at the index
     */
    public Song get(int index) {
        if (isEmpty()) return null;
        if (index < 0 || index >= size)
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        return getNode(index).data;
    }

    /**
     * Returns the Node object at the specified index.
     * @param index Index of node
     */
    public Node getNodeAt(int index) {
        return getNode(index);
    }

    /**
     * Finds the index of the given song.
     * @param song Song to find
     * @return Index or -1 if not found
     */
    public int indexOf(Song song) {
        Node current = head;
        int index = 0;
        while (current != null) {
            if (current.data.equals(song)) return index;
            current = current.next;
            index++;
        }
        return -1;
    }

    /**
     * Checks if the list contains the specified song.
     * @param song Song to check
     */
    public boolean contains(Song song) {
        return indexOf(song) != -1;
    }

    /**
     * Finds the node containing the given song.
     * @param song Song to search for
     * @return Node or null if not found
     */
    public Node findNode(Song song) {
        Node current = head;
        while (current != null) {
            if (current.data.equals(song)) return current;
            current = current.next;
        }
        return null;
    }

    public Node findNodeByData(Song song) {
        return findNode(song);
    }

    // ======= Circular List Support =======

    /**
     * Converts the list to circular.
     * Tail links to head and vice versa.
     */
    public void makeCircular() {
        if (!isEmpty() && head != tail) {
            tail.next = head;
            head.prev = tail;
        }
    }

    /**
     * Breaks circular linkage, making list linear.
     */
    public void makeLinear() {
        if (!isEmpty()) {
            if (tail != null) tail.next = null;
            if (head != null) head.prev = null;
        }
    }

    /**
     * Checks whether the list is circular.
     * @return true if circular, false otherwise
     */
    public boolean isCircular() {
        return !isEmpty() &&
               head != null && tail != null &&
               tail.next == head && head.prev == tail;
    }

    /**
     * Toggles circular/linear mode.
     * @param circular true to make circular, false to make linear
     */
    public void makeCircular(boolean circular) {
        if (circular) makeCircular();
        else makeLinear();
    }

    // ======= Utility =======

    /**
     * Clears the list completely.
     */
    public void clear() {
        head = tail = null;
        size = 0;
    }

    /**
     * Internal optimized node traversal.
     * @param index Index of node
     * @return Node at the index
     */
    private Node getNode(int index) {
        if (index < 0 || index >= size)
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);

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