Списки

Материал из Algocode wiki
Версия от 14:32, 18 октября 2019; Глеб (обсуждение | вклад) (Новая страница: «==Односвязные и двусвязные списки== Осторожно: эти списки никак не связаны со списками из...»)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

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

Осторожно: эти списки никак не связаны со списками из питона (которые на самом деле динамические массивы).

Проблема стека: нельзя добавлять и удалять элементы в середине.

Давайте хранить массив $values$ с нужными нам элементами, и для каждого элемента еще хранить (в структуре или в отдельном массиве $next$) индекс следующего элемента. И, конечно, хранить индекс самого первого элемента $start$. Будем называть такую структуру данных односвязным списком.

Чтобы пройтись по всему односвязному списку, нужно начать с индекса первого элемента и постепенно переходить по индексу следующего элемента ($i$ -> $next[i]$), пока $next[i] \neq i$.

Тогда если у нас есть индекс какого-то элемента $index$, мы за $O(1)$ можем вставить после него еще один - нужно добавить в массив справа еще один элемент, пусть он получил индекс $new$, и сделать $next[new] = next[index], next[index] = new$.

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