Garbage value in pop_back, Doubly Linked List in C++

user_13064645 0
Viewed 273

In the following code, I implemented the doubly linked list. I am getting the output as 56 2 3 4 0 instead of 56 2 3 4. However, if I remove lt.erase(5); lt.push_back(46); then I get the correct output. I first thought that erase() have some bugs but by individually testing every function they seem fine to me. However, in this combination, I am getting an extra 0. 

#include <iostream>
using namespace std;

template <class T>
class LinkedList {
private:
    T data;
    LinkedList *prev, *next, *head, *tail;
public:
    LinkedList() : next(nullptr), head(nullptr), tail(nullptr), prev(nullptr){}
    LinkedList* get_node(T);
    void push_back(T);
    void insert(int, T);
    void pop_bak();
    void erase(int);
    void print();
};

template <typename T>
LinkedList<T>* LinkedList<T>:: get_node(T element) {
    auto* new_node = new LinkedList;
    new_node -> data = element;
    new_node -> prev = nullptr;
    new_node ->next = nullptr;
    return new_node;
}

template <typename T>
void LinkedList<T>:: push_back(T element) {
    static LinkedList *temp;
    if(head == nullptr) {
        head = get_node(element);
        tail = head;
        temp = head;
    } else {
        LinkedList *node = get_node(element);
        tail->next = node;
        tail = node;
        tail->prev = temp;
        temp = temp->next;
    }
}

template <typename T>
void LinkedList<T>:: insert(int position, T element) {
    LinkedList *node = get_node(element);
    if(position == 1){
        head->prev = node;
        node->next = head;
        head = node;
    } else {
        LinkedList *start = head;
        int it = 1;
        while (it < position - 1) {
            start = start->next;
            ++it;
        }
        node->next = start->next;
        node->prev = start;
        start->next = node;
    }
}

template <typename T>
void LinkedList<T>:: pop_bak() {
    LinkedList *temp;
    temp = tail;
    tail = tail->prev;
    tail->next = nullptr;
    delete temp;
}

template <typename T>
void LinkedList<T>:: erase(int position) {
    LinkedList *temp;
    if(position == 1){
        temp = head;
        head = head ->next;
        delete temp;
    } else {
        LinkedList *start = head;
        int it = 1;
        while (it < position - 1) {
            start = start->next;
            ++it;
        }
        if(start->next == tail) {
            temp = tail;
            tail = tail ->prev;
            tail->next = nullptr;
            delete temp;
        } else {
            temp = start -> next;
            start ->next = start ->next->next;
            delete temp;
        }
    }
}

template <typename T>
void LinkedList<T>:: print() {
    LinkedList *start = head;
    while(start != tail->next) {
        cout << start->data << " ";
        start = start->next;
    }
}

int main() {
    LinkedList<int> lt;
    lt.push_back(2);
    lt.push_back(3);
    lt.push_back(4);
    lt.push_back(5);
    lt.insert(1, 56);
    lt.erase(5); // Remove this
    lt.push_back(46); // And this and it works perfectly. Where is the bug?
    lt.pop_bak();
    lt.print();
}
doubly-linked-list data-structures linked-list c++
2 Answers

Solution

static LinkedList *temp; in push_back seems like a lazy hack. It's not needed and your code get's even shorter without this:

template <typename T>
void LinkedList<T>::push_back(T element) {
    if (head == nullptr) {
        head = get_node(element);
        tail = head;
    }
    else {
        LinkedList* node = get_node(element);
        tail->next = node;
        node->prev = tail;
        tail = node;
    }
}

But that's just the error I found for this specific problem. Zan Lynx is probably right, there may be more bugs.

Explanation

You get undefined behaviour because you access deleted memory. The bug or design failure is the static LinkedList *temp; in push_back. Note that this temp will always point to the last pushed element. But at some point you delete the last element! So let's take it step by step:

After lt.push_back(5); your list looks like this:

                         temp (from push_back)
                         |
56 <-> 2 <-> 3 <-> 4 <-> 5 -> nullptr
|                        |
head                     tail

Now erase deletes the node with value 5. But temp still points to the memory that was freed1, so you get:

                        temp (from push_back)
                        |
56 <-> 2 <-> 3 <-> 4    5 [freed]
|                  |
head               tail

After the next line lt.push_back(46); things go crazy. You have the following code (simplyfied):

void LinkedList<T>::push_back(T element) {
    static LinkedList* temp;
    if (head == nullptr) {...}
    else {
        LinkedList* node = get_node(element);
        tail->next = node;                   
        tail = node;                         
        tail->prev = temp; // prev->temp is now pointing to freed memory
        temp = temp->next; // dereferencing an invalid pointer -> undefined behaviour
    }
}

This results in:

                                          temp (from push_back)
         5 [deleted] <-                   |
56 <-> 2 <-> 3 <-> 4 -> 46  -> nullptr    ????  
|                       |
head                    tail

Then everything goes to hell in handbasket with lt.pop_bak();:

void LinkedList<T>::pop_bak() {
    LinkedList* temp;
    temp = tail;
    tail = tail->prev;    // tail->prev is an invalid pointer, now tail is too
    tail->next = nullptr; // dereferencing invalid pointer (again)
    delete temp;
}

                        temp (from pop_bak)                 
                        |                                   
56 <-> 2 <-> 3 <-> 4 -> 46 [deleted] -> nullptr     5 [deleted] -> nullptr
|                                                   |
head                                                tail

As you see your list got completely cut up and you got two pointers that point to freed memory (e.g. memory you don't own that contains garbage data). Just because you saved a pointer in static LinkedList *temp; in push_back.

1Though in C++ you use delete and not the C-function free, I refer to "freed memory" because it's clearer in my opinion. The memory is still there, it just doesn't belong to your program any more

user_51059490

Write a function to test the validity of your list. After every operation call this function. If the list is not valid, call abort() to break into your debugger. The last operation is the buggy one.

For one thing, just looking at your code I am pretty sure you aren't keeping your double links correctly. I see you adjusting next links but never the prev links.

Zan_Lynx_134220
Related