Linked list is not displaying properly-CodePudding

For my assignment, I have to create a singly headed singly linked list of characters using a stack. I have created a class called Stack which contains "StackNodes" as private members. The first issue, as described in the title, is that in my testDriver.cpp file, I am trying to display the elements of the list but when I run it I have an infinite loop of "a-a-a-a-a-...". I have 4 files that I am manipulating to run my test driver: makefile, stack.cpp, stack.h, and testDriver.cpp. I think the issue is in my stack.cpp code.

Another issue is that when I modified my display() function to print the head of the list, I get an error saying "free() double free detected in tcache 2," and I'm not sure if that's an indication of an issue with my destructor. Any help or ideas on what's going on would be greatly appreciated.

Here's my stack.cpp file:

#include <iostream>
#include "stack.h"
using namespace std;

// Description: Default Constructor
// Postcondition: Stack is empty.

Stack::Stack()
{
    head = new StackNode;
    head->next = NULL;

    // Exit if memory allocation fails
    if (head == NULL) {
        cout << "Failed to allocate memory for a new stack.\n";
        EXIT_FAILURE;
    }
}

// Description: Destructor
// Postcondition: All nodes are deleted.

Stack::~Stack()
{
    while (head != NULL) {
        StackNode* temp = head;
        head = head->next;
        delete temp;
    }

    // Free pointer
    delete head;
}

// Description: Inserts "newElement" at the top of the Stack.
// Postcondition: "newElement" is the new topmost element; other elements unchanged.

void Stack::push(char newElement) {
    StackNode* temp;
    temp = head;
    head->data = newElement;
    head->next = temp;
}

// Description: Removes and returns element at the top of the Stack.
// Precondition: Stack non empty.
// Postcondition: Topmost element is removed and returned; 
//                other elements unchanged.

char Stack::pop() {
    char topElement = head->data;
    StackNode* temp = head;
    temp->next = NULL;
    head = head->next;

    // Pop the element
    delete temp;
    temp = NULL;
    return topElement;
}

// Description: Returns the topmost element of the stack.
// Precondition: Stack non empty.
// Postcondition: Elements unchanged (const).

char Stack::peek() const {
    char topElement = head->data;
    return topElement;
}

// Description: Returns true if and only if Stack is empty.
// Postcondition: Elements unchanged (const).

bool Stack::isEmpty() const {
    if (head == NULL) {
        return true;
    }
    return false;
}

// Description: Display list
// Precondition: Stack non empty

void Stack::display() const {
    StackNode * temp = head;
    while (temp != NULL) {
        cout << temp->data << " - ";
        temp = temp->next;
    }
}

Here's my stack.h file:

#pragma once

class Stack {

  private:

    // Description:  Nodes for a singly-linked list.
    class StackNode {
      public:
        char data;
        StackNode * next;
    };
        
    // Description:  head = ptr to the first StackNode (NULL if empty)
    StackNode* head;

  public:

    // Description: Constructor
    // Postcondition: Stack is empty.
    Stack();

    // Description: Destructor
    // Postcondition: All nodes are deleted.
    ~Stack();

    // Description: Inserts "newElement" at the top of the Stack.
    // Postcondition: "newElement" is the new topmost element; other elements unchanged.
    void push(char newElement);

    // Description: Removes and returns element at the top of the Stack.
    // Precondition: Stack non empty.
    // Postcondition: Topmost element is removed and returned; 
    //                other elements unchanged.
    char pop();

    // Description: Returns the topmost element of the stack.
    // Precondition: Stack non empty.
    // Postcondition: Elements unchanged (const).
    char peek() const;

    // Description: Returns true if and only if Stack is empty.
    // Postcondition: Elements unchanged (const).
    bool isEmpty() const;

    // Description: Display list
    // Precondition: Stack non empty
    void display() const;
};

And here's my test driver:

#include <iostream>
#include "stack.h"
using namespace std;

int main() {

    // Create a stack object
    Stack s1 = Stack();

    // Push some elements into stack list
    s1.push('c');
    s1.push('b');
    s1.push('a');

    // Print the list
    s1.display();

    return 0;
}

CodePudding user response：

The crux of the problem is actually in your Stack() constructor and the push() method. By creating an empty StackNode in your c'tor, and you are creating a StackNode with a garbage data field, and setting up the problem that exists with push() at the same time. It further means that the head value, which should be NULL at this juncture, is occupied, meaning that isEmpty() would be false even though you haven't pushed anything on to the stack yet.

For consistency's sake, you should initialize head to NULL in your c'tor, and test for an empty head in the functions which would fail if head is NULL.

Stack::Stack(): head(NULL)
{
}

As if happens, though, push() isn't one of these functions. In your current version, you aren't actually creating a new StackNode, only an uninitialized pointer to one. Furthermore, you are creating a recursive link by copying head to temp, and then copying temp ( == head) to temp->next. The solution is to initialize temp to a new StackNode, setting temp->next to head, and then copying temp to head. Something like so:

void Stack::push(char newElement) {
    StackNode* temp = new StackNode;
    temp->data = newElement;
    temp->next = head;
    head = temp;
}

This only solves the immediate problem, but it should get you past your current hurdle. As for the double free() issue, my solution posted above should do well:

Stack::~Stack()
{
    while (!this->isEmpty()) {
        this->pop();
    }
}

BTW, you can simplify the isEmpty() code a bit, while you are at it:

bool Stack::isEmpty() const {
    return (head == NULL);
}

As an aside: be careful in using #pragma once, as it is non-standard and only really supported by Visual C . With other compilers, you would need to use an include guard using the #ifndef/#define/#endif combination, and for the sake of portability this is generally preferred for any program not specifically for Windows.