2

Есть ли способ удалить элемент из односвязного списка за О(1)? При условии, что у нас есть указатель на удаляемый элемент.

5
  • 3
    Как вариант — перекопировать следующий в удаляемый, и удалить следующий...
    – Harry
    22 окт 2021 в 9:34
  • @Harry, и что делать, если он последний?
    – avp
    22 окт 2021 в 13:46
  • @avp Добавить еще один и удалять :)
    – Harry
    22 окт 2021 в 14:18
  • @Lil_Chil, если адреса указателя на начало списка у вас нет, то первый и последний в списке удалить не получится. И сами, наверное, понимаете, что если на данные в списке есть указатели из других структур, то копировать элементы списка друг в друга нельзя
    – avp
    22 окт 2021 в 16:07
  • Есть интерфейс односвязного списка, который приписывают Джону Кармаку. В нем можно удалять и добавлять элемент за O(1). 22 окт 2021 в 18:35

1 ответ 1

3

В C и в C++ можно сделать односвязный список с удалением элемента за константу. Для этого в интерфейс функций добавляется дополнительный уровень косвенности: функции получают не адрес узла, а адрес указателя на адрес узла (обычно в предыдущем элементе списка). Идею подал Джон Кармак.

// gcc -std=c11 -pedantic -Wall -Wextra -Werror -O3 carmack-list.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct node_t node_t;
struct node_t {
    char value;
    node_t *next;
};

void insert_head(node_t **head, char value) {
    node_t *new_node = malloc(sizeof(node_t));
    new_node->value = value;
    new_node->next = *head;
    *head = new_node;
}

void remove_head(node_t **head) {
    node_t *old_node = *head;
    *head = (*head)->next;
    free(old_node);
}

node_t **find(node_t **head, char value) {
    node_t **node;
    for (node = head; *node != NULL; node = &(*node)->next) {
        if ((*node)->value == value) {
            break;
        }
    }
    return node;
}

node_t *make_list(const char *s) {
    node_t *head = NULL;
    for (int i = strlen(s) - 1; i >= 0; --i) {
        insert_head(&head, s[i]);
    }
    return head;
}

void print_list(node_t *head) {
    for (node_t *node = head; node != NULL; node = node->next) {
        putc(node->value, stdout);
    }
    putc('\n', stdout);
}

int main() {
    node_t *list = make_list("C+-C+-C+-C");
    print_list(list);
    for (; ; ) {
        node_t **node = find(&list, 'C');
        if (*node == NULL) {
            break;
        }
        remove_head(node);
        print_list(list);
    }
}
$ gcc -std=c11 -pedantic -Wall -Wextra -Werror -O3 carmack-list.c && ./a.out 
C+-C+-C+-C
+-C+-C+-C
+-+-C+-C
+-+-+-C
+-+-+-
6
  • 1
    Супер! Для лучшего (более быстрого) понимания читателями сути, я бы добавил несколько слов -- "...добавляется дополнительный уровень косвенности: функции получают не адрес узла, а адрес указателя на адрес узла в предыдущем элементе списка" / Кстати, мне помнится подобная идея была у Кнута в т. 1
    – avp
    23 окт 2021 в 16:18
  • @avp, спасибо. Я добавил "обычно в предыдущем элементе списка". Для головы списка это указатель на локальную переменную указывающую на голову списка. :( 23 окт 2021 в 16:28
  • @StanislavVolodarskiy Спасибо, идея классная. Но можно Вас попросить на пальцах простыми словами описать как будет работать алгоритм удаления элемента за константу? С этим вашим доп. уровнем косвенности.(Код для меня сложный).
    – Lil_Chill
    24 окт 2021 в 10:57
  • В функцию удаления передаётся адрес поля next предыдущего узла. Функция удаляет следующий узел и исправляет поле в предыдущем. Это в каком-то смысле обман - указатели указывают не на сами узлы, а на поля в предыдущих узлах. В языках без возможности указывать на поле делается указатель на предыдущий узел, а для головы списка заводится дополнительный "узел перед началом списка". 24 окт 2021 в 14:50
  • @StanislavVolodarskiy А если нет возможности передать адрес next предыдущего узла? Чтобы его передать, нужно перебрать весь список и найти его, а это уже будет O(n)
    – Lil_Chill
    25 окт 2021 в 10:54

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.