C++ 删除链表中的back元素

Deleting the back element in a linked list

提问by Riptyde4

This is not a duplicate of the question with a similar name, This involves OOP and new and delete calls.

这不是具有相似名称的问题的重复，这涉及 OOP 以及 new 和 delete 调用。

I'm trying to write a function that will iterate to the back of my linked list and then delete the allocated memory in the heap of the last node.

我正在尝试编写一个函数，该函数将迭代到我的链表的后面，然后删除最后一个节点的堆中分配的内存。

Here is my code:

这是我的代码：

void LinkedList::delete_back(){
    if(head != NULL){
            ListNode *end = head;
            while(end->next != NULL)
                    end = end->next;
            delete end;
    }
    size--;
}

And here is my class definitions:

这是我的类定义：

class ListNode{

    public:
            Item data;
            ListNode *next;
};
class LinkedList{

    private:
            ListNode *head;
            int size;

    public:
            LinkedList();
            ~LinkedList(); 
            bool empty();
            void insert_front(Item i);
            void insert_back(Item i);
            void delete_front();
            void delete_back();
            void print();
};

Annddddd.....this is the problem, I get spammed with error messages like this from valgrind, some stating invalid read of size 4, other stating invalid read of size 8:

Annddddd.....这就是问题所在，我收到了来自 valgrind 的类似这样的错误消息的垃圾邮件，一些说明大小为 4 的无效读取，其他说明大小为 8 的无效读取：

==4385== Invalid read of size 4
==4385==    at 0x400CAA: LinkedList::print() (in /home/jon/jball2_lab06/linkedlist)
==4385==    by 0x400EDD: main (in /home/jon/jball2_lab06/linkedlist)
==4385==  Address 0x5a04f30 is 0 bytes inside a block of size 16 free'd
==4385==    at 0x4C2A4BC: operator delete(void*) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==4385==    by 0x400C5E: LinkedList::delete_back() (in /home/jon/jball2_lab06/linkedlist)
==4385==    by 0x400E99: main (in /home/jon/jball2_lab06/linkedlist) 

I'll post the rest of the errors if that helps but I don't feel like hitting space 4 times on 50 lines unless I need to. Does anyone know what this could be? What am I doing wrong?

如果有帮助，我会发布其余的错误，但除非我需要，否则我不想在 50 行上打 4 次空格。有谁知道这可能是什么？我究竟做错了什么？

UPDATE----------------------- I've edited the code to be:

更新----------------------- 我已将代码编辑为：

void LinkedList::delete_back(){
    if(head != NULL){
            ListNode *end = head;
            ListNode *prev_end;
            while(end->next != NULL){
                    prev_end = end;
                    end = end->next;
            }
            prev_end->next = NULL;
            if(end != NULL) delete end;
            size--;
    }
}

I'm now getting more invalid read of size 8/4 errors and invalid free/delete errors

我现在收到了更多无效读取大小为 8/4 的错误和无效的自由/删除错误

==5294== Invalid free() / delete / delete[] / realloc()
==5294==    at 0x4C2A4BC: operator delete(void*) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)

and this:

和这个：

==5294== Use of uninitialised value of size 8
==5294==    at 0x400C3D: LinkedList::delete_back() (in /home/jon/jball2_lab06/linkedlist)
==5294==    by 0x400EEC: main (in /home/jon/jball2_lab06/linkedlist)

Here is the test code im using:

这是我使用的测试代码：

    for(Item i = 50; i < 100; i++){
            ll.insert_back(i);
            cout << "Inserted [" << i << "] in back.\n";
    }
    ll.print();
    for(int i = 0; i < 50; i++)
            ll.delete_back();
    cout << "Removed 50 elements from the back.\n";
    ll.print();

This occurs when the last element is removed from the list using delete_back()

当使用 delete_back() 从列表中删除最后一个元素时会发生这种情况

UPDATE-------------------------

更新 - - - - - - - - - - - - -

