Связный список
Связный список (англ. linked list) — структура данных, используемая для хранения данных. В обывательском смысле это как массив, только нефиксированного размера, чудеса.
Как устроен, есть ли побочные эффекты?[править]
Связный список является очень простой вещью, по-сути это набор ячеек (если говорить абстрактно), где каждая ячейка имеет ссылку на следующую.
Хороший пример IRL — очереди за колбасой и на почту.
Последняя же ячейка, имеет вместо адреса следующей ячейки значение NULL, что при переборе должно означать, что дальше Бога нет это последний элемент в списке.
Главное отличие списка от массива состоит в том, что он не хранится на стеке, а в куче[1], что даёт меньшую скорость доступа. А также для нового элемента списка может просто банально не найтись свободного места в ОЗУ, что приведёт к аварийной ошибке, если не уследить за этим моментом.
Двусвязный список[править]
Тот же связный список, но кроме ссылки на следующий элемент, хранит ссылку и на предыдущий. Обеспечивает возможность движения по списку в обе стороны, в ущерб размера элементов, так как в 64-битной архитектуре каждый указатель занимает 8 байт, а если принять во внимание, то что элементов в списке могут быть тысячи, а запущенных процессов может быть десятки, то уже может появиться заметное использование оперативной памяти.
Интрузивный связанный список[править]
Это когда ссылки на следующий (предыдущий, или обе) элемент хранятся внутри самих элементов списка, а не хранящих эти элементы узлов. Более низкоуровневый способ организации данных позволяет связывать элементы, созданные кем-то еще и хранимые где угодно.
Список без слова «связный»[править]
Не следует путать связный список и просто список. В некоторых языках List — интерфейс последовательного контейнера, обеспечивающего эффективный доступ по индексам и быструю вставку в конец, таким требованиям удовлетворяет обычный динамический массив.
Операции и взаимодействие[править]
Допустим, у нас есть односвязный список, то какие базовые операции мы может делать:
Вставить в начало[править]
- Создаем новый элемент и записываем ему .next на адрес текущей головы списка (в случае изначально пустого списка это NULL, все ок)
- Обновляем ссылку на начало ссылкой на новый элемент
Добавить в конец (add)[править]
- Берем связный список.
- Проходим по списку до самого конца (пока ссылка на след. элемент не станет равна NULL).
- Создаем новый элемент.
- Меняем ссылку последнего элемента, присваивая ей адрес созданного элемента.
Вставить (insert)[править]
- Берем связный список и индекс элемента, после которого надо создать новый.
- Проходим по списку до нужного элемента (пока кол-во пройденных элементов не станет равно указанному индексу).
- Создаем новый элемент.
- Запоминаем адрес элемента следующего после того, на который указывает индекс.
- Меняем ссылку элемента с указанным индексом, присваивая ей адрес созданного элемента.
- Меняем ссылку нового элемента на адрес, который мы запомнили выше.
Удалить по индексу (pop)[править]
- Берем связный список и индекс элемента, который нам надо стереть с лица земли.
- Проходим по списку до нужного элемента (пока кол-во пройденных элементов не станет равно указанному индексу).
- Когда кол-во пройденных элементов станет равно [индекс-1], то запоминаем адрес элемента, чтобы в дальнейшем его изменить.
- Получаем адрес элемента идущего после того, что нам нужно уничтожить.
- Уничтожаем элемент (высвобождаем занятую им память).
- Меняем ссылку элемента который мы до этого запомнили на адрес следующего элемента.
Удалить элемент из произвольного места (remove)[править]
- Берем непустой связный список и элемент, предшествующий тому, который хотим стереть с лица земли
- Заменяем у предшествующего элемента ссылку на .next на .next стираемого элемента
- Удаляем осиротевший элемент, на которого теперь никто не ссылается
Обход контейнера[править]
- Берем связный список
- Заводим переменную — указатель на текущий узел, изначально указывающий на начало
- Пока текущий указатель не NULL, делаем что-то с содержимым узла, а потом обновляем указатель на .next
- Из-за особенностей работы процессора с памятью[2], последовательный доступ к элементам не так эффективен, как для массивов, что несколько ограничивает применение.
Доступ по индексу[править]
- Берем связный список
- Как и в случае с обходом, переходим к следующему элементу N раз, пока не насчитаем нужный
- Операция имеет линейную сложность O(N), поэтому так лучше не делать, это НЕ то, для чего нужен этот контейнер.
Объединение двух связанных списков[править]
- Берем два связанных списка
- Записываем .next последнего элемента в head второго списка
- Помечаем второй список как пустой (head = NULL)
Примечания[править]
- ↑ важно ответить, что массив тоже может хранится в куче, если его выделить динамически
- ↑ чтение памяти по произвольному адресу — операция довольно медленная, а пользовательские данные обычно упакованы плотно, поэтому при запросе в RAM по заданному адресу процессор читает не только запрошенные данные, а целый блок с запасом («кеш-линия»), и записывает в собственную быстродействующую память. Если следующий запрос будет по близкому адресу — данные возьмутся прямо из кеша. В противном случае процессору придется заново читать память, такая ситуация называется «cache miss»
