Что происходит при добавлении элемента в Stack реализованный с помощью LinkedList

Отличный вопрос, который касается фундаментальных структур данных и их реализации в Java. Давайте разберем по порядку, что именно происходит.

Основные концепции

Важно сразу уточнить термины. В Java Stack — это устаревший (legacy) класс, который наследуется от Vector и использует синхронизированные методы. В современной разработке рекомендуется использовать интерфейс Deque и его реализацию ArrayDeque для стека. Однако, ваш вопрос о реализации с помощью LinkedList — это классический учебный пример, который раскрывает внутреннюю механику.

Если мы говорим о реализации стека поведения (LIFO — Last In, First Out) с использованием LinkedList в качестве внутреннего хранилища, то ключевыми операциями будут push (добавление) и pop (извлечение).

Детальный процесс добавления элемента

Предположим, у нас есть простой класс StackOnLinkedList:

public class StackOnLinkedList<T> {
    private LinkedList<T> list = new LinkedList<>();

    public void push(T item) {
        // Основной метод добавления
    }
}

1. Вызов метода push(T item)

Когда вызывается метод push, элемент должен быть помещен на "верх" стека. В контексте LinkedList "верх" стека чаще всего — это начало списка (head). Это позволяет операциям push и pop выполняться за константное время O(1).

public void push(T item) {
    list.addFirst(item); // Или list.push(item);
}

2. Внутри LinkedList.addFirst(E e)

Метод addFirst выполняет последовательность действий:

• Создание нового узла: Создается объект внутреннего класса Node<E>, который содержит:

    *   `E item` — сам добавляемый элемент.
    *   `Node<E> next` — ссылка на следующий узел (который в данный момент является `first`, т.е. текущей головой списка).
    *   `Node<E> prev` — для двусвязного списка Java `LinkedList` это будет `null`, так как это начало.

• Обновление ссылок:

    *   Если список был **пуст**, то новый узел становится и `first`, и `last`.
    *   Если список **не пуст**, то:
        1.  Ссылка `next` нового узла устанавливается на текущий `first` узел.
        2.  Ссылка `prev` текущего старого `first` узла обновляется и начинает ссылаться на новый узел (так как список двусвязный).
        3.  Ссылка `first` самого объекта `LinkedList` перезаписывается и начинает указывать на новый узел.

• Инкремент счетчика: Увеличивается внутренний счетчик size (количество элементов в списке) и модификатор modCount (для корректной работы итераторов и проверки на одновременную модификацию).

3. Альтернатива — добавление в конец

Технически стек можно реализовать и добавляя элементы в конец (tail) LinkedList через addLast(). Тогда "верхушкой" стека будет последний элемент. Однако в этом случае операция pop() (удаление последнего элемента) все равно будет O(1), но для некоторых операций это может быть менее эффективно с точки зрения кеша процессора. Классический подход — использовать начало списка.

Сравнение с java.util.Stack

Если бы мы использовали стандартный java.util.Stack, то при вызове его метода push(E item) произошло бы следующее:

// Упрощенная суть метода из класса Stack
public E push(E item) {
    addElement(item); // Этот метод наследован от Vector
    return item;
}

Метод addElement(item) из Vector:

1. Проверяет, не нужно ли увеличить внутренний массив (Object[] elementData).
2. Присваивает элемент в ячейку массива по индексу elementCount.
3. Увеличивает elementCount.
4. Вся операция синхронизирована (synchronized), что создает дополнительные накладные расходы.

Преимущества и недостатки реализации на LinkedList

Преимущества:

• Динамический размер: Нет необходимости предопределять емкость и тратить время на ресайзинг массива (как в ArrayStack или Vector).
• Константное время O(1) операций push/pop: При корректной реализации (работе с head).
• Эффективное использование памяти для небольших объектов: Память выделяется только под новые элементы.

Недостатки:

• Высокая затрата памяти на каждый элемент: Для каждого элемента (Node) создаются дополнительные объекты с ссылками next и prev (плюс служебные заголовки объектов в JVM).
• Плохая локальность данных: Узлы списка могут быть разбросаны по памяти, что приводит к промахам кеша процессора (cache misses) и потенциальному снижению производительности по сравнению с ArrayDeque на больших объемах данных.

Заключение

При добавлении элемента в стек, реализованный через LinkedList, физически происходит вставка нового узла в начало двусвязного списка. Этот процесс включает создание объекта-узла, обновление ссылок соседних узлов и обновление заголовочной ссылки first самого списка. Хотя такая реализация наглядно демонстрирует принцип LIFO и эффективна по времени для основных операций, в промышленной разработке для стека предпочтительнее использовать ArrayDeque, как рекомендует официальная документация Java, из-за лучшей производительности и более экономного использования памяти.