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

Для работы со связным списком мы обычно храним указатели на начало и конец списка. Они называются head и tail.
Таким образом, сам список может быть представлен как:
Типы связного списка
Односвязный список
Это стандартный связный список, описанный выше. Каждый узел хранит указатель только на следующий узел.
Двусвязный список
В двусвязном списке каждый узел хранит ещё один указатель: prev, который указывает на предыдущий узел.

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

Операции со связным списком
Поиск узла
Найти -й узел
Индексация начинается с нуля.
Идея проста:
- начать с
head; - перейти к следующему узлу ровно раз.
Найти узел по значению
Чтобы найти узел с заданным значением:
- начать с
head; - двигаться вперёд, пока не будет найдено нужное значение или список не закончится.