Удаление заднего элемента в связанном списке

Это не дубликат вопроса с похожим названием. Это связано с ООП, вызовами new и delete.

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

Вот мой код:

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

И вот мои определения классов:

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();
};

Anddddd ..... это проблема, я получаю спам с сообщениями об ошибках, подобными этому, от 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) 

Я опубликую остальные ошибки, если это поможет, но мне не хочется нажимать пробел 4 раза на 50 строках, если мне это не нужно. Кто-нибудь знает, что это может быть? Что я делаю неправильно?

ОБНОВЛЕНИЕ ----------------------- Я отредактировал код следующим образом:

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--;
    }
}

Теперь я получаю больше недопустимых чтений ошибок размера 8/4 и недопустимых ошибок бесплатного/удаления

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

и это:

==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)

Вот тестовый код, который я использую:

    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();

Это происходит, когда последний элемент удаляется из списка с помощью delete_back().

ОБНОВИТЬ-------------------------

Проблема заключалась в том, что если end->next равно null, то цикл while никогда не будет выполняться, prev_end никогда не будет инициализирован. Опубликован ответ с реализованными исправлениями.


person Riptyde4    schedule 11.10.2013    source источник
comment
Немного не по теме, но..... вы можете скопировать и вставить их через четыре пробела вместо того, чтобы вводить их по отдельности ;)   -  person Paddyd    schedule 11.10.2013


Ответы (6)


Когда у вас есть список, содержащий как минимум 2 узла, и вы delete последний. Предыдущий все еще имеет ссылку на последний (которого больше не существует), что приводит к неопределенному поведению к тому времени, когда ваш print пытается разыменовать недопустимый (висячий) указатель. Вместо:

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

ты должен сделать:

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;
}
person LihO    schedule 11.10.2013
comment
Итак, создайте еще один временный указатель, чтобы отслеживать узел перед последним, чтобы я мог установить его равным нулю. Итак, вы говорите, что недопустимые ошибки чтения возникают из-за наличия указателей, которые ни на что не указывают? - person Riptyde4; 11.10.2013
comment
@Riptyde4: Да. Попробуйте применить это изменение и посмотрите, жалуется ли по-прежнему valgrind. - person LihO; 11.10.2013
comment
Работает отлично. Спасибо! - person Riptyde4; 11.10.2013
comment
Похоже, я был на самом деле неправ, отредактировал вопрос, у меня все еще есть проблема - person Riptyde4; 13.10.2013
comment
Как можно в третьей строке второго блока установить для заголовка значение NULL, если оно уже удалено? - person Sarah Sepanski; 03.08.2017

Не забудьте обновить 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;
    }

Также, если вы очистили список, установите для заголовка значение NULL.

person villekulla    schedule 11.10.2013
comment
На самом деле я использовал этот код вместо верхнего, поскольку он был ближе к тому, как я его уже закодировал. Спасибо! - person Riptyde4; 12.10.2013
comment
Как я могу проверить, пуст ли список, кроме проверки того, является ли голова нулевой? Кроме того, я отредактировал свой вопрос... кажется, больше проблем - person Riptyde4; 13.10.2013

вы не устанавливаете новый конечный узел равным нулю.

Например:

А->В->С->НОЛЬ

Когда вы удаляете C , B next является оборванным указателем

Итак, в функции удаления вам нужно перейти к предпоследнему узлу и установить его рядом с NULL.

В приведенном выше примере после удаления C список должен выглядеть так

A->B->NULL вместо A->B->(висит)

Таким образом, вы можете удалить B в следующей операции delete_back.

Вы можете сделать что-то вроде ниже

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--;
  }
  }
person Ravi    schedule 11.10.2013
comment
ой, я не видел два предыдущих ответа - person Ravi; 12.10.2013

Исправлены все проблемы.

Код:

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--;
    }
}
person Riptyde4    schedule 13.10.2013
comment
Это точно такой же код, который я опубликовал вчера, с той лишь разницей: вы уменьшаете size в конце... - person LihO; 13.10.2013
comment
Да, в основном, я пропустил предложение else, и это вызывало ошибку. глупая ошибка. Спасибо. - person Riptyde4; 16.10.2013

вот так должно работать

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");
 }
} 
person mohammed    schedule 23.10.2015

Самый простой код для удаления в конце:

void DeleteAtLast(){
    node *temp=head;
    while(temp->next->next!=NULL){
        temp=temp->next;
    }
    temp-next=NULL;
}
person Usama Azad    schedule 06.12.2016
comment
Избегайте ответов, содержащих только код. Пожалуйста, отредактируйте свой ответ, чтобы включить пояснения к вашему коду. Вы можете прочитать это об ответах, содержащих только код. - person Donald Duck; 06.12.2016