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

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

Сложность: вставка/удаление в известном месте — O(1); доступ по индексу и поиск — O(n). Память: O(n), но с накладными расходами на ссылки.

class Node:
    def __init__(self, val, nxt=None):
        self.val = val
        self.next = nxt

head = Node(1, Node(2, Node(3)))
node = head
while node:          # обход O(n)
    print(node.val)
    node = node.next