DoublyLinkedList

DoublyLinkedList.java

package lab4.container;

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

/**
 * Узагальнений клас, що представляє двобічно зв'язаний список
 * @param <E> тип елементів списку
 */
public class DoublyLinkedList<E> implements Iterable<E> {

    /**
     * Внутрішній клас, що представляє вузол списку
     */
    private static class Node<E> {
        E data;            // Дані вузла
        Node<E> prev;      // Посилання на попередній вузол
        Node<E> next;      // Посилання на наступний вузол

        /**
         * Конструктор вузла
         * @param data дані вузла
         * @param prev попередній вузол
         * @param next наступний вузол
         */
        Node(E data, Node<E> prev, Node<E> next) {
            this.data = data;
            this.prev = prev;
            this.next = next;
        }
    }

    private Node<E> head;  // Перший вузол списку
    private Node<E> tail;  // Останній вузол списку
    private int size;      // Розмір списку

    /**
     * Конструктор порожнього списку
     */
    public DoublyLinkedList() {
        head = null;
        tail = null;
        size = 0;
    }

    /**
     * Конструктор списку з масивом елементів
     * @param elements масив елементів для додавання до списку
     */
    @SafeVarargs
    public DoublyLinkedList(E... elements) {
        this();
        for (E element : elements) {
            add(element);
        }
    }

    /**
     * Додає елемент в кінець списку
     * @param element елемент для додавання
     * @return true (як визначено специфікацією Collection)
     */
    public boolean add(E element) {
        addLast(element);
        return true;
    }

    /**
     * Додає елемент на початок списку
     * @param element елемент для додавання
     */
    public void addFirst(E element) {
        Node<E> newNode = new Node<>(element, null, head);
        if (head == null) {
            // Якщо список порожній, новий вузол стає і головою, і хвостом
            head = newNode;
            tail = newNode;
        } else {
            // Інакше новий вузол стає головою, а старий попереднім до нього
            head.prev = newNode;
            head = newNode;
        }
        size++;
    }

    /**
     * Додає елемент в кінець списку
     * @param element елемент для додавання
     */
    public void addLast(E element) {
        Node<E> newNode = new Node<>(element, tail, null);
        if (tail == null) {
            // Якщо список порожній, новий вузол стає і головою, і хвостом
            head = newNode;
            tail = newNode;
        } else {
            // Інакше новий вузол стає хвостом, а старий попереднім від нього
            tail.next = newNode;
            tail = newNode;
        }
        size++;
    }

    /**
     * Додає елемент за вказаним індексом
     * @param index індекс, за яким буде вставлено елемент
     * @param element елемент для додавання
     * @throws IndexOutOfBoundsException якщо індекс виходить за межі списку
     */
    public void add(int index, E element) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("Індекс: " + index + ", Розмір: " + size);
        }

        if (index == 0) {
            addFirst(element);
        } else if (index == size) {
            addLast(element);
        } else {
            // Знаходимо вузол, перед яким потрібно вставити новий
            Node<E> current = getNodeAt(index);

            // Створюємо новий вузол з посиланнями на попередній і поточний
            Node<E> newNode = new Node<>(element, current.prev, current);

            // Оновлюємо посилання у сусідніх вузлах
            current.prev.next = newNode;
            current.prev = newNode;

            size++;
        }
    }

    /**
     * Видаляє перший елемент списку
     * @return видалений елемент
     * @throws NoSuchElementException якщо список порожній
     */
    public E removeFirst() {
        if (isEmpty()) {
            throw new NoSuchElementException("Список порожній");
        }

        E element = head.data;

        if (head == tail) {
            // Якщо це був єдиний елемент
            head = null;
            tail = null;
        } else {
            // Інакше видаляємо голову і оновлюємо посилання
            head = head.next;
            head.prev = null;
        }

        size--;
        return element;
    }

    /**
     * Видаляє останній елемент списку
     * @return видалений елемент
     * @throws NoSuchElementException якщо список порожній
     */
    public E removeLast() {
        if (isEmpty()) {
            throw new NoSuchElementException("Список порожній");
        }

        E element = tail.data;

        if (head == tail) {
            // Якщо це був єдиний елемент
            head = null;
            tail = null;
        } else {
            // Інакше видаляємо хвіст і оновлюємо посилання
            tail = tail.prev;
            tail.next = null;
        }

        size--;
        return element;
    }

    /**
     * Видаляє елемент за вказаним індексом
     * @param index індекс елемента для видалення
     * @return видалений елемент
     * @throws IndexOutOfBoundsException якщо індекс виходить за межі списку
     */
    public E remove(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Індекс: " + index + ", Розмір: " + size);
        }

        if (index == 0) {
            return removeFirst();
        } else if (index == size - 1) {
            return removeLast();
        } else {
            // Знаходимо вузол, який потрібно видалити
            Node<E> current = getNodeAt(index);
            E element = current.data;

            // Оновлюємо посилання, щоб "обійти" поточний вузол
            current.prev.next = current.next;
            current.next.prev = current.prev;

            // Видаляємо посилання на сусідні вузли для збирання сміття
            current.prev = null;
            current.next = null;
            current.data = null;

            size--;
            return element;
        }
    }

    /**
     * Видаляє перше входження вказаного елемента зі списку
     * @param element елемент для видалення
     * @return true, якщо елемент був у списку
     */
    public boolean remove(E element) {
        if (isEmpty()) {
            return false;
        }

        // Перевіряємо, чи елемент - голова списку
        if (head.data == null ? element == null : head.data.equals(element)) {
            removeFirst();
            return true;
        }

        // Перевіряємо, чи елемент - хвіст списку
        if (tail.data == null ? element == null : tail.data.equals(element)) {
            removeLast();
            return true;
        }

        // Шукаємо елемент у списку
        Node<E> current = head.next;
        while (current != tail) {
            if (current.data == null ? element == null : current.data.equals(element)) {
                // Знайшли елемент, видаляємо його
                current.prev.next = current.next;
                current.next.prev = current.prev;

                // Видаляємо посилання для збирання сміття
                current.prev = null;
                current.next = null;
                current.data = null;

                size--;
                return true;
            }
            current = current.next;
        }

        // Елемент не знайдено
        return false;
    }

    /**
     * Отримує елемент за вказаним індексом
     * @param index індекс елемента
     * @return елемент за індексом
     * @throws IndexOutOfBoundsException якщо індекс виходить за межі списку
     */
    public E get(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Індекс: " + index + ", Розмір: " + size);
        }

        return getNodeAt(index).data;
    }

    /**
     * Отримує перший елемент списку
     * @return перший елемент
     * @throws NoSuchElementException якщо список порожній
     */
    public E getFirst() {
        if (isEmpty()) {
            throw new NoSuchElementException("Список порожній");
        }
        return head.data;
    }

    /**
     * Отримує останній елемент списку
     * @return останній елемент
     * @throws NoSuchElementException якщо список порожній
     */
    public E getLast() {
        if (isEmpty()) {
            throw new NoSuchElementException("Список порожній");
        }
        return tail.data;
    }

    /**
     * Змінює елемент за вказаним індексом
     * @param index індекс елемента
     * @param element новий елемент
     * @return старий елемент
     * @throws IndexOutOfBoundsException якщо індекс виходить за межі списку
     */
    public E set(int index, E element) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Індекс: " + index + ", Розмір: " + size);
        }

        Node<E> node = getNodeAt(index);
        E oldValue = node.data;
        node.data = element;
        return oldValue;
    }

    /**
     * Перевіряє, чи містить список вказаний елемент
     * @param element елемент для перевірки
     * @return true, якщо елемент присутній у списку
     */
    public boolean contains(E element) {
        // Обхід списку і пошук елемента
        for (Node<E> current = head; current != null; current = current.next) {
            if (current.data == null ? element == null : current.data.equals(element)) {
                return true;
            }
        }
        return false;
    }

    /**
     * Знаходить індекс першого входження елемента
     * @param element елемент для пошуку
     * @return індекс першого входження або -1, якщо елемент не знайдено
     */
    public int indexOf(E element) {
        int index = 0;
        for (Node<E> current = head; current != null; current = current.next, index++) {
            if (current.data == null ? element == null : current.data.equals(element)) {
                return index;
            }
        }
        return -1;
    }

    /**
     * Очищає список
     */
    public void clear() {
        // Очищення посилань для допомоги збирачу сміття
        for (Node<E> current = head; current != null; ) {
            Node<E> next = current.next;
            current.data = null;
            current.prev = null;
            current.next = null;
            current = next;
        }

        head = null;
        tail = null;
        size = 0;
    }

    /**
     * Повертає розмір списку
     * @return кількість елементів у списку
     */
    public int size() {
        return size;
    }

    /**
     * Перевіряє, чи список порожній
     * @return true, якщо список не містить елементів
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * Повертає рядкове представлення списку
     * @return рядок зі всіма елементами списку
     */
    @Override
    public String toString() {
        if (isEmpty()) {
            return "[]";
        }

        StringBuilder sb = new StringBuilder("[");
        Node<E> current = head;

        // Проходимо всі елементи, крім останнього
        while (current.next != null) {
            sb.append(current.data).append(", ");
            current = current.next;
        }

        // Додаємо останній елемент
        sb.append(current.data).append("]");

        return sb.toString();
    }

    /**
     * Повертає ітератор для обходу списку у прямому напрямку
     * @return ітератор
     */
    @Override
    public Iterator<E> iterator() {
        return new Iterator<E>() {
            private Node<E> current = head;
            private Node<E> lastReturned = null;

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

            @Override
            public E next() {
                if (!hasNext()) {
                    throw new NoSuchElementException();
                }

                lastReturned = current;
                current = current.next;
                return lastReturned.data;
            }

            @Override
            public void remove() {
                if (lastReturned == null) {
                    throw new IllegalStateException("next() не був викликаний, або елемент вже був видалений");
                }

                // Видаляємо останній повернутий елемент
                if (lastReturned == head) {
                    removeFirst();
                } else if (lastReturned == tail) {
                    removeLast();
                } else {
                    lastReturned.prev.next = lastReturned.next;
                    lastReturned.next.prev = lastReturned.prev;

                    lastReturned.prev = null;
                    lastReturned.next = null;
                    lastReturned.data = null;

                    size--;
                }

                lastReturned = null;
            }
        };
    }

    /**
     * Повертає ітератор для обходу списку у зворотному напрямку
     * @return ітератор
     */
    public Iterator<E> descendingIterator() {
        return new Iterator<E>() {
            private Node<E> current = tail;
            private Node<E> lastReturned = null;

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

            @Override
            public E next() {
                if (!hasNext()) {
                    throw new NoSuchElementException();
                }

                lastReturned = current;
                current = current.prev;
                return lastReturned.data;
            }
        };
    }

    /**
     * Отримує вузол за індексом
     * @param index індекс вузла
     * @return вузол за індексом
     */
    private Node<E> getNodeAt(int index) {
        // Оптимізація: якщо індекс ближче до початку, йдемо з початку
        // якщо ближче до кінця - йдемо з кінця
        if (index < size / 2) {
            Node<E> current = head;
            for (int i = 0; i < index; i++) {
                current = current.next;
            }
            return current;
        } else {
            Node<E> current = tail;
            for (int i = size - 1; i > index; i--) {
                current = current.prev;
            }
            return current;
        }
    }
}