尝试在给定节点之前删除

Question

我有下面的两个函数，我可以让 removeAfter 函数正常工作，但是当尝试实现 removeBefore 函数时，链表根本没有改变。我错过了什么吗？我已经进行了必要的更改，但仍然得到相同的结果：removeBefore 不会对列表输出任何更改。

// remove the node after the node p
void DoublyLinkedList::removeAfter(DListNode &p){
if (isEmpty()){
throw EmptyDLinkedListException("Empty Doubly Linked List");
}
DListNode *to_delete = &p;
to_delete = to_delete->next;
if (to_delete != NULL){
if(to_delete->next != NULL){
to_delete->prev->next = to_delete->next;
}
if(to_delete->prev != NULL){
to_delete->next->prev = &p;
}
if (to_delete == &trailer) {
trailer = *to_delete->prev;
}

}
if (to_delete == NULL){
throw EmptyDLinkedListException("Cannot delete a null pointer");
}
delete to_delete;
}
// remove the node before the node p
void DoublyLinkedList::removeBefore(DListNode &p){
/* Complete this function */
if (isEmpty()){
throw EmptyDLinkedListException("Empty Doubly Linked List");
}
DListNode *to_delete = &p;
to_delete = to_delete->prev;
if (to_delete != NULL){
if (to_delete->next != NULL) {
to_delete->next->prev = to_delete->prev;
}
if (to_delete->prev != NULL) {
to_delete->prev->next = to_delete->next;
}
if (to_delete == &header) {
header = *to_delete->next;
}
}
if (to_delete == NULL){
throw EmptyDLinkedListException("Cannot delete a null pointer");
}
delete to_delete;
}

Answer 1

代码中存在错误。

首先，链表是指针列表，因此不习惯通过引用传递节点。您确实应该通过指针传递它们。

removeAfter()不考虑p.next在输入时可能为 NULL 的可能性(当p是列表中的最后一个节点时(。 而且在删除to_delete本身之前，它没有正确更新to_delete的兄弟姐妹。 它应该看起来像这样：

void DoublyLinkedList::removeAfter(DListNode *p)
{
DListNode *to_delete = p->next; //Get to the node after p that is to be deleted
if (to_delete != NULL)
{
if (to_delete->next != NULL) {
to_delete->next->prev = to_delete->prev;
}
if (to_delete->prev != NULL) {
to_delete->prev->next = to_delete->next;
}

// update the tail pointer if to_delete is the tail node...
if (trailer == to_delete) {
trailer = to_delete->prev;
}
delete to_delete;
}
}

removeBefore()正在犯类似的错误。 它不考虑p.prev在输入时可能为 NULL 的可能性(当p是列表中的第一个节点时(，甚至不考虑它可能是列表的头节点的可能性。 它应该看起来像这样：

void DoublyLinkedList::removeBefore(DListNode *p)
{
DListNode *to_delete = p->prev; //Get to the node before p that is to be deleted
if (to_delete != NULL)
{
if (to_delete->next != NULL) {
to_delete->next->prev = to_delete->prev;
}
if (to_delete->prev != NULL) {
to_delete->prev->next = to_delete->next;
// update the head pointer if to_delete is the head node...
if (header == to_delete) {
header = to_delete->next;
}
delete to_delete;
}
}

话虽如此，通过集中化逻辑会更好地实现，例如：

void DoublyLinkedList::remove(DListNode *p)
{
if (p = NULL) return;
if (p->next != NULL) {
p->next->prev = p->prev;
}
if (p->prev != NULL) {
p->prev->next = p->next;
}
if (header == p) {
header = p->next;
}

if (trailer == p) {
trailer = p->prev;
}
delete p;
}
void DoublyLinkedList::removeAfter(DListNode *p)
{
remove(p->next);
}
void DoublyLinkedList::removeBefore(DListNode *p)
{
remove(p->prev);
}

话虽如此，一旦你理解了双链表的工作原理，你应该扔掉所有这些代码，改用 STLstd::list类，这是一个标准的双链表实现。