Алгоритм для удаления одного элемента в единственном связанном списке с O (1) сложность

Я - студент информатики в Германии. Мой преподаватель дал использованию следующий вопрос думать о:

'Учитывая ссылку на узел в единственном связанном списке (который не является последним узлом). Дайте алгоритм для удаления этого элемента из списка, который имеет O (1) сложность при поддержании целостности'.

Я думал об этом, но я вполне уверен, что нет такого алгоритма. так как это - единственный связанный список, необходимо циклично выполниться через каждый узел в списке, пока Вы не достигаете узла, который должен быть, удаляют, потому что необходимо изменить прямой указатель в узле перед удаленным. Который привел бы к O (n) сложность.

Я пропускаю что-нибудь?

8
задан code4life 27 September 2012 в 17:16
поделиться

6 ответов

Это зависит от того, являются ли узлы изменяемыми (по значению).

Там есть способ сделать это, если вы можете делать то, что вам нравится с узлы:

toDelete.value = toDelete.next.value
toDelete.next = toDelete.next.next

Вся информация из toDelete теперь перезаписана информацией из старого toDelete.next . (В зависимости от платформы вам может потребоваться освободить старый toDelete.next - что означает сохранение временной ссылки на него. Не хорошо, если у кого-то еще есть ссылка на него, конечно. В Java / C # вы бы просто проигнорировали это.)

Я пытался выработать способ намека на это, не отдавая его, но это довольно сложно ...

Он полагается, что это не последний узел в хотя список.

24
ответ дан 5 December 2019 в 04:46
поделиться

Не совсем считается удаление узла, но вы можете скопировать данные следующего узла в текущий и удалить следующий узел:

// pseudocode:
this.data = next.data;
var temp = this.next;
this.next = next.next;
delete temp;
8
ответ дан 5 December 2019 в 04:46
поделиться

Если узлы являются базовыми структурами в памяти, вы можете скопировать содержимое «следующего» узел в ячейку памяти удаленного узла и освобождает память, где был «следующий» узел.

3
ответ дан 5 December 2019 в 04:46
поделиться

Да. Вы сохраняете в качестве итеративного указателя указатель на следующий указатель предыдущего списка.

walk = &head;
while (!match(*walk)) {
    walk = &walk[0]->next;
    if (!*walk) return ;
}
*walk = walk[0]->next;
2
ответ дан 5 December 2019 в 04:46
поделиться

Предполагая, что у вас есть указатель на узел, который вы хотите удалить. Скопируйте следующее значение в текущий узел. Заменить текущий указатель на узел, на который указывает следующий.

2
ответ дан 5 December 2019 в 04:46
поделиться
2
ответ дан 5 December 2019 в 04:46
поделиться
Другие вопросы по тегам:

Похожие вопросы: