Есть ли способ удалить элемент из односвязного списка за О(1)? При условии, что у нас есть указатель на удаляемый элемент.
1 ответ
В 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 +-+-+-
-
1Супер! Для лучшего (более быстрого) понимания читателями сути, я бы добавил несколько слов -- "...добавляется дополнительный уровень косвенности: функции получают не адрес узла, а адрес указателя на адрес узла в предыдущем элементе списка" / Кстати, мне помнится подобная идея была у Кнута в т. 1– avp23 окт 2021 в 16:18
-
@avp, спасибо. Я добавил "обычно в предыдущем элементе списка". Для головы списка это указатель на локальную переменную указывающую на голову списка. :( 23 окт 2021 в 16:28
-
@StanislavVolodarskiy Спасибо, идея классная. Но можно Вас попросить на пальцах простыми словами описать как будет работать алгоритм удаления элемента за константу? С этим вашим доп. уровнем косвенности.(Код для меня сложный). 24 окт 2021 в 10:57
-
В функцию удаления передаётся адрес поля
next
предыдущего узла. Функция удаляет следующий узел и исправляет поле в предыдущем. Это в каком-то смысле обман - указатели указывают не на сами узлы, а на поля в предыдущих узлах. В языках без возможности указывать на поле делается указатель на предыдущий узел, а для головы списка заводится дополнительный "узел перед началом списка". 24 окт 2021 в 14:50 -
@StanislavVolodarskiy А если нет возможности передать адрес next предыдущего узла? Чтобы его передать, нужно перебрать весь список и найти его, а это уже будет O(n) 25 окт 2021 в 10:54
O(1)
.