Удаление случайного узла из односвязных и двусвязных списков

Мне сложно придумать логику удаления какого-либо узла как из двусвязного, так и из односвязного списка. Я искал в Интернете справку, но не нашел простого примера. Вот что у меня есть:

Двусвязное удаление. dCurrent - это узел, который мы хотим удалить.

if (dCurrent == dHead){
   dHead = dCurrent->next;
   dHead->prev = NULL;
}
else if(dCurrent == dTail){
   dTail = dCurrent->prev;
   dTail->next = NULL;
}
else{
   dCurrent->next->prev = dCurrent->prev;
   dCurrent->prev->next = dCurrent->next;   
}

Вот что у меня есть для односвязного списка. Опять же, sCurrent - это узел, который нужно удалить. и sPrev = sCurrent->prev.

if(sPrev == NULL){
   sHead = sCurrent->next;
}
else{
   sPrev->next = sCurrent->next;
}

Проблема в том, что после удаления набора случайных узлов из обоих списков двусвязный список отображается правильно от головы до хвоста, но не от хвоста к голове. Односвязный список тоже отображается некорректно.


c linked-list doubly-linked-list singly-linked-list
person Michael Schilling    schedule 30.11.2011    source источник
comment
Так в чем твоя проблема. С первого взгляда код в порядке.   -  person Roman Byshko    schedule 01.12.2011
comment
Код выглядит нормально. А ваш вопрос?   -  person Piotr Zierhoffer    schedule 01.12.2011
comment
Извините, я как-то забыл изложить свою проблему. Исправлено сейчас   -  person Michael Schilling    schedule 01.12.2011
comment
@MichaelSchilling: Код, который вы показали, похоже, не содержит ошибки. Я думаю, вам нужно опубликовать полную программу, которая должна быть как можно более краткой, но при этом отображать вашу проблему. (Кроме того, вы можете ограничить этот вопрос только одной проблемой или другой. Проблема с вашей программой с двусвязным списком может оказаться совершенно не связанной с проблемой с вашей программой с односвязным списком, и в этом случае это должны быть отдельные вопросы, иначе они могут оказаться совершенно одинаковыми, и в этом случае вам все равно нужно будет спросить только об одном.)   -  person ruakh    schedule 01.12.2011

Ответы (2)


arrow_upward
3
arrow_downward

Мне нравится ваша логика двусвязного списка. Меня беспокоит только то, что если dCurrent - единственный элемент в списке, то это:

if (dCurrent == dHead){
    dHead = dCurrent->next;
    dHead->prev = NULL;
}

скорее всего, попытается сослаться на нулевой указатель. (Это зависит от того, как вы разрабатываете свой список. Но в типичном дизайне, если dCurrent является единственным узлом, тогда dCurrent->next будет NULL.)

Ваша логика односвязных списков мне тоже кажется прекрасной абстрактно, учитывая предположение, что "sPrev = sCurrent-> prev"; но я не понимаю, как это предположение может быть правильным. Если это односвязный список, тогда sCurrent не имеет указатель prev.

person ruakh    schedule 30.11.2011
comment
о sPrev заботятся в цикле for, просто чтобы избежать длинных объяснений - person Michael Schilling; 01.12.2011

arrow_upward
0
arrow_downward

Единственные проблемы, которые я вижу, - это то, что ваш код не будет работать должным образом в сценариях, когда голова или хвост обновляются до NULL.

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

dHead->prev = NULL;

вот так

if (dHead != NULL) {
  dHead->prev = NULL;
}

Один из способов «обойти» такое количество условных выражений - это присвоить элемент NIL (а не тип).

NIL - это «узел», который заменяет NULL. Он представляет собой «часть списка данных, не относящуюся к данным», поэтому его следующее значение - ВСЕГДА NIL (циклическая ссылка), а предыдущее - ВСЕГДА NIL (циклическая ссылка). В таких случаях вы гарантируете, что NIL никогда не будет доступен за пределами списка, и что head-> prev == NIL и tail-> next == NIL. Таким образом вы сможете избежать множества операторов типа if (tail != null) { ... }.

При такой конструкции пустой список - это тот, где head == NIL && tail == NIL. Это значительно сокращает количество операторов if (something == null), но у вас все еще есть один оператор if для рассмотрения, когда head равен NIL (после удаления чего-то) вам нужно установить tail для NIL для согласованности.

person Edwin Buck    schedule 30.11.2011