Реализовать односвязный список

71. Реализовать односвязный список

Условие задачи:
Необходимо реализовать собственный односвязный список на Java.

Список должен поддерживать:

добавление элемента в конец;
получение элемента по индексу;
удаление элемента по индексу;
получение количества элементов.

Спойлеры к решению

Подсказки

💡 Каждый элемент списка хранится в отдельном узле Node.
💡 Узел содержит значение и ссылку на следующий узел.
💡 Поле head указывает на первый элемент списка.
💡 Поле tail позволяет добавлять элементы в конец за O(1).
💡 При удалении первого или последнего элемента нужно обновить head или tail.

Решение

public class SinglyLinkedList<T> {

    private Node<T> head;
    private Node<T> tail;
    private int size;

    public void add(T value) {
        Node<T> newNode = new Node<>(value);

        if (head == null) {
            head = newNode;
            tail = newNode;
        } else {
            tail.next = newNode;
            tail = newNode;
        }

        size++;
    }

    public T get(int index) {
        checkIndex(index);
        return getNode(index).value;
    }

    public T remove(int index) {
        checkIndex(index);

        if (index == 0) {
            T removedValue = head.value;
            head = head.next;
            size--;

            if (size == 0) {
                tail = null;
            }

            return removedValue;
        }

        Node<T> previous = getNode(index - 1);
        Node<T> removed = previous.next;

        previous.next = removed.next;

        if (removed == tail) {
            tail = previous;
        }

        removed.next = null;
        size--;

        return removed.value;
    }

    public int size() {
        return size;
    }

    private Node<T> getNode(int index) {
        Node<T> current = head;

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

        return current;
    }

    private void checkIndex(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException(
                    "Index: " + index + ", size: " + size
            );
        }
    }

    private static class Node<T> {

        private final T value;
        private Node<T> next;

        private Node(T value) {
            this.value = value;
        }
    }
}

Пример использования:

SinglyLinkedList<String> list = new SinglyLinkedList<>();

list.add("one");
list.add("two");
list.add("three");

System.out.println(list.get(1)); // two

list.remove(1);

System.out.println(list.get(1)); // three
System.out.println(list.size()); // 2

Сложность операций:

add() — O(1);
get() — O(n);
remove() — O(n);
size() — O(1).