В этом интервью Slashdot Линус Торвальдс цитирует слова:
Я видел слишком много людей, которые удаляли односвязную запись списка, отслеживая запись «prev», а затем удаляли запись, делая что-то вроде
if (prev)
prev-> next = entry-> next;
иначе
list_head = entry-> next;и всякий раз, когда я вижу такой код, я просто говорю: «Этот человек не понимает указателей». И это, к сожалению, довольно часто.
Люди, которые понимают указатели, просто используют «указатель на указатель записи» и инициализируют его адресом list_head. И затем, проходя по списку, они могут удалить запись без использования каких-либо условий, просто выполнив «* pp = entry-> next».
Как разработчик PHP, я не касался указателей с момента введения в Си в университете десять лет назад. Тем не менее, я чувствую, что это тип ситуации, с которой я, по крайней мере, должен быть знаком. О чем говорит Линус? Если честно, если бы меня попросили реализовать связанный список и удалить элемент, то вышеупомянутый «неправильный» путь - это то, как я бы поступил. Что мне нужно знать, чтобы кодировать, как лучше всего говорит Линус?
Я спрашиваю здесь, а не о переполнении стека, поскольку у меня фактически нет проблем с этим в производственном коде.
prev
, а не весь узел, вы можете просто сохранить местоположениеprev.next
, так как это единственное, что вас интересует. Указатель на указатель. И если вы сделаете это, вы избежите глупостиif
, так как теперь у вас нет неловкого случаяlist_head
быть указателем извне узла. В этом случае указатель на начало списка семантически совпадает с указателем на следующий узел.Ответы:
Используя мои навыки L331 MS Paint:
Первоначальное решение - указать на узлы через
curr
. В этом случае вы проверяете, имеет ли следующий узелcurr
значение удаления, и если это так, сбрасываете указательcurr
узлаnext
. Проблема в том, что нет узла, который указывает на заголовок списка. Это означает, что должен быть особый случай, чтобы проверить это.Вместо этого Линус (скорее всего) предлагает не сохранять указатель на текущий проверенный узел, а скорее указатель на указатель на текущий узел (помеченный
pp
). Операция такая же - еслиpp
указатель указывает на узел с правильным значением, вы сбрасываетеpp
указатель.Разница возникает в самом начале списка. Хотя нет узла, который указывает на заголовок списка, на самом деле есть указатель на заголовок списка. И это точно такой же указатель на узел, как и
next
указатель на другой узел . Следовательно, нет необходимости в специальном предложении для начала списка.источник
list_head
указывать на что-то сnext
узлом, который указывает на первый реальный элемент данных (иprev
инициализировать этот же фиктивный объект). Мне не нравится идеяprev
указывать на что-то другого типа, поскольку такие приемы могут вводить неопределенное поведение с помощью псевдонимов и делать код ненужным образом чувствительным к структуре структуры.prev
указывать на узлы, он указывает на указатели. Он всегда указывает на что-то одного типа, а именно указатель на узел. Ваше предложение по сути то же самое - имейте вprev
виду что-то "сnext
узлом". Если вы отбрасываете оболочку, вы просто получаете начальныйlist_head
указатель. Или, другими словами, то, что определяется только указателем на следующий узел, семантически эквивалентно указателю на узел.list_head
иnext
будет держать такой же «вид» указателя. Возможно, не проблема в C, но, возможно, проблема в C ++.Пример кода
Если нам нужна логика для уничтожения узла, тогда мы можем просто добавить строку кода в конце:
источник