Алгоритм для удаления одного элемента в единственном связанном списке с O (1) сложность
Я - студент информатики в Германии. Мой преподаватель дал использованию следующий вопрос думать о:
'Учитывая ссылку на узел в единственном связанном списке (который не является последним узлом). Дайте алгоритм для удаления этого элемента из списка, который имеет O (1) сложность при поддержании целостности'.
Я думал об этом, но я вполне уверен, что нет такого алгоритма. так как это - единственный связанный список, необходимо циклично выполниться через каждый узел в списке, пока Вы не достигаете узла, который должен быть, удаляют, потому что необходимо изменить прямой указатель в узле перед удаленным. Который привел бы к O (n) сложность.
Я пропускаю что-нибудь?
6 ответов
Это зависит от того, являются ли узлы изменяемыми (по значению).
Там есть способ сделать это, если вы можете делать то, что вам нравится с узлы:
toDelete.value = toDelete.next.value
toDelete.next = toDelete.next.next
Вся информация из toDelete теперь перезаписана информацией из старого toDelete.next . (В зависимости от платформы вам может потребоваться освободить старый toDelete.next - что означает сохранение временной ссылки на него. Не хорошо, если у кого-то еще есть ссылка на него, конечно. В Java / C # вы бы просто проигнорировали это.)
Я пытался выработать способ намека на это, не отдавая его, но это довольно сложно ...
Он полагается, что это не последний узел в хотя список.
Не совсем считается удаление узла, но вы можете скопировать данные следующего узла в текущий и удалить следующий узел:
// pseudocode:
this.data = next.data;
var temp = this.next;
this.next = next.next;
delete temp;
Если узлы являются базовыми структурами в памяти, вы можете скопировать содержимое «следующего» узел в ячейку памяти удаленного узла и освобождает память, где был «следующий» узел.
Да. Вы сохраняете в качестве итеративного указателя указатель на следующий указатель предыдущего списка.
walk = &head;
while (!match(*walk)) {
walk = &walk[0]->next;
if (!*walk) return ;
}
*walk = walk[0]->next;
Предполагая, что у вас есть указатель на узел, который вы хотите удалить. Скопируйте следующее значение в текущий узел. Заменить текущий указатель на узел, на который указывает следующий.
перемещать данные, а не ссылку. посмотрите на эту другую ветку: Удаление среднего узла из одного связанного списка, когда указатель на предыдущий узел недоступен