# Список
Список — это структура данных, хранящая элементы последовательно и позволяющая эффективно вставлять и удалять элементы в любом месте\.
## Односвязный список
Список состоит из узлов\. Каждый узел хранит в себе как минимум указатель на следующий узел и данные\. Если в узлах списка хранится указатель только на следующий узел, то это односвязный список\. Схематично его можно изобразить так:
У последнего узла в односвязном списке указатель на следующий узел равен [нулевому указателю](https://en.cppreference.com/w/cpp/language/pointer#Null_pointers)\. Сам список — это просто указатель на первый узел\.
Пример реализации односвязного списка на языке C можно посмотреть [здесь](https://pvs-studio.ru/ru/blog/terms/6680/), а на языке C\+\+ — [здесь](https://pvs-studio.ru/ru/blog/terms/6684/)\.
## Двусвязный список
Также в узлах списка можно хранить не только указатель на следующий узел, но и указатель на предыдущий узел\. Такой список называется двусвязным\. Схематично его можно изобразить следующим образом:
У первого узла в двусвязном списке указатель на предыдущий узел равен нулевому указателю\.
Пример реализации двусвязного списка на языке C можно посмотреть [здесь](https://pvs-studio.ru/ru/blog/terms/6682/), а на языке C\+\+ — [здесь](https://pvs-studio.ru/ru/blog/terms/6683/)\.
## Основные операции
### Обход списка и доступ к произвольному элементу
Чтобы обойти список, достаточно хранить указатель на текущий узел\. Переход на следующий узел осуществляется по хранимому в текущем узле указателю\.
Для обращения к n\-ому элементу списка нужно последовательно по указателям на следующий узел обойти первые n узлов\. Как результат, доступ к произвольному элементу происходит за _O\(n\)_\.
### Поиск
Поиск элемента в списке — это просто обход списка с проверкой каждого узла на наличие целевого элемента\. В худшем случае, например, если искомый элемент отсутствует в списке, будет выполнен обход всего списка\. В общем случае поиск выполняется за _O\(n\)_\.
### Вставка
Вставка в список осуществляется за _O\(1\)_\. Для вставки элемента в список достаточно создать новый узел и обновить значение нескольких указателей\.
Для вставки нового узла в односвязный список нужно выполнить следующие шаги:
1. Выбрать узел, после которого следует сделать вставку\.
1. Сохранить значение указателя на следующий узел у выбранного\.
1. Указатель на следующий узел у выбранного присвоить адресу вставляемого узла\.
1. Указатель на следующий узел у вставляемого присвоить в сохранённое значение на шаге 2\.
Схематически вставка выглядит так:
Для вставки нового узла в двусвязный список нужно выполнить следующие шаги:
1. Выбрать узел, перед которым следует сделать вставку\.
1. Сохранить значение указателя на предыдущий узел у выбранного\.
1. Сохранить значение указателя на следующий узел у узла перед выбранным\.
1. Указатель на предыдущий узел у выбранного присвоить адресу нового узла\.
1. Указатель на следующий узел у узла перед выбранным присвоить адресу нового узла\.
1. Указатель на предыдущий узел у вставляемого присвоить значению, сохранённому на шаге 2\.
1. Указатель на следующий узел у вставляемого присвоить значению, сохранённому на шаге 3\.
Схематически вставка выглядит так:
### Удаление
Удаление из списка выполняется за _O\(1\)_\. Для удаления узла из списка также достаточно обновить несколько указателей\.
Для удаления узла в односвязном списке нужно выполнить следующие шаги:
1. Выбрать узел, после которого следует сделать удаление\.
1. Сохранить значение указателя на следующий элемент у удаляемого узла\.
1. Указатель на следующий узел у выбранного присвоить адресу узла, сохранённому на шаге 2\.
1. Удалить узел и освободить память\.
Схематически удаление выглядит так:
Для удаления узла в двусвязном списке нужно выполнить следующие шаги:
1. Выбрать узел, который нужно удалить\.
1. Сохранить значение указателя на предыдущий узел у удаляемого узла\.
1. Сохранить значение указателя на следующий узел у удаляемого узла\.
1. Указатель на предыдущий узел у узла после выбранного присвоить адресу узла, сохранённому на шаге 2\.
1. Указатель на следующий узел у узла перед выбранным присвоить адресу узла, сохранённому на шаге 3\.
1. Удалить узел и освободить память\.
Схематически удаление выглядит так:
## Список VS массив
Массив — это структура данных, хранящая элементы в линейном порядке непрерывно в памяти и поддерживающая возможность обращения к произвольному элементу последовательности\. Схематично массив выглядит так:
Чтобы удалить элемент из середины массива, нужно сдвинуть все элементы, стоящие после удаляемого элемента, на одну позицию вперёд:
Чтобы удалить 100\-ый элемент в массиве из 1000 элементов, нужно сделать 900 перемещений\. Таким образом, удаление элемента из любой позиции, кроме конца, происходит за _O\(n\)_\. Удаление элемента из конца происходит за _O\(1\)_\.
Не лучше обстоит дело и со вставкой в середину массива\. В этом случае все элементы массива после места вставки нужно переместить на одну позицию назад:
Чтобы вставить элемент на 100\-ую позицию в массиве из 1000 элементов, нужно 900 перемещений\. Таким образом, вставка элемента в любую позицию, кроме конца, происходит за _O\(n\)_\. Вставка элемента в конец происходит за _O\(1\)_\.
Как мы видим, вставка и удаление в произвольное место массива, кроме конца, неэффективны\. В то же время для вставки или удаления элемента в любом месте списка достаточно обновления нескольких указателей \(не более четырех\)\. Это означает, что если вам нужно удалять и вставлять элементы в произвольные места вашей последовательности, то хранить её элементы лучше в списке\.
Исходя из вышесказанного, можно выделить еще одно достоинство списка: он гарантирует, что ссылки на элементы и итераторы на узлы остаются валидными при любых вставках и удалениях \(кроме самих удаляемых узлов\)\. Для массивов всё сложнее:
* При вставках:
* Если произошла реаллокация для хранения большего числа элементов, то инвалидируются все итераторы и ссылки на элементы\.
* Иначе они валидны до позиции вставки\. Итераторы и ссылки, начиная с позиции вставки, инвалидируются\.
* При удалениях инвалидируются все итераторы и ссылки после удаляемого элемента\.
Недостаток списка заключается в медленном доступе к произвольному элементу списка\. Если вам нужен 901\-ый элемент списка, вам придётся обойти все 900 первых элементов списка\. Кроме того, элементы списка, как правило, расположены непоследовательно в виртуальной памяти\. Это означает, что каждый переход к следующему узлу будет сопровождаться произвольным обращением к памяти\.
Элементы массива расположены непрерывно в виртуальной памяти\. Поэтому обращение к произвольному элементу — это одно обращение по адресу, полученному с помощью адресной арифметики: к адресу нулевого элемента прибавляется смещение, равное _n_ \* _sizeof\(Item\)_\. Кроме этого, если выполняется последовательный доступ к элементам массива небольшого размера, современные процессоры умеют это распознавать и загружают данные заранее в кэш \([cache prefetching](https://en.wikipedia.org/wiki/Cache_prefetching)\)\. Например, при размере кэш\-линии в 64 байта при обращении к элементу массива типа _int_ размером 4 байта процессор загрузит в свой кэш сразу 16 элементов\. В случае списков из\-за [кэш\-промахов](https://en.wikipedia.org/wiki/CPU_cache#Cache_miss) процессору придётся намного чаще обращаться в виртуальную память, а это значительно медленнее обращений в кэш процессора\.
Поэтому, если вам нужен произвольный доступ к элементам последовательности, используйте массив вместо списка\.
Краткое сравнение массива и списка выглядит так:
||Обращение к произвольному элементу|Вставка нового элемента|Удаление произвольного элемента|
|---|---|---|---|
|Массив|\_O\\\(1\\\)\_|\_O\\\(n\\\)\_ в общем случае
\_O\\\(1\\\)\_ при вставке в конец|\_O\\\(n\\\)\_
\_O\\\(1\\\)\_ при удалении из конца|
|Список|\_O\\\(n\\\)\_|\_O\\\(1\\\)\_|\_O\\\(1\\\)\_|
## Дополнительные ссылки
* [List](https://en.cppreference.com/w/cpp/container/list)
* [Реализация двусвязного списка на C](https://pvs-studio.ru/ru/blog/terms/6682/)
* [Реализация двусвязного списка на C\+\+](https://pvs-studio.ru/ru/blog/terms/6683/)
* [Реализация односвязного списка на C](https://pvs-studio.ru/ru/blog/terms/6680/)
* [Реализация односвязного списка на C\+\+](https://pvs-studio.ru/ru/blog/terms/6684/)