Почему удаление узла из двусвязного списка происходит быстрее, чем удаление узла из односвязного списка?
Мне было любопытно, почему удаление узла из двойного связанного списка происходит быстрее, чем одиночного связанного. Согласно моей лекции, для двойного связанного списка требуется O(1) по сравнению с O(n) для одного связанного списка. Согласно моему мыслительному процессу, я думал, что они оба должны быть O(n), так как вам нужно пройти через все элементы, так что это зависит от размера.
Я понимаю, что это будет связано с тем фактом, что каждый узел имеет предыдущий указатель и следующий указатель на следующий узел, я просто не могу понять, как это будет постоянная операция в смысле O(1)
3 ответа
Это частично зависит от того, как вы интерпретируете настройку. Вот две разные версии.
Версия 1: Предположим, что вы хотите удалить узел связанного списка, содержащий определенное значение x, из списка с одиночной или двойной связью, но вы не знаете, где он находится в списке. В этом случае вам придется просматривать список, начиная с самого начала, пока вы не найдете узел, который нужно удалить. И в односвязном, и в двусвязном списке вы можете удалить его за O(1), поэтому общее время выполнения равно O(n). Тем не менее, сделать шаг удаления в односвязном списке труднее, поскольку вам нужно обновить указатель в предыдущей ячейке (на которую не указывает ячейка для удаления), поэтому вам нужно хранить два указателя как ты делаешь это.
Версия 2: Теперь давайте предположим, что вам дан указатель на ячейку для удаления, и вам нужно ее удалить. В двусвязном списке вы можете сделать это, используя следующий и предыдущий указатели, чтобы идентифицировать две ячейки вокруг ячейки, чтобы удалить их, а затем перемонтировать их, чтобы разделить ячейку из списка. Это занимает время O(1). Но как насчет односвязного списка? Чтобы удалить эту ячейку из списка, необходимо изменить следующий указатель ячейки, который появляется перед ячейкой для удаления, чтобы она больше не указывала на ячейку для удаления. К сожалению, у вас нет указателя на эту ячейку, поскольку список только односвязный. Поэтому вы должны начать с начала списка, пройтись по узлам вниз и найти узел, который находится непосредственно перед тем, который нужно удалить. Это занимает время O(n), поэтому время выполнения шага удаления в худшем случае равно O(n), а не O(1). (Тем не менее, если вы знаете два указателя - ячейку, которую хотите удалить, и ячейку прямо перед ней, то вы можете удалить ячейку за O(1) раз, так как вам не нужно сканировать список, чтобы найти предыдущую ячейку..)
Вкратце: если вы знаете, что ячейка должна быть удалена заранее, список с двойной связью позволяет вам удалить ее за время O(1), тогда как для списка с одной ссылкой потребуется время O(n). Если вы не знаете ячейку заранее, то в обоих случаях это O(n).
Надеюсь это поможет!
Этот список не нужно просматривать, чтобы подключить предыдущий узел к следующему узлу в двойном списке. Вы просто указываете
curr.Prev.Next = curr.Next а также curr.Next.Prev = curr.Prev,
В односвязном списке вы должны просмотреть список, чтобы найти предыдущий узел. Обход может быть O(n) в несортированном списке.
Альтернативный подход заключается в использовании двойных указателей, как описано в этом превосходном ресурсе: https://github.com/mkirchner/linked-list-good-taste. Это означает, что вам не нужно отслеживать текущий и предыдущий указатель, поскольку вы используете только один указатель на указатель, который может изменяться непосредственно на месте. Пожалуйста, дайте мне знать, если это неточно, поскольку я только что узнал об этом.