Удаление случайного узла из списков как по отдельности, так и в двойной связи

Question

Мне трудно придумывать логику для удаления некоторого узла как из двойного, так и в одиночном связанном списке. Я посмотрел в Интернете с помощью, но я не смог найти простой пример этого. Вот что у меня есть:

---

Вдвойне связанное удаление. 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;
}

---

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

Answer 1

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

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

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

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

Answer 2

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

По сути, если вы удалите единственный узел, Dhead укажет на NULL, поэтому вам нужно поставить «охранников» вокруг последующих утверждений, таких как

dHead->prev = NULL;

вот так

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

Один из способов «обойти», имея так много условий, - это назначить элемент нуля (не тип).

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

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