Связные СпискиLinked Lists

Список состоит из узлов, каждый из которых хранит значение и указатель на следующий узел (в двусвязном списке — ещё и на предыдущий). Структура поддерживает указатель на head (первый узел) и обычно на tail (последний), что делает push_front и push_back операциями O(1): новый узел создаётся, его указатель next устанавливается на текущий head (или, для push_back, текущий tail's next устанавливается на новый узел), после чего head (или tail) переставляется на новый узел. Удаление узла с уже известным предыдущим соседом — тоже O(1): указатель предыдущего узла просто перенаправляется через удаляемый, на его next.A list consists of nodes, each storing a value and a pointer to the next node (in a doubly linked list, also to the previous one). The structure maintains a pointer to head (the first node) and usually to tail (the last), making push_front and push_back O(1) operations: a new node is created, its next pointer is set to the current head (or, for push_back, the current tail's next is set to the new node), then head (or tail) is repointed to the new node. Deleting a node whose previous neighbor is already known is also O(1): the previous node's pointer is simply rerouted around the deleted one, to its next.

Цена этой гибкости — потеря произвольного доступа: чтобы добраться до k-го элемента, нет способа быстрее, чем пройти по цепочке от head, делая k шагов, — O(n) в худшем случае, тогда как массив делает это за O(1) благодаря непрерывности памяти и арифметике индексов.The price of this flexibility is losing random access: reaching the k-th element has no way faster than walking the chain from head, taking k steps — O(n) worst case, whereas an array does it in O(1) thanks to memory contiguity and index arithmetic.

struct Node {
    int val;
    Node* next;
};

struct LinkedList {
    Node* head = nullptr;
    Node* tail = nullptr;

    void push_front(int val) {
        Node* n = new Node{val, head};
        head = n;
        if (!tail) tail = n;
    }

    void push_back(int val) {
        Node* n = new Node{val, nullptr};
        if (tail) tail->next = n; else head = n;
        tail = n;
    }

    bool remove(int val) {          // поиск сам по себе O(n), удаление — O(1)// the search itself is O(n), the removal is O(1)
        Node* prev = nullptr;
        for (Node* cur = head; cur; prev = cur, cur = cur->next) {
            if (cur->val == val) {
                if (prev) prev->next = cur->next; else head = cur->next;
                if (cur == tail) tail = prev;
                delete cur;
                return true;
            }
        }
        return false;
    }
};

Каждый узел — блок со значением и стрелкой к следующему. Кнопки push_front/push_back/delete выполняют операцию сразу; жёлтая подсветка отмечает затронутый узел.Each node is a block with a value and an arrow to the next one. The push_front/push_back/delete buttons execute immediately; yellow highlights the affected node.

В однонаправленном списке (показанном выше) удаление произвольного узла требует знания его предшественника — если дан только указатель на сам узел, единственный способ найти предыдущий — пройти список с начала, O(n). Двусвязный список хранит указатель prev в каждом узле, что делает удаление по известному указателю на сам узел настоящим O(1) без поиска — цена ровно один дополнительный указатель на узел.In a singly linked list (shown above), deleting an arbitrary node requires knowing its predecessor — if only a pointer to the node itself is given, the only way to find the predecessor is to walk the list from the start, O(n). A doubly linked list stores a prev pointer in every node, making deletion via a known pointer to the node itself a true O(1) with no search — the cost is exactly one extra pointer per node.

Sentinel-узлы (фиктивные head/tail, которые никогда не удаляются и не хранят реальные данные) устраняют особые случаи "список пуст" и "удаляем единственный элемент" из кода: вставка и удаление всегда работают с реальным соседом с обеих сторон, без проверок на nullptr для head/tail. Это классический пример того, как небольшая структурная избыточность упрощает логику операций ценой константной дополнительной памяти.Sentinel nodes (dummy head/tail that are never removed and hold no real data) eliminate the "list is empty" and "deleting the only element" special cases from the code: insertion and deletion always work with a real neighbor on both sides, with no nullptr checks for head/tail. This is a classic example of how a bit of structural redundancy simplifies operation logic at the cost of constant extra memory.