У массива есть врождённая проблема: вставка и удаление в середине заставляют сдвигать элементы, а размер задан заранее. Связанный список решает и то и другое — это, пожалуй, вторая по популярности структура хранения после массива. Плата за гибкость — потеря быстрого доступа по индексу. Разберём, как он устроен.

Узлы и ссылки

В массиве элементы лежат подряд, и позиция каждого известна по индексу. В связанном списке всё иначе: каждый элемент — это отдельный объект-узел (node), который хранит данные и ссылку на следующий узел. Узлы разбросаны по памяти где угодно, а держатся вместе за счёт этих ссылок — как звенья цепи.

class Node {
    long data;
    Node next;
}

Класс, поле которого ссылается на объект того же класса, называют самоссылочным. Сам список хранит только ссылку на первый узел (first); от него по цепочке next можно дойти до любого. Последний узел ссылается в «никуда» (null) — это признак конца списка.

Ключевая идея: список опирается на отношения между элементами, а не на их позиции. В массиве вы находите дом по адресу; в списке — только пройдя по цепочке от начала, спрашивая каждого: «где следующий?».

Что список делает быстро, а что медленно

  • Вставка в начало — O(1). Создаём узел, его next направляем на бывший первый, а first — на новый. Ничего сдвигать не надо, сколько бы элементов ни было.
  • Удаление из начала — O(1). Просто сдвигаем first на второй узел.
  • Удаление узла из середины — дёшево, если он уже найден: достаточно у предыдущего узла заменить ссылку next, «перекинув» её через удаляемый. Никаких сдвигов.
  • Поиск — O(N). Здесь слабость: чтобы найти элемент по значению или дойти до нужной позиции, приходится идти по цепочке от начала.

Сравните с массивом: у массива быстрый доступ по индексу, но дорогая вставка/удаление; у списка — наоборот. Это ещё один пример главного принципа: у каждой структуры свои сильные и слабые стороны.

Двусвязный список

У простого (односвязного) списка есть неудобство: по нему можно двигаться только вперёд, а зная узел, нельзя быстро попасть к предыдущему. Двусвязный список добавляет в каждый узел вторую ссылку — на предыдущий элемент (prev). Теперь список можно обходить в обе стороны, а удаление узла не требует отдельно искать предшественника.

Плата — лишняя ссылка в каждом узле (чуть больше памяти) и необходимость аккуратно обновлять обе ссылки при каждой операции. Двусвязный список — удобная основа для дека, где добавляют и забирают с обоих концов.

Список как основа для других структур

Связанный список часто служит фундаментом для других структур. Стек и очередь можно построить не на массиве, а на списке: push/pop стека — это вставка/удаление в начале списка, обе O(1). Преимущество перед массивом — не нужно заранее знать размер: список растёт по мере надобности.

Здесь всплывает важное понятие — абстрактный тип данных (ADT). Стек определяется не тем, как он устроен внутри, а тем, что умеет: push, pop, peek. А внутри это может быть массив или связанный список — пользователю всё равно. ADT описывает поведение (интерфейс), отделяя его от реализации. Это позволяет менять внутреннее устройство, не трогая код, который структурой пользуется.

Сортированный список

Как и массив, список можно держать отсортированным — новый элемент вставляют не в начало, а на нужное по порядку место. При этом:

  • вставка становится O(N) (надо пройти до места вставки), но по-прежнему без сдвигов — только перекинуть пару ссылок;
  • минимальный (или максимальный) элемент всегда в начале, его выемка мгновенна.

Сортированный список удобен как простая приоритетная очередь и как способ отсортировать данные вставкой по мере поступления.

Итераторы

Слабое место списка — нет доступа по индексу. Если нужно не просто «найти по значению», а планомерно ходить по списку, вставлять и удалять в произвольном месте, используют итератор — отдельный объект, который помнит текущую позицию в списке (ссылку на текущий узел) и умеет двигаться к следующему, читать, вставлять и удалять «здесь». Итератор — это как палец, которым ведут по строчкам: он даёт контролируемый доступ к середине списка, которого у самого списка нет. Тот же принцип лежит в основе перебора коллекций в стандартных библиотеках.

Коротко

  • Связанный список — цепочка узлов, каждый хранит данные и ссылку на следующий; список опирается на связи между элементами, а не на позиции.
  • Вставка и удаление в начале — O(1), без сдвигов и без заранее заданного размера. Поиск — O(N): надо идти по цепочке.
  • Двусвязный список добавляет ссылку на предыдущий узел — обход в обе стороны, удобная основа для дека.
  • Список — частая основа для стека и очереди; отсюда идея ADT: структура определяется поведением, а не внутренним устройством.
  • Сортированный список держит элементы по порядку; итератор даёт контролируемый доступ к середине.

Дальше — рекурсия: приём, где метод вызывает сам себя, и на нём же работает стек вызовов, который мы уже упоминали.