Связный список

Введение

Связный список — это линейная структура данных, в которой элементы не хранятся в одном непрерывном блоке памяти. Вместо этого они хранятся как отдельные узлы, соединённые друг с другом с помощью указателей.

Каждый узел хранит:

• data — значение, содержащееся в узле;
• next — указатель на следующий узел в списке.

Для работы со связным списком мы обычно храним указатели на начало и конец списка. Они называются head и tail.

Таким образом, сам список может быть представлен как:

Типы связного списка

Односвязный список

Это стандартный связный список, описанный выше. Каждый узел хранит указатель только на следующий узел.

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

В двусвязном списке каждый узел хранит ещё один указатель: prev, который указывает на предыдущий узел.

Кольцевой связный список

В кольцевом связном списке последний узел указывает обратно на первый узел, образуя цикл.

Операции со связным списком

Поиск узла

Найти $i$-й узел

Индексация начинается с нуля.

Идея проста:

• начать с head;
• перейти к следующему узлу ровно $i$ раз.

Найти узел по значению

Чтобы найти узел с заданным значением:

• начать с head;
• двигаться вперёд, пока не будет найдено нужное значение или список не закончится.

Добавление узла