CODEWITHSUNDEEP
c++linked-liststack
Martian
Martian

Reputation: 225

Pointer being freed was not allocated (while implementing stack as a linked list)

Here's my stack:

template <class Type>
struct Node {
    Type value;
    Node* next;
    Node(Type n_value)
        : value(n_value), next(nullptr)
    { }
    static Node<Type>* Add(Node<Type>* head, const Type value) {
        if (!head) { head = new Node<Type>(value); }
        else { head->next = Add (head->next, value); }
        return head;
    }
    static void Remove(Node<Type>* head) {
        if (head->next) { Remove(head->next); }
        else { delete head; }
    }
    static void Empty(Node<Type>* head) {
        if (head->next) { Empty(head->next); }
        delete head;
    }
    static void Display(const Node<Type>* head) {
        std::cout << "\nBEGINNING\n";
        std::function<void(const Node<Type>*)> DisplayElements = [&] (const Node<Type>* head) {
            if (head) {
                std::cout << head->value << std::endl;
                if (head->next) { DisplayElements(head->next); }
            }
        };
        DisplayElements(head);
        std::cout << "\nEND\n";
    }
};

With following code:

auto beg = Node<int>::Add(nullptr, 0);
for (int i = 0; i < 10; i++) { Node<int>::Add(beg, i); }
Node<int>::Display(beg);
Node<int>::Empty(beg);

Everything is okay:

BEGINNING
0
0
1
2
3
4
5
6
7
8
9
END
Program ended with exit code: 0

But when I try to remove something:

auto beg = Node<int>::Add(nullptr, 0);
for (int i = 0; i < 10; i++) { Node<int>::Add(beg, i); }
Node<int>::Remove(beg);
Node<int>::Remove(beg);
Node<int>::Display(beg);
Node<int>::Empty(beg);
return 0;

I get Pointer being freed was not allocated on delete head; in Remove. Why? It's absolutely the same as Empty (which erases whole list), except it deletes only last node. Empty works fine.

Empty is needed to delete whole list (so that we don't get memory leaks), and Remove is to remove last element.

Upvotes: 0

Views: 62

Answers (1)

2785528
2785528

Reputation: 5566

I am unable to reproduce your results, so instead of an answer, I am providing a nudge on how you might proceed.

I changed the parameter of DisplayElements to 'lhead' (for local head), because the 'head' declaration shadow's the one in the outer scope. You also have some other shadows ... so I recommend you add -Wshadow to your compiler settings.

I also added to your Display() function some diagnostic hex output.

  static void Display(const Node<Type>* head)
  {
     std::cout << "\nBEGINNING\n";

     std::function<void(const Node<Type>*)> DisplayElements =
        [&] (const Node<Type>* lhead)
           {
              if (lhead)
              {  //           vvvvvvvvvvvv--diagnostic only
                 std::cout << hex << lhead << "  " << dec
                           << lhead->m_value << std::endl;
                 if (lhead->m_next)
                 {
                    DisplayElements(lhead->m_next);
                 }
              }
           };

     DisplayElements(head);
     std::cout << "\nEND\n";
  }

And in addition ... I changed the following. By avoiding the Empty() and the other couple of lines, the first display will more closely match the second:

        auto beg = Node<int>::Add(nullptr, 0);
        {
           for (int i = 0; i < 10; i++) { Node<int>::Add(beg, i); }
           Node<int>::Display(beg);
//         Node<int>::Empty(beg);
        }

        {
//           auto beg = Node<int>::Add(nullptr, 0);
//           for (int i = 0; i < 10; i++) { Node<int>::Add(beg, i); }
           Node<int>::Remove(beg);
           Node<int>::Remove(beg);
           Node<int>::Display(beg);
           Node<int>::Empty(beg);
        }

Now consider connecting the debugger and setting a break point to inspect what "Remove()" is doing.

Don't be shy about adding more diagnostic cout's.

What I notice is:

a) that the last lines of output are an infinite loop.

b) outputs for values 1..8 are identical to the first,

c) the output for value 9 is missing ... and I suppose should be ... but something about that last Node (perhaps the one with 8?) must be confused.

Upvotes: 1

Related Questions