Связный список хранит элементы не рядом в памяти, а в узлах: каждый узел несёт данные и ссылку на следующий. Эта простая идея делает вставку и удаление O(1) без сдвигов, но превращает доступ по индексу в O(n). Модель памяти массива разбиралась в уроке про массив и динамический массив.

Массив и связный список
Массив и связный список

Узел и класс LinkedList

Node хранит два поля: value и next. Список знает только head, а размер считает отдельно, чтобы len работал за O(1). __iter__ написан как генератор (протокол итерации), поэтому list(...), sum(...) и in работают сразу; про __len__ — в уроке про dunder-методы.

python
class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next

class LinkedList:
    def __init__(self):
        self.head = None
        self._size = 0

    def push_front(self, value):
        self.head = Node(value, self.head)
        self._size += 1