The problem was that if end->next is null than the while loop will never execute, prev_end will never be initalized. Posted answer with fixes implemented.

问题是如果 end->next 为空，那么 while 循环将永远不会执行， prev_end 永远不会被初始化。已实施修复的已发布答案。

回答by LihO

When you have a list that contains at least 2 nodes and you deletethe last one. The previous one still has a reference to the last one (which doesn't exist anymore), which results in undefined behaviorby the time your printtries to dereference invalid (dangling) pointer. Instead of:

当您有一个包含至少 2 个节点的列表而您delete是最后一个时。前一个仍然有对最后一个（不再存在）的引用，当您尝试取消引用无效（悬空）指针时，这会导致未定义的行为print。代替：

ListNode *end = head;
while(end->next != NULL)
    end = end->next;
delete end;

you should do:

你应该做：

if (head->next == NULL) {
    delete head;
    head = NULL;
}
else {
    ListNode *nextToEnd = head;
    ListNode *end = head->next;
    while (end->next != NULL) {
        nextToEnd = end;
        end = end->next;
    }
    delete end;
    nextToEnd->next = NULL;
}

回答by Ravi

you are not setting the new end node to be null.

您没有将新的结束节点设置为空。

For eg:

例如：

A->B->C->NULL

A->B->C->NULL

When you delete C , B's next is a dangling pointer

当您删除 C 时， B 的下一个是一个悬空指针

So in the delete function you need to go to the second last node and and set its next to NULL.

因此，在删除函数中，您需要转到倒数第二个节点并将其 next 设置为 NULL。

In the above example after deleting C , the list should look like

在删除 C 后的上述示例中，列表应如下所示

A->B->NULL instead of A->B->(dangling)

A->B->NULL 而不是 A->B->(dangling)

So you can delete B in the next delete_back operation.

所以你可以在接下来的 delete_back 操作中删除 B。

You can do something like below

您可以执行以下操作

void LinkedList::delete_back(){
if(head != NULL){
        ListNode *end = head;
        //This if block is for when only one element is left
        if(end->next == NULL)
         { delete end;
           end = NULL;
         }
        else
        while(end!= NULL)
        { 
               if(end->next) /// reach the second last element
                if(end->next->next==NULL)
                 {
                  delete end->next; //delete the last element
                  end->next=NULL; // set the next of second last element to NULL
                 }
               end=end->next;
        } 
  size--;
  }
  }

回答by villekulla

Don't forget to update nextof your new last element.

不要忘记更新next新的最后一个元素。

void LinkedList::delete_back(){
    if(head != NULL){
            ListNode *end = head;
            ListNode *prev_end;
            while(end->next != NULL)
            {
                 prev_end = end;
                 end = end->next;
            }
            prev_end->next = 0;
            delete end;
    }

Also if you emptied the list, set head to NULL.

此外，如果您清空了列表，请将 head 设置为 NULL。

回答by Riptyde4

Fixed all issues.

修复了所有问题。

Code:

代码：

void LinkedList::delete_back(){
    if(head != NULL){
            ListNode *end = head;
            if(end->next != NULL){
                    ListNode *prev_end;
                    while(end->next != NULL){
                            prev_end = end;
                            end = end->next;
                    }
                    prev_end->next = NULL;
                    delete end;
            }
            else {
                    delete head;
                    head = NULL;
            }
            size--;
    }
}

回答by mohammed

like this should work

像这样应该工作

void del_rear()

{
  struct node *end, *last

 if (head->next != NULL) {

   *end=head;

while(end->next!=null){
*last=end;
 end=end->next;
  }
    free(end);
    last->next=null;
   }     
 else
   {

    pf("list is empty\n");
 }
} 

回答by Usama Azad

The easiest code to delete at end is:

最后删除最简单的代码是：

void DeleteAtLast(){
    node *temp=head;
    while(temp->next->next!=NULL){
        temp=temp->next;
    }
    temp-next=NULL;
}