Удалить узел в списке одиночных ссылок - PullRequest
Новая
       13

Удалить узел в списке одиночных ссылок

9 голосов
/ 25 декабря 2009

Как удалить узел в списке одиночных ссылок, указав только один указатель на удаляемый узел?

[Начальный и конечный указатели неизвестны, доступная информация - указатель на узел, который следует удалить]

Ответы [ 3 ]

17 голосов
/ 25 декабря 2009

Вы можете удалить узел, не получая предыдущий узел, имитируя следующий узел и удаляя его вместо: 

void delete(Node *n) {
  if (!is_sentinel(n->next)) {
    n->content = n->next->content;
    Node *next = n->next;
    n->next = n->next->next;
    free(next);
  } else {
    n->content = NULL;
    free(n->next);
    n->next = NULL;
  }
}

Как видите, вам нужно будет действовать специально для последнего элемента. Я использую специальный узел в качестве сторожевого узла, чтобы отметить окончание, которое имеет content и next be NULL.

ОБНОВЛЕНИЕ: строки Node *next = n->next; n->next = n->next->next в основном перетасовывают содержимое узла и освобождают узел: Изображение, на которое вы получаете ссылку на узел B, которое будет удалено в: 

   A           / To be deleted
  next   --->  B
              next  --->    C
                           next ---> *sentinel*

Первый шаг - n->content = n->next->content: скопировать содержимое следующего узла в узел, который нужно «удалить»: 

   A           / To be deleted
  next   --->  C
              next  --->    C
                           next ---> *sentinel*

Затем измените next баллов: 

   A           / To be deleted
  next   --->  C       /----------------
              next  ---|    C          |
                           next ---> *sentinel*

Фактически свободен следующий элемент, попадающий в окончательный вариант: 

   A           / To be deleted
  next   --->  C
              next  --->    *sentinel*
16 голосов
/ 25 декабря 2009

Не возможно.

Есть хаки, имитирующие удаление.

Но ни один из них фактически не удалит узел, на который указывает указатель.

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

Вы можете найти обсуждение SO здесь .

4 голосов
/ 25 декабря 2009

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

...