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

Связный список (англ. linked list) — структура данных, используемая для хранения данных. В обывательском смысле это как массив, только нефиксированного размера, чудеса.

Как устроен, есть ли побочные эффекты?

Связный список является очень простой вещью, по-сути это набор ячеек (если говорить абстрактно), где каждая ячейка имеет ссылку на следующую.
Последняя же ячейка, имеет вместо адреса следующей ячейки значение NULL, что при переборе должно означать, что дальше Бога нет это последний элемент в списке.
Главное отличие списка от массива состоит в том, что он не хранится на стеке, а в куче, что даёт меньшую скорость доступа. А также для нового элемента списка может просто банально не найтись свободного места в ОЗУ, что приведёт к аварийной ошибке, если не уследить за этим моментом.

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

Тот же связный список, но кроме ссылки на следующий элемент, хранит ссылку и на предыдущий. Обеспечивает возможность движения по списку в обе стороны, в ущерб размера элементов, так как в 64-битной архитектуре каждый указатель занимает 8 байт, а если принять во внимание, то что элементов в списке могут быть тысячи, а запущенных процессов может быть десятки, то уже может появиться заметное использование оперативной памяти.

Операции и взаимодействие

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

Добавить в конец (add)

• Берем связный список.
• Проходим по списку до самого конца (пока ссылка на след. элемент не станет равна NULL).
• Создаем новый элемент.
• Меняем ссылку последнего элемента, присваивая ей адрес созданного элемента.

Вставить (insert)

• Берем связный список и индекс элемента, после которого надо создать новый.
• Проходим по списку до нужного элемента (пока кол-во пройденных элементов не станет равно указанному индексу).
• Создаем новый элемент.
• Запоминаем адрес элемента следующего после того, на который указывает индекс.
• Меняем ссылку элемента с указанным индексом, присваивая ей адрес созданного элемента.
• Меняем ссылку нового элемента на адрес, который мы запомнили выше.

Удалить по индексу (pop)

• Берем связный список и индекс элемента, который нам надо стереть с лица земли.
• Проходим по списку до нужного элемента (пока кол-во пройденных элементов не станет равно указанному индексу).
• Когда кол-во пройденных элементов станет равно [индекс-1], то запоминаем адрес элемента, чтобы в дальнейшем его изменить.
• Получаем адрес элемента идущего после того, что нам нужно уничтожить.
• Уничтожаем элемент (высвобождаем занятую им память).
• Меняем ссылку элемента который мы до этого запомнили на адрес следующего элемента.