Списки
Односвязные и двусвязные списки
Осторожно: эти списки никак не связаны со списками из питона (которые на самом деле динамические массивы).
Проблема стека: нельзя добавлять и удалять элементы в середине.
Давайте хранить массив $values$ с нужными нам элементами, и для каждого элемента еще хранить (в структуре или в отдельном массиве $next$) индекс следующего элемента. И, конечно, хранить индекс самого первого элемента $start$. Будем называть такую структуру данных односвязным списком.
Чтобы пройтись по всему односвязному списку, нужно начать с индекса первого элемента и постепенно переходить по индексу следующего элемента ($i$ -> $next[i]$), пока $next[i] \neq i$.
Тогда если у нас есть индекс какого-то элемента $index$, мы за $O(1)$ можем вставить после него еще один - нужно добавить в массив справа еще один элемент, пусть он получил индекс $new$, и сделать $next[new] = next[index], next[index] = new$.
Часто бывает удобно хранить еще предыдущий элемент помимо следующего, чтобы можно было проходить по списку справа налево, и добавлять элемент перед каким-нибудь. Такой список называется двусвязным.