Hello programmers!

I am working on a program that checks if a user's input is a palindrome (in this case, the input is a string).
I am using a custom class template "stack", that is a constrained version of my custom class "List", which is a linked list class template. Each item in the LinkedList is of a class template ListNode, and it has a pointer to the next item.

How my program works to check if a string it a palindrome:
It gets input from a user, removes spaces, removes punctionation marks, makes all letters lowercase, and then creates two stacks, which have the letters being pushed on it in reverse order for one, and in forward order for the other.

Then, I start popping the stacks and comparing for the equality between the two.
The main() program works just fine.

However, when the destructor for the stacks are called, which then calls the base class destructor, I get the following:

Palindrome testing with stacks(36206,0x7fff7d151310) malloc: *** error for object 0x100200090: pointer being freed was not allocated
*** set a breakpoint in malloc_error_break to debug

Could anyone suggest for me what to do regarding this message?
I never worked with malloc, so I do not know what to do. I was doing some debuggin in my xCode (for mac) debugger, and the destructor for List is called three times, even though I created two stacks (and therefore means that it has to be called two times).

The reason why I am catching this problem now is that I modified the stack and list class to behave as my demands of them required, so this is going on.

I would like for your attention to be directed to the Stack class and to the List class's destructor.

Here's my code:

//  main.cpp
//  A program that tests a string to see if it's a palindrome

#include <iostream>
#include <algorithm>
#include <string>
#include <ctype.h>
#include "Stack.h"
using namespace std;

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
string getString(const string& msg)
{
    //gets a desired string input from user
    string input;
    cout << msg << flush;
    cin >> input;
    return input;
}

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

bool hasNum(const string& toTest)
{
    //tests to see if toTest contains at least one character that is a num
    for (auto iter=toTest.cbegin();iter != toTest.cend();++iter)
    {
        if (isnumber(*iter))
        {
            return true;
        }
    }
    return false;
}

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
template<typename T>
bool areEqual(Stack<T> stackOne,Stack<T> stackTwo)
{
    T tempStackOne;
    T tempStackTwo;

    while (!(stackOne.isStackEmpty()))
    {
        stackOne.pop(tempStackOne);
        stackTwo.pop(tempStackTwo);

        if (tempStackOne != tempStackTwo)
            return false;
    }

    return true;
}

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

int main()
{
    string input="";

    //get a string from user
    cout << "This is a program that tests if an inputted string is a palindrome\n" << endl;

    do
    {
       input=getString("Enter a phrase (without any numbers in it) in to be tested: ");
       if (hasNum(input))
       {
           cerr << "Input can not have any numeric characters." << endl;
           cout << "Please try again." << endl;
       }
    }
    while(hasNum(input));


    //process string by removing all punctuation marks and spaces
    input.erase(remove_if(input.begin(),input.end(),::ispunct),input.end());

    //process by which all spaces are removed
    input.erase(remove_if(input.begin(),input.end(),::isspace),input.end());

    //convert all letters to lowercase
    transform(input.begin(), input.end(), input.begin(), ::tolower);

    //after this is done, create two stacks, in order, and reverse
    Stack<char> forwardStack;
    Stack<char> backwardStack;

    //iterate backwards, and add the chars in order to forwardStack
    for (auto iter=input.crbegin(); iter!=input.crend();++iter)
    {
        forwardStack.push(*iter);
    }
    for (auto iter=input.cbegin();iter!=input.cend();++iter)
    {
        backwardStack.push(*iter);
    }

    //check to see if the stacks are equal
    cout << "\n\nThe input " << (areEqual(forwardStack, backwardStack)? "is":"is not") << " a palindrome.\n\n" << endl;
}

My Stack class:

//  Stack.h
//  Stack class-template definition using private inheritance of class List

#ifndef Stack_h
#define Stack_h

#include "List.h"

template<typename STACKTYPE>
class Stack : private List<STACKTYPE>
{
public:


    //push calls the List function insertAtFront
    void push(const STACKTYPE &data)
    {
        this->insertAtFront(data);
    }

    //pop calls the List function removeFromFront
    bool pop(STACKTYPE &data)
    {
        return this->removeFromFront(data);
    }

    //isStackEmpty calls List function isEmpty
    bool isStackEmpty() const
    {
        return (this->isEmpty());
    }

    //printStack calls the List function print
    void printStack() const
    {
        this->print();
    }
};

#endif

My List class (PAY ATTENTION TO DESTRUCTOR):

//  List.h
//  List class-template definition

#ifndef List_h
#define List_h

#include <iostream>
#include "ListNode.h"


template <typename NODETYPE>
class List
{
public:

    //default constructor
    List(): firstPtr(nullptr),lastPtr(nullptr)
    {}

    //destructor
    ~List()
    {
        emptyList();
        std::cout << "All nodes destroyed\n\n";
    }

    //insert node at front of List
    void insertAtFront(const NODETYPE& value)
    {
        ListNode<NODETYPE> *newPtr=getNewNode(value);   //new node

        if (isEmpty())                                  //List is empty
            firstPtr=lastPtr=newPtr;                    //new List has only one node
        else
        {
            //List is not empty
            newPtr->nextPtr=firstPtr;
            firstPtr=newPtr;
        }
    }


    //insert node at back of List
    void insertAtBack(const NODETYPE& value)
    {
        ListNode<NODETYPE> *newPtr=getNewNode(value);   //new node

        if (isEmpty())
            firstPtr=lastPtr=newPtr;                    //new List has only one node
        else
        {
            //list is not empty
            lastPtr->nextPtr = newPtr;                  //update previous last node
            lastPtr = newPtr;
        }
    }

    //delete node from front of list [return boolean to signify if operation is successful]
    bool removeFromFront(NODETYPE& value)
    {
        if (isEmpty())      //List is empty
            return false;   //delete unucessful
        else
        {
            ListNode<NODETYPE> *tempPtr=firstPtr;       //hold item to delete

            if (firstPtr==lastPtr)                      //no nodes remain after removal
                firstPtr=lastPtr=nullptr;               //set all ptr's to nullptr
            else                                        //some nodes remain after removal
                firstPtr=firstPtr->nextPtr;             //set firstPtr to nextPtr

            //return data being removed via the reference variable value
            value=tempPtr->data;                        //return the data being removed
            delete tempPtr;                             //reclaim previous front node
            return true;
        }
    }

    //delete node from back of list [return boolean to signify if operation is successful
    bool removeFromBack(NODETYPE& value)
    {
        if (isEmpty())      //List is empty
            return false;   //delete unsuccessful

        else
        {
            ListNode<NODETYPE> *tempPtr=lastPtr;         //hold item to delete

            if (firstPtr == lastPtr)                     //no nodes remain after removal
                firstPtr=lastPtr=nullptr;                //set all ptr's to nullptr
            else
            {
                ListNode<NODETYPE>* currentPtr = firstPtr;

                //locate second-to-last element
                while (currentPtr->nextPtr != lastPtr)
                    currentPtr=currentPtr->nextPtr;      //move to next node

                lastPtr=currentPtr;                      //remove last node
                currentPtr->nextPtr = nullptr;           //this is now the last node
            }

            value = tempPtr->data;                       //return value from old last node
            delete tempPtr;                              //reclaim former last node
            return true;
        }
    }

    //returns true if List is empty
    bool isEmpty() const
    {
        return firstPtr==nullptr;
    }

    //display contents of List
    void print() const
    {
        if (isEmpty())  //List is empty
        {
            std::cout << "The list is empty.\n\n";
            return;
        }

        //continue by printing the list's contents
        ListNode<NODETYPE> *currentPtr=firstPtr;

        std::cout << "The list is: ";
        while (currentPtr != nullptr)       //get element data
        {
            std::cout << currentPtr->data << ' ';
            currentPtr = currentPtr->nextPtr;
        }
        std::cout << "\n" << std::endl;
    }

    List<NODETYPE> operator=(const List<NODETYPE>& toAssign)
    {
        //check to see if the list is the same, to avoid assigning to self
        if (this != &toAssign)
        {
            //empty the list being assigned to, and then assign toAssign's contents to this List
            emptyList();

            //iterate over toAssign's contents, and assign the contents to list
            List<NODETYPE> *currentPtr=toAssign.firstPtr;
            while (currentPtr != nullptr)
            {
                this->insertAtFront(currentPtr);
                currentPtr=currentPtr->nextPtr;     //get toAssign's next content
            }
        }

        return *this;
    }

    NODETYPE& operator[](int subscript)
    {
        if ( subscript < 0 || subscript >= size())
            throw std::out_of_range("Subscript out of range");

        //subscript is in valid range -
        //return a modifiable lvalue
        int count=0;
        ListNode<NODETYPE> *currentPtr=firstPtr;

        while (count != subscript)
        {
            ++count;
            currentPtr=currentPtr->nextPtr;
        }

        return (currentPtr->data);
    }

    NODETYPE operator[](int subscript) const//returns non-modifiable rvalue
    {
        if (subscript < 0 || subscript >= size())
            throw std::out_of_range("Subscript out of range");

        //subscript is in valid range -
        //return a non-modifiable lvalue
        int count=0;
        ListNode<NODETYPE> *currentPtr=firstPtr;

        while (count != subscript)
        {
            ++count;
            currentPtr=currentPtr->nextPtr;
        }

        return (currentPtr->data);
    }
    unsigned size()                         //returns list size
    {
        if (isEmpty())                      //List is empty
            return 0;                       //size is 0
        else
        {
            ListNode<NODETYPE> *currentPtr=firstPtr;
            int sizeCount=0;
            while (currentPtr != nullptr)
            {
                ++sizeCount;
                currentPtr=currentPtr->nextPtr;
            }

            return sizeCount;
        }
    }

    void emptyList()    //PROBLEMATIC FUNCTION IF THE DECISION IN THE IF STATEMENT EVALUATES TO TRUE
    {
        if (!isEmpty()) //List is not empty
        {
            std::cout << "Destroying nodes ...\n";

            ListNode<NODETYPE> *currentPtr=firstPtr;
            ListNode<NODETYPE> *tempPtr=nullptr;

            while (currentPtr != nullptr) //delete remaining nodes
            {
                tempPtr=currentPtr;
                std::cout << tempPtr->data << '\n';
                currentPtr = currentPtr->nextPtr;
                delete tempPtr;
            }
        }
    }


private:
    ListNode<NODETYPE> *firstPtr;           //pointer to first node
    ListNode<NODETYPE> *lastPtr;            //pointer to last node

    //utility function to allocate new node
    ListNode<NODETYPE> *getNewNode(const NODETYPE& value)
    {
        return new ListNode<NODETYPE>(value);
    }

};
#endif

And then my ListNode.h:

//  ListNode class-template definition

#ifndef ListNode_h
#define ListNode_h

//forward declaration of class List is required to announce that class
//List exists so it can be used in the friend declaration at line 20
template<typename NODETYPE> class List;

template<typename NODETYPE>
class ListNode
{
    friend class List<NODETYPE>;    //make List a friend

public:

    //constructor
    explicit ListNode(const NODETYPE &info): data(info), nextPtr(nullptr)
    {}

    //return all data in node
    NODETYPE getData() const
    {
        return data;
    }

private:
    NODETYPE data;                  //data
    ListNode<NODETYPE> *nextPtr;    //pointer to next node in list
};


#endif

I do not want people wasting their precious time on my code, but I am asking for some guidance in debugging, escpecially with the malloc message.

Here's an example of how the program runs leading up to the message:

This is a program that tests if an inputted string is a palindrome

Enter a phrase (without any numbers in it) in to be tested: abcba


The input is a palindrome.


All nodes destroyed

All nodes destroyed

Destroying nodes ...

Palindrome testing with stacks(36206,0x7fff7d151310) malloc: *** error for object 0x100200090: pointer being freed was not allocated
*** set a breakpoint in malloc_error_break to debug
(lldb) 

Many thanks!

Just a quick scan and I noticed this:

(What is wrong here? Hint what is the tail node value after adding first node to list? What should it be?)

//insert node at front of List
void insertAtFront(const NODETYPE& value)
{
    ListNode<NODETYPE> *newPtr=getNewNode(value);   //new node

    if (isEmpty())                                  //List is empty
        firstPtr=lastPtr=newPtr;                    //new List has only one node
    else
    {
        //List is not empty
        newPtr->nextPtr=firstPtr;
        firstPtr=newPtr;
    }
}


//insert node at back of List
void insertAtBack(const NODETYPE& value)
{
    ListNode<NODETYPE> *newPtr=getNewNode(value);   //new node

    if (isEmpty())
        firstPtr=lastPtr=newPtr;                    //new List has only one node
    else
    {
        //list is not empty
        lastPtr->nextPtr = newPtr;                  //update previous last node
        lastPtr = newPtr;
    }
}

Edited 2 Years Ago by David W

I changed it, and it still does not work. Any suggestions. I modified the insertAtFront, and the insertAtBack functions.

//  List class-template definition

#ifndef List_h
#define List_h

#include <iostream>
#include "ListNode.h"


template <typename NODETYPE>
class List
{
public:

    //default constructor
    List(): firstPtr(nullptr),lastPtr(nullptr)
    {}

    //destructor
    ~List()
    {
        emptyList();
        std::cout << "All nodes destroyed\n\n";
    }

    //insert node at front of List
    void insertAtFront(const NODETYPE& value)
    {
        ListNode<NODETYPE> *newPtr=getNewNode(value);   //new node

        if (isEmpty())                                  //List is empty
        {
            firstPtr=newPtr;
            lastPtr=nullptr;
            newPtr->nextPtr=lastPtr;
        }
        else
        {
            //List is not empty
            newPtr->nextPtr=firstPtr;
            firstPtr=newPtr;
        }
        newPtr->nextPtr=nullptr;
    }


    //insert node at back of List
    void insertAtBack(const NODETYPE& value)
    {
        ListNode<NODETYPE> *newPtr=getNewNode(value);   //new node

        if (isEmpty())
        {
            //new List has only one node

            firstPtr=newPtr;
            lastPtr=nullptr;
            newPtr->nextPtr=lastPtr;
        }
        else
        {
            //list is not empty
            lastPtr->nextPtr = newPtr;                  //update previous last node
            lastPtr = newPtr;
        }
        newPtr->nextPtr=nullptr;
    }

    //delete node from front of list [return boolean to signify if operation is successful]
    bool removeFromFront(NODETYPE& value)
    {
        if (isEmpty())      //List is empty
            return false;   //delete unucessful
        else
        {
            ListNode<NODETYPE> *tempPtr=firstPtr;       //hold item to delete

            if (firstPtr==lastPtr)                      //no nodes remain after removal
                firstPtr=lastPtr=nullptr;               //set all ptr's to nullptr
            else                                        //some nodes remain after removal
                firstPtr=firstPtr->nextPtr;             //set firstPtr to nextPtr

            //return data being removed via the reference variable value
            value=tempPtr->data;                        //return the data being removed
            delete tempPtr;                             //reclaim previous front node
            return true;
        }
    }

    //delete node from back of list [return boolean to signify if operation is successful
    bool removeFromBack(NODETYPE& value)
    {
        if (isEmpty())      //List is empty
            return false;   //delete unsuccessful

        else
        {
            ListNode<NODETYPE> *tempPtr=lastPtr;         //hold item to delete

            if (firstPtr == lastPtr)                     //no nodes remain after removal
                firstPtr=lastPtr=nullptr;                //set all ptr's to nullptr
            else
            {
                ListNode<NODETYPE>* currentPtr = firstPtr;

                //locate second-to-last element
                while (currentPtr->nextPtr != lastPtr)
                    currentPtr=currentPtr->nextPtr;      //move to next node

                lastPtr=currentPtr;                      //remove last node
                currentPtr->nextPtr = nullptr;           //this is now the last node
            }

            value = tempPtr->data;                       //return value from old last node
            delete tempPtr;                              //reclaim former last node
            return true;
        }
    }

    //returns true if List is empty
    bool isEmpty() const
    {
        return firstPtr==nullptr;
    }

    //display contents of List
    void print() const
    {
        if (isEmpty())  //List is empty
        {
            std::cout << "The list is empty.\n\n";
            return;
        }

        //continue by printing the list's contents
        ListNode<NODETYPE> *currentPtr=firstPtr;

        std::cout << "The list is: ";
        while (currentPtr != nullptr)       //get element data
        {
            std::cout << currentPtr->data << ' ';
            currentPtr = currentPtr->nextPtr;
        }
        std::cout << "\n" << std::endl;
    }

    List<NODETYPE> operator=(const List<NODETYPE>& toAssign)
    {
        //check to see if the list is the same, to avoid assigning to self
        if (this != &toAssign)
        {
            //empty the list being assigned to, and then assign toAssign's contents to this List
            emptyList();

            //iterate over toAssign's contents, and assign the contents to list
            List<NODETYPE> *currentPtr=toAssign.firstPtr;
            while (currentPtr != nullptr)
            {
                this->insertAtFront(currentPtr);
                currentPtr=currentPtr->nextPtr;     //get toAssign's next content
            }
        }

        return *this;
    }

    NODETYPE& operator[](int subscript)
    {
        if ( subscript < 0 || subscript >= size())
            throw std::out_of_range("Subscript out of range");

        //subscript is in valid range -
        //return a modifiable lvalue
        int count=0;
        ListNode<NODETYPE> *currentPtr=firstPtr;

        while (count != subscript)
        {
            ++count;
            currentPtr=currentPtr->nextPtr;
        }

        return (currentPtr->data);
    }

    NODETYPE operator[](int subscript) const//returns non-modifiable rvalue
    {
        if (subscript < 0 || subscript >= size())
            throw std::out_of_range("Subscript out of range");

        //subscript is in valid range -
        //return a non-modifiable lvalue
        int count=0;
        ListNode<NODETYPE> *currentPtr=firstPtr;

        while (count != subscript)
        {
            ++count;
            currentPtr=currentPtr->nextPtr;
        }

        return (currentPtr->data);
    }
    unsigned size()                         //returns list size
    {
        if (isEmpty())                      //List is empty
            return 0;                       //size is 0
        else
        {
            ListNode<NODETYPE> *currentPtr=firstPtr;
            int sizeCount=0;
            while (currentPtr != nullptr)
            {
                ++sizeCount;
                currentPtr=currentPtr->nextPtr;
            }

            return sizeCount;
        }
    }

    void emptyList()    //PROBLEMATIC FUNCTION IF THE DECISION IN THE IF STATEMENT EVALUATES TO TRUE
    {
        if (!isEmpty()) //List is not empty
        {
            std::cout << "Destroying nodes ...\n";

            ListNode<NODETYPE> *currentPtr=firstPtr;
            ListNode<NODETYPE> *tempPtr=nullptr;

            while (currentPtr != nullptr) //delete remaining nodes
            {
                tempPtr=currentPtr;
                std::cout << tempPtr->data << '\n';
                currentPtr = currentPtr->nextPtr;
                delete tempPtr;
            }
        }
    }


private:
    ListNode<NODETYPE> *firstPtr;           //pointer to first node
    ListNode<NODETYPE> *lastPtr;            //pointer to last node

    //utility function to allocate new node
    ListNode<NODETYPE> *getNewNode(const NODETYPE& value)
    {
        return new ListNode<NODETYPE>(value);
    }

};
#endif

Edited 2 Years Ago by nathan.pavlovsky: wrong code

Look at my previous message, as it is edited.

Edited 2 Years Ago by nathan.pavlovsky: Accidentally sent wrong file

Not fixed yet ...

(Note: there are other problems besides these 2 ...)

What is wrong here?
(See changes/added comments to your code.)

//insert node at front of List
void insertAtFront(const NODETYPE& value)
{
    ListNode<NODETYPE> *newPtr=getNewNode(value);

    if (isEmpty()) //List is empty
    {
        firstPtr = newPtr;
        //lastPtr = nullptr; // NOT what you want //

        lastPtr = ?? //hint: how many nodes now exist ?


        //newPtr->nextPtr = lastPtr; // really? NO line needed here anyway //
    }
    else // List is not empty
    {
        newPtr->nextPtr = firstPtr; // GOOD
        firstPtr = newPtr; // GOOD
    }

    //newPtr->nextPtr=nullptr; // NO, this undoes link //
}

And here ...

//insert node at back of List
void insertAtBack(const NODETYPE& value)
{
    ListNode<NODETYPE> *newPtr=getNewNode(value);

    if (isEmpty())
    {
        firstPtr=newPtr;
        // lastPtr=nullptr; // SAME problem as above

        lastPtr = ?? ;// hint as above

        // newPtr->nextPtr=lastPtr; // NO, and do not need any line here anyways //
    }
    else //list is not empty
    {
        lastPtr->nextPtr = newPtr;                  
        lastPtr = newPtr;
    }
    // newPtr->nextPtr=nullptr; // redundant // 
}

So just (further) fix up this ONE line in both methods:
lastPtr = ?? //
and you will be ok with these two methods.

Hint:
I would add a private member to your list to track the size ...

size_t len;
// then public method size is so easy :)
size_t size() const { return len; }

Edited 2 Years Ago by David W

I still get the malloc error message....

Here's what I have:

//  List class-template definition

#ifndef List_h
#define List_h

#include <iostream>
#include "ListNode.h"


template <typename NODETYPE>
class List
{
public:

    //default constructor
    List(): firstPtr(nullptr),lastPtr(nullptr)
    {}

    //destructor
    ~List()
    {
        emptyList();
        std::cout << "All nodes destroyed\n\n";
    }

    //insert node at front of List
    void insertAtFront(const NODETYPE& value)
    {
        ListNode<NODETYPE> *newPtr=getNewNode(value);   //new node

        if (isEmpty())                                  //List is empty
        {
            firstPtr=newPtr;
            lastPtr=newPtr;
        }
        else
        {
            //List is not empty
            newPtr->nextPtr=firstPtr;
            firstPtr=newPtr;
        }
    }


    //insert node at back of List
    void insertAtBack(const NODETYPE& value)
    {
        ListNode<NODETYPE> *newPtr=getNewNode(value);   //new node

        if (isEmpty())
        {
            //new List has only one node
            firstPtr=newPtr;
            lastPtr=newPtr;
        }
        else
        {
            //list is not empty
            lastPtr->nextPtr = newPtr;                  //update previous last node
            lastPtr = newPtr;
        }
    }

    //delete node from front of list [return boolean to signify if operation is successful]
    bool removeFromFront(NODETYPE& value)
    {
        if (isEmpty())      //List is empty
            return false;   //delete unucessful
        else
        {
            ListNode<NODETYPE> *tempPtr=firstPtr;       //hold item to delete

            if (firstPtr==lastPtr)                      //no nodes remain after removal
                firstPtr=lastPtr=nullptr;               //set all ptr's to nullptr
            else                                        //some nodes remain after removal
                firstPtr=firstPtr->nextPtr;             //set firstPtr to nextPtr

            //return data being removed via the reference variable value
            value=tempPtr->data;                        //return the data being removed
            delete tempPtr;                             //reclaim previous front node
            return true;
        }
    }

    //delete node from back of list [return boolean to signify if operation is successful
    bool removeFromBack(NODETYPE& value)
    {
        if (isEmpty())      //List is empty
            return false;   //delete unsuccessful

        else
        {
            ListNode<NODETYPE> *tempPtr=lastPtr;         //hold item to delete

            if (firstPtr == lastPtr)                     //no nodes remain after removal
                firstPtr=lastPtr=nullptr;                //set all ptr's to nullptr
            else
            {
                ListNode<NODETYPE>* currentPtr = firstPtr;

                //locate second-to-last element
                while (currentPtr->nextPtr != lastPtr)
                    currentPtr=currentPtr->nextPtr;      //move to next node

                lastPtr=currentPtr;                      //remove last node
                currentPtr->nextPtr = nullptr;           //this is now the last node
            }

            value = tempPtr->data;                       //return value from old last node
            delete tempPtr;                              //reclaim former last node
            return true;
        }
    }

    //returns true if List is empty
    bool isEmpty() const
    {
        return firstPtr==nullptr;
    }

    //display contents of List
    void print() const
    {
        if (isEmpty())  //List is empty
        {
            std::cout << "The list is empty.\n\n";
            return;
        }

        //continue by printing the list's contents
        ListNode<NODETYPE> *currentPtr=firstPtr;

        std::cout << "The list is: ";
        while (currentPtr != nullptr)       //get element data
        {
            std::cout << currentPtr->data << ' ';
            currentPtr = currentPtr->nextPtr;
        }
        std::cout << "\n" << std::endl;
    }

    List<NODETYPE> operator=(const List<NODETYPE>& toAssign)
    {
        //check to see if the list is the same, to avoid assigning to self
        if (this != &toAssign)
        {
            //empty the list being assigned to, and then assign toAssign's contents to this List
            emptyList();

            //iterate over toAssign's contents, and assign the contents to list
            List<NODETYPE> *currentPtr=toAssign.firstPtr;
            while (currentPtr != nullptr)
            {
                this->insertAtFront(currentPtr);
                currentPtr=currentPtr->nextPtr;     //get toAssign's next content
            }
        }

        return *this;
    }

    NODETYPE& operator[](int subscript)
    {
        if ( subscript < 0 || subscript >= size())
            throw std::out_of_range("Subscript out of range");

        //subscript is in valid range -
        //return a modifiable lvalue
        int count=0;
        ListNode<NODETYPE> *currentPtr=firstPtr;

        while (count != subscript)
        {
            ++count;
            currentPtr=currentPtr->nextPtr;
        }

        return (currentPtr->data);
    }

    NODETYPE operator[](int subscript) const//returns non-modifiable rvalue
    {
        if (subscript < 0 || subscript >= size())
            throw std::out_of_range("Subscript out of range");

        //subscript is in valid range -
        //return a non-modifiable lvalue
        int count=0;
        ListNode<NODETYPE> *currentPtr=firstPtr;

        while (count != subscript)
        {
            ++count;
            currentPtr=currentPtr->nextPtr;
        }

        return (currentPtr->data);
    }
    unsigned size()                         //returns list size
    {
        if (isEmpty())                      //List is empty
            return 0;                       //size is 0
        else
        {
            ListNode<NODETYPE> *currentPtr=firstPtr;
            int sizeCount=0;
            while (currentPtr != nullptr)
            {
                ++sizeCount;
                currentPtr=currentPtr->nextPtr;
            }

            return sizeCount;
        }
    }

    void emptyList()    //PROBLEMATIC FUNCTION IF THE DECISION IN THE IF STATEMENT EVALUATES TO TRUE
    {
        if (!isEmpty()) //List is not empty
        {
            std::cout << "Destroying nodes ...\n";

            ListNode<NODETYPE> *currentPtr=firstPtr;
            ListNode<NODETYPE> *tempPtr=nullptr;

            while (currentPtr != nullptr) //delete remaining nodes
            {
                tempPtr=currentPtr;
                std::cout << tempPtr->data << '\n';
                currentPtr = currentPtr->nextPtr;
                delete tempPtr;
            }
        }
    }


private:
    ListNode<NODETYPE> *firstPtr;           //pointer to first node
    ListNode<NODETYPE> *lastPtr;            //pointer to last node

    //utility function to allocate new node
    ListNode<NODETYPE> *getNewNode(const NODETYPE& value)
    {
        return new ListNode<NODETYPE>(value);
    }

};
#endif

I changed only insertAtFront, and insertAtBack. Could you tell me what I'm doing wrong? Thanks!

Glad to see that you fixed-up the insert at front and back methods ... that's really great.

Now ... here's how I might start out to code a SLList in C++11 ... using some of your variable names and style, but changing several method names to be more like the names used in the STL. Note the ++len when adding list elements ... or ... --len when deleting list elements ... 'as we go'.

I also added an iterator class 'nested' inside of the SLList class.

Take a look:

Firstly the file: "LISTNODE.H"

// LISTNODE.H //  // needs C++11 compiler //

#ifndef LISTNODE_H
#define LISTNODE_H

//forward declaration of class SLList is required to announce that class
template< typename NODETYPE > class SLList;

template< typename NODETYPE >
class Node
{
private:
    friend class SLList< NODETYPE >;

    NODETYPE data;
    Node< NODETYPE > *nextPtr;
public:
    // value ctor...
    Node( const NODETYPE& info ) : data(info), nextPtr(nullptr)
    {}
} ;

#endif

Then the file: "SLList.h"

// SLList.h //  // needs C++11 compiler //


#ifndef SLLIST_H
#define SLLIST_H

#include "LISTNODE.H"

#include <iostream>
#include <stdexcept>

template < typename NODETYPE >
class SLList
{
public:

    //default constructor
    explicit SLList(): firstPtr(nullptr), lastPtr(nullptr), len(0) {}

    //destructor
    ~SLList()
    {
        clear();
        std::cout << "All nodes destroyed\n";
    }

    void push_front( const NODETYPE& value )
    {
        Node< NODETYPE >* newPtr = getNewNode( value );

        // faster running code if firstly handle most likely case ...
        if( len ) 
        {
            newPtr->nextPtr = firstPtr;
            firstPtr = newPtr;
        }
        else
        {
            lastPtr = firstPtr = newPtr;
        }
        ++len;
    }

    void push_back( const NODETYPE& value )
    {
        Node< NODETYPE >* newPtr = getNewNode( value );

        if( len )
        {
            lastPtr->nextPtr = newPtr;
            lastPtr = newPtr;
        }
        else
        {
            lastPtr = firstPtr =  newPtr;
        }
        ++len;
    }


    const NODETYPE& front() const
    {
        if( !len )
            throw std::out_of_range( "Error! List is empty, "
                                     "so can NOT access front() ..." ) ;
        // else ...
        return firstPtr->data;
    }
    const NODETYPE& back() const
    {
        if( !len )
            throw std::out_of_range( "Error! List is empty, "
                                     "so can NOT access back() ..." ) ;
        return lastPtr->data;
    }


    //return boolean to signify if operation is successful
    bool pop_front()
    {
        if( len )
        {
            Node< NODETYPE >* curPtr = firstPtr;
            firstPtr = firstPtr->nextPtr;
            delete curPtr;
            --len;
            if( !len ) lastPtr = nullptr;
            return true;
        }
        // else if reach here ...
        return false;
    }

    //return boolean to signify if operation is successful
    bool pop_back()
    {
        if( len )
        {
            Node< NODETYPE >* curPtr = firstPtr,
                            * prevPtr = nullptr;
            while( curPtr->nextPtr )
            {
                prevPtr = curPtr;
                curPtr = curPtr->nextPtr;
            }

            lastPtr = prevPtr;
            if( lastPtr ) lastPtr->nextPtr = nullptr;
            else firstPtr = nullptr;
            delete curPtr;
            --len;
            //if( !len ) firstPtr = nullptr; // handled above //
        }
        // else if reach here ...
        return false;
    }

    //returns true if SLList is empty
    bool empty() const
    {
        return !len;
    }

    //display contents of SLList
    void print() const
    {
        if( empty() )   //SLList is empty
        {
            std::cout << "The list is empty.\n\n";
            return;
        }

        //continue by printing the list's contents
        Node< NODETYPE >* currentPtr = firstPtr;

        std::cout << "The list is: ";
        while( currentPtr )
        {
            std::cout << currentPtr->data << ' ';
            currentPtr = currentPtr->nextPtr;
        }
        std::cout << std::endl;
    }

    // copy ctor ...
    SLList< NODETYPE > ( const SLList< NODETYPE >& old )
    {
        firstPtr = lastPtr = nullptr;
        len = 0;
        //iterate over old ... and add copy of each to new list
        Node< NODETYPE >* curPtr = old.firstPtr;
        while( curPtr )
        {
            push_back( curPtr->data );
            curPtr = curPtr->nextPtr;
        }
    }

    // move copy ctor ...
    SLList< NODETYPE > ( const SLList< NODETYPE >&& old )
    {
        firstPtr = old.firstPtr;
        lastPtr = old.lastPtr;
        len = old.len;

        old.firstPtr = old.lastPtr = nullptr;
        old.len = 0;
    }


    // overloaded assignment ...
    SLList< NODETYPE >& operator = ( const SLList< NODETYPE >& old )
    {
        //check to see if the list is the same, to avoid assigning to self
        if( this != &old )
        {
            //first ensure the list being assigned to is empty ...
            clear();

            //iterate over old ... and add copy of each to new list
            Node< NODETYPE >* curPtr = old.firstPtr;
            while( curPtr )
            {
                push_back( curPtr->data );
                curPtr = curPtr->nextPtr;
            }
        }
        return *this;
    }

    // move overloaded assignment ...
    SLList< NODETYPE >& operator = ( const SLList< NODETYPE >&& old )
    {
        //check to see if the list is the same, to avoid assigning to self
        if( this != &old )
        {
            clear();

            firstPtr = old.firstPtr;
            lastPtr = old.lastPtr;
            len = old.len;

            old.firstPtr = old.lastPtr = nullptr;
            old.len = 0;
        }
        return *this;
    }


    // return a modifiable lvalue ...
    NODETYPE& operator [] ( size_t index )
    {
        if( index >= len )
            throw std::out_of_range( "Index out of range" ) ;

        //is in valid range ...
        size_t i = 0;
        Node< NODETYPE >* curPtr = firstPtr;

        while( i != index )
        {
            ++i;
            curPtr = curPtr->nextPtr;
        }
        return ( curPtr->data );
    }

    //returns non-modifiable rvalue
    const NODETYPE& operator [] ( size_t index ) const
    {
        if( index >= len )
            throw std::out_of_range( "Index out of range" ) ;

        //is in valid range ...
        size_t i = 0;
        Node< NODETYPE >* curPtr = firstPtr;

        while( i != index )
        {
            ++i;
            curPtr = curPtr->nextPtr;
        }
        return ( curPtr->data );
    }

    size_t size()  const
    {
        return len;
    }

    void clear()
    {
        if( len ) //SLList is not empty
        {
            std::cout << "Clearing nodes ...\n";

            Node< NODETYPE > *curPtr = firstPtr;
            Node< NODETYPE > *tmpPtr = nullptr;

            while( curPtr )
            {
                tmpPtr = curPtr->nextPtr;
                //std::cout << curPtr->data << '\n';
                delete curPtr;
                curPtr = tmpPtr;
                --len;
            }
            firstPtr = lastPtr = nullptr;
        }
    }

    class iterator
    {
    public:
        iterator& operator ++ () { ptr = ptr->nextPtr; return *this; }
        iterator& operator ++ ( int dummy ) { ptr = ptr->nextPtr; return *this; }
        bool operator !=  (const iterator& it2)  const { return  ptr != it2.ptr; }
        const NODETYPE operator * () const { return ptr->data; }
        NODETYPE& operator * () { return ptr->data; }
    private:
        Node< NODETYPE >* ptr;
    } ;

    iterator begin()
    {
        //typename SLList< NODETYPE >::iterator it; // before C++11
        SLList< NODETYPE >::iterator it; // C++11
        it.ptr = firstPtr;
        return it;
    }
    iterator end()
    {
        //typename SLList< NODETYPE >::iterator it; // before C++11
        SLList< NODETYPE >::iterator it; // C++11
        it.ptr = nullptr;;
        return it;
    }

private:
    Node< NODETYPE >* firstPtr;
    Node< NODETYPE >* lastPtr;
    size_t len;

    Node< NODETYPE >* getNewNode( const NODETYPE& value )
    {
        return new Node< NODETYPE >( value );
    }
} ;

#endif

Lastly, a little test file: "test_SLList.h.cpp"

// test_SLList.h.cpp //  // needs C++11 compiler //

#include "SLList.h"

void tests_1()
{
    using std::cout; using std::cin; using std::endl;

    SLList< int > myLst;

    // get some test data into the list ...
    myLst.push_back( 3 );
    myLst.push_back( 4 );
    myLst.push_back( 5 );

    myLst.push_front( 2 );
    myLst.push_front( 1 );
    myLst.push_front( 0 );

    //SLList< int > myLst2 = myLst;
    auto myLst2 = myLst;

    cout << "Testing using iterator to print... \n";
    cout << "Note: each element has value++ when done.\n";
/*
    SLList< int >::iterator it;
    for( it = myLst.begin(); it != myLst.end(); ++ it )
         cout << (*it)++ << endl;
*/
    for( auto &e : myLst2 ) cout << e++ << ' ';

    cout << "\nmyLst2.print()... \n";
    myLst2.print();

    cout << endl;
    while( myLst2.size() > 3 )
    {
        cout << "size = " << myLst2.size()
             << ", front = " << myLst2.front()
             << ", back = " << myLst2.back()
             << ", pop_front() ...\n";
        myLst2.pop_front();
    }

    cout << endl;
    while( !myLst2.empty() )
    {
        cout << "size = " << myLst2.size()
             << ", front = " << myLst2.front()
             << ", back = " << myLst2.back()
             << ", pop_back() ...\n";
        myLst2.pop_back();
    }

    cout << "\nmyLst2.print() ...\n";
    myLst2.print();
}

int main()
{
    tests_1();

    std::cout << "\nPress ''Enter' to continue/exit ... ";
    std::cin.get();
}

Edited 2 Years Ago by David W

Sir, you don't understand... this is not "fixed" as you said, because I still get the malloc error message.

I do not want to retype everything I just did in order to fit the suggested convention without having mine working first. Again, here's the code for that modified file:

//  List class-template definition

#ifndef List_h
#define List_h

#include <iostream>
#include "ListNode.h"


template <typename NODETYPE>
class List
{
public:

    //default constructor
    List(): firstPtr(nullptr),lastPtr(nullptr)
    {}

    //destructor
    ~List()
    {
        emptyList();
        std::cout << "All nodes destroyed\n\n";
    }

    //insert node at front of List
    void insertAtFront(const NODETYPE& value)
    {
        ListNode<NODETYPE> *newPtr=getNewNode(value);   //new node

        if (isEmpty())                                  //List is empty
        {
            firstPtr=newPtr;
            lastPtr=newPtr;
        }
        else
        {
            //List is not empty
            newPtr->nextPtr=firstPtr;
            firstPtr=newPtr;
        }
    }


    //insert node at back of List
    void insertAtBack(const NODETYPE& value)
    {
        ListNode<NODETYPE> *newPtr=getNewNode(value);   //new node

        if (isEmpty())
        {
            //new List has only one node
            firstPtr=newPtr;
            lastPtr=newPtr;
        }
        else
        {
            //list is not empty
            lastPtr->nextPtr = newPtr;                  //update previous last node
            lastPtr = newPtr;
        }
    }

    //delete node from front of list [return boolean to signify if operation is successful]
    bool removeFromFront(NODETYPE& value)
    {
        if (isEmpty())      //List is empty
            return false;   //delete unucessful
        else
        {
            ListNode<NODETYPE> *tempPtr=firstPtr;       //hold item to delete

            if (firstPtr==lastPtr)                      //no nodes remain after removal
                firstPtr=lastPtr=nullptr;               //set all ptr's to nullptr
            else                                        //some nodes remain after removal
                firstPtr=firstPtr->nextPtr;             //set firstPtr to nextPtr

            //return data being removed via the reference variable value
            value=tempPtr->data;                        //return the data being removed
            delete tempPtr;                             //reclaim previous front node
            return true;
        }
    }

    //delete node from back of list [return boolean to signify if operation is successful
    bool removeFromBack(NODETYPE& value)
    {
        if (isEmpty())      //List is empty
            return false;   //delete unsuccessful

        else
        {
            ListNode<NODETYPE> *tempPtr=lastPtr;         //hold item to delete

            if (firstPtr == lastPtr)                     //no nodes remain after removal
                firstPtr=lastPtr=nullptr;                //set all ptr's to nullptr
            else
            {
                ListNode<NODETYPE>* currentPtr = firstPtr;

                //locate second-to-last element
                while (currentPtr->nextPtr != lastPtr)
                    currentPtr=currentPtr->nextPtr;      //move to next node

                lastPtr=currentPtr;                      //remove last node
                currentPtr->nextPtr = nullptr;           //this is now the last node
            }

            value = tempPtr->data;                       //return value from old last node
            delete tempPtr;                              //reclaim former last node
            return true;
        }
    }

    //returns true if List is empty
    bool isEmpty() const
    {
        return firstPtr==nullptr;
    }

    //display contents of List
    void print() const
    {
        if (isEmpty())  //List is empty
        {
            std::cout << "The list is empty.\n\n";
            return;
        }

        //continue by printing the list's contents
        ListNode<NODETYPE> *currentPtr=firstPtr;

        std::cout << "The list is: ";
        while (currentPtr != nullptr)       //get element data
        {
            std::cout << currentPtr->data << ' ';
            currentPtr = currentPtr->nextPtr;
        }
        std::cout << "\n" << std::endl;
    }

    List<NODETYPE> operator=(const List<NODETYPE>& toAssign)
    {
        //check to see if the list is the same, to avoid assigning to self
        if (this != &toAssign)
        {
            //empty the list being assigned to, and then assign toAssign's contents to this List
            emptyList();

            //iterate over toAssign's contents, and assign the contents to list
            List<NODETYPE> *currentPtr=toAssign.firstPtr;
            while (currentPtr != nullptr)
            {
                this->insertAtFront(currentPtr);
                currentPtr=currentPtr->nextPtr;     //get toAssign's next content
            }
        }

        return *this;
    }

    NODETYPE& operator[](int subscript)
    {
        if ( subscript < 0 || subscript >= size())
            throw std::out_of_range("Subscript out of range");

        //subscript is in valid range -
        //return a modifiable lvalue
        int count=0;
        ListNode<NODETYPE> *currentPtr=firstPtr;

        while (count != subscript)
        {
            ++count;
            currentPtr=currentPtr->nextPtr;
        }

        return (currentPtr->data);
    }

    NODETYPE operator[](int subscript) const//returns non-modifiable rvalue
    {
        if (subscript < 0 || subscript >= size())
            throw std::out_of_range("Subscript out of range");

        //subscript is in valid range -
        //return a non-modifiable lvalue
        int count=0;
        ListNode<NODETYPE> *currentPtr=firstPtr;

        while (count != subscript)
        {
            ++count;
            currentPtr=currentPtr->nextPtr;
        }

        return (currentPtr->data);
    }
    unsigned size()                         //returns list size
    {
        if (isEmpty())                      //List is empty
            return 0;                       //size is 0
        else
        {
            ListNode<NODETYPE> *currentPtr=firstPtr;
            int sizeCount=0;
            while (currentPtr != nullptr)
            {
                ++sizeCount;
                currentPtr=currentPtr->nextPtr;
            }

            return sizeCount;
        }
    }

    void emptyList()    //PROBLEMATIC FUNCTION IF THE DECISION IN THE IF STATEMENT EVALUATES TO TRUE
    {
        if (!isEmpty()) //List is not empty
        {
            std::cout << "Destroying nodes ...\n";

            ListNode<NODETYPE> *currentPtr=firstPtr;
            ListNode<NODETYPE> *tempPtr=nullptr;

            while (currentPtr != nullptr) //delete remaining nodes
            {
                tempPtr=currentPtr;
                std::cout << tempPtr->data << '\n';
                currentPtr = currentPtr->nextPtr;
                delete tempPtr;
            }
        }
    }


private:
    ListNode<NODETYPE> *firstPtr;           //pointer to first node
    ListNode<NODETYPE> *lastPtr;            //pointer to last node

    //utility function to allocate new node
    ListNode<NODETYPE> *getNewNode(const NODETYPE& value)
    {
        return new ListNode<NODETYPE>(value);
    }

};
#endif

In addition, I am reposting the code of all my other files so you could see what's going on.

//  ListNode class-template definition

#ifndef ListNode_h
#define ListNode_h

//forward declaration of class List is required to announce that class
//List exists so it can be used in the friend declaration at line 20
template<typename NODETYPE> class List;

template<typename NODETYPE>
class ListNode
{
    friend class List<NODETYPE>;    //make List a friend

public:

    //constructor
    explicit ListNode(const NODETYPE &info): data(info), nextPtr(nullptr)
    {}

    //return all data in node
    NODETYPE getData() const
    {
        return data;
    }

private:
    NODETYPE data;                  //data
    ListNode<NODETYPE> *nextPtr;    //pointer to next node in list
};


#endif

And:

//  Stack class-template definition using private inheritance of class List

#ifndef Stack_h
#define Stack_h

#include "List.h"

template<typename STACKTYPE>
class Stack : private List<STACKTYPE>
{
public:


    //push calls the List function insertAtFront
    void push(const STACKTYPE &data)
    {
        this->insertAtFront(data);
    }

    //pop calls the List function removeFromFront
    bool pop(STACKTYPE &data)
    {
        return this->removeFromFront(data);
    }

    //isStackEmpty calls List function isEmpty
    bool isStackEmpty() const
    {
        return (this->isEmpty());
    }

    //printStack calls the List function print
    void printStack() const
    {
        this->print();
    }
};

#endif

And the main.cpp file:

//  A program that tests a string to see if it's a palindrome

#include <iostream>
#include <algorithm>
#include <string>
#include <ctype.h>
#include "Stack.h"
using namespace std;

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
string getString(const string& msg)
{
    //gets a desired string input from user
    string input;
    cout << msg << flush;
    cin >> input;
    return input;
}

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

bool hasNum(const string& toTest)
{
    //tests to see if toTest contains at least one character that is a num
    for (auto iter=toTest.cbegin();iter != toTest.cend();++iter)
    {
        if (isnumber(*iter))
        {
            return true;
        }
    }
    return false;
}

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
template<typename T>
bool areEqual(Stack<T> stackOne,Stack<T> stackTwo)
{
    T tempStackOne;
    T tempStackTwo;

    while (!(stackOne.isStackEmpty()))
    {
        stackOne.pop(tempStackOne);
        stackTwo.pop(tempStackTwo);

        if (tempStackOne != tempStackTwo)
            return false;
    }

    return true;
}

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

int main()
{
    string input="";

    //get a string from user
    cout << "This is a program that tests if an inputted string is a palindrome\n" << endl;

    do
    {
       input=getString("Enter a phrase (without any numbers in it) in to be tested: ");
       if (hasNum(input))
       {
           cerr << "Input can not have any numeric characters." << endl;
           cout << "Please try again." << endl;
       }
    }
    while(hasNum(input));


    //process string by removing all punctuation marks and spaces
    input.erase(remove_if(input.begin(),input.end(),::ispunct),input.end());

    //process by which all spaces are removed
    input.erase(remove_if(input.begin(),input.end(),::isspace),input.end());

    //convert all letters to lowercase
    transform(input.begin(), input.end(), input.begin(), ::tolower);

    //after this is done, create two stacks, in order, and reverse
    Stack<char> forwardStack;
    Stack<char> backwardStack;

    //iterate backwards, and add the chars in order to forwardStack
    for (auto iter=input.crbegin(); iter!=input.crend();++iter)
    {
        forwardStack.push(*iter);
    }
    for (auto iter=input.cbegin();iter!=input.cend();++iter)
    {
        backwardStack.push(*iter);
    }

    //check to see if the stacks are equal
    cout << "\n\nThe input " << (areEqual(forwardStack, backwardStack)? "is":"is not") << " a palindrome.\n\n" << endl;
}

Please test on your computer if all the code is working, because I get the following in the xCode for mac console window:

This is a program that tests if an inputted string is a palindrome

Enter a phrase (without any numbers in it) in to be tested: I saw Elba able was I


The input is a palindrome.


All nodes destroyed

All nodes destroyed

Destroying nodes ...
i
Palindrome testing with stacks(48959,0x7fff7d151310) malloc: *** error for object 0x100103bc0: pointer being freed was not allocated
*** set a breakpoint in malloc_error_break to debug
(lldb) 

Perhaps you do not 'see' my method here ... It was to GIVE you some working code examples (just at first for a SLList class) ... so that you could then compare each working method there ... to yours ... and thus to 'see' ... your several coding errors.

The methods for the push_front and push_back ACTUALLY were fixed, by your futher fix re. this common line in each method:

lastPtr = newPtr;

But, like I stated at the top, there were still several other errors in your single-linked list class.

After I posted the above example, code, I noticed a line was missing in the nested iterator class. That class should be like this:

class iterator
{
private:
    Node< NODETYPE >* ptr;
    friend class SLList< NODETYPE >; // this line was missing //
public:
    iterator& operator ++ () { ptr = ptr->nextPtr; return *this; }
    iterator& operator ++ ( int dummy ) { ptr = ptr->nextPtr; return *this; }
    bool operator !=  (const iterator& it2)  const { return  ptr != it2.ptr; }
    const NODETYPE operator * () const { return ptr->data; }
    NODETYPE& operator * () { return ptr->data; }
} ;

Firstly ...

get your SLList working and tested ok.

Create a simple test program like the example I provided that tests out all the functionality in your list class to 'prove' to yourself that each part is working correctly.

Then ... and only then, work on using that list in some other program.

(But even better, develope the other program first, by using the STL list ... this will allow you to KNOW that any errors are in your 'other program' and not the list.)

Edited 2 Years Ago by David W

For example, using the STL stack (with the STL list), this demos a 'proof of concept' ... and a way to trim your code some more ... since you are already using C++11 ...

//  testIfPalindrome.cpp //  // needs C++11 compiler //

#include <iostream>
#include <string>
#include <algorithm>
#include <cctype> // for C++ ... but Note:  C uses <ctype.h> //

#include <list>
#include <stack> // developed first with a KNOWN working stack container //

using namespace std;


// some utilities used here ...

string takeInString( const string& msg = "" )
{
    cout << msg << flush;
    string val;
    getline( cin, val );
    return val;
}
int takeInChr( const std::string& msg = "" )
{
    string reply = takeInString( msg );
    if( reply.size() )
        return reply[0];
    // else ...
    return 0;
}
bool more()
{
    if( tolower( takeInChr( "More (y/n) ? " )) == 'n' )
        return false;
    // else ...
    return true;
}
bool hasDigits( const string& toTest )
{
    for( auto e : toTest )
        if( isdigit(e) )
            return true;

    // else ... if reach here ...
    return false;
}



int main()
{
    cout << "This program tests if "
            "a string is a 'palindrome' ...\n\n";
    do
    {
        string input;
        for( ; ; )
        {
            input = takeInString( "Enter a line of text, without "
                                  "any numbers in it, to be "
                                  "tested:\n" );
            if( hasDigits( input ) )
            {
                cout << "\nInput can not have any numeric characters"
                     << ", please try again.\n\n";
            }
            else
                break;
        }

        //convert all letters to lowercase
        transform( input.begin(), input.end(), input.begin(), ::tolower );

        //after this is done, create two stacks ...
        //'forward' and 'reverse', and ...
        //use the STL list for the stack//
        stack< char, list< char > > forwardStack,
                                    backwardStack;

        // now can populate 'forward' and 'backward' stacks
        for( auto e : input ) 
            if( isalpha(e) ) forwardStack.push( e );

        for( auto it = input.rbegin(); it != input.rend(); ++ it )
            if( isalpha(*it) ) backwardStack.push( *it );

        //check to see if the stacks are equal
        cout << "\n'" << input << "' is"
             << (forwardStack == backwardStack ? "" : " not")
             << " a palindrome.\n\n";
     }
     while( more() );
}

Now ... can you see why your SLList will not work here, unless it has at least a forward iterator also defined, (and of course, an overloaded == also defined) ?

Edited 2 Years Ago by David W

And here is an 'homegrown' Stack example, revised from your example, that you can use to compare and fix up your stack class (it uses the above class SLList) :

(Note the overloaded == is supplied in the derived class, since the base class did not have it.)

// STACK.H //  // needs a C++11 compiler //

// class definition using private inheritance of class SLList //

#ifndef Stack_h
#define Stack_h

#include "SLList.h"

template< typename STACKTYPE >
class Stack : private SLList< STACKTYPE >
{
public:

    void push( const STACKTYPE& data )
    {
        this->push_front( data )  ;
    }

    const STACKTYPE& top()
    {
        return this->top();
    }

    bool pop()
    {
        return this->pop_front();
    }

    bool operator == ( Stack& other )
    {
        if( this->size() != other.size() ) return false;
        // else ...
        auto it = this->begin(), it2 = other.begin();

        while( it != this->end() )
        {
            if( *it != *it2 ) return false;
            ++it, ++it2;
        }
        // if reach here ...
        return true;
    }

    void print()
    {
        std::cout << "The stack is: ";
        for( auto it = this->begin(); it != this->end(); ++it )
             std::cout << *it << ' ';
    }
} ;
#endif

And you can see that there were only a few simple edits made to the 'test program' ... to enable the use of the 'homegrown stack' :

//  testIfPalindrome2.cpp //  // needs C++11 compiler //

#include <iostream>
#include <string>
#include <algorithm>
#include <cctype> // for C++ ... but Note:  C uses <ctype.h> //

#include "STACK.H"


using namespace std;


// some utilities used here ...

string takeInString( const string& msg = "" )
{
    cout << msg << flush;
    string val;
    getline( cin, val );
    return val;
}
int takeInChr( const std::string& msg = "" )
{
    string reply = takeInString( msg );
    if( reply.size() )
        return reply[0];
    // else ...
    return 0;
}
bool more()
{
    if( tolower( takeInChr( "More (y/n) ? " )) == 'n' )
        return false;
    // else ...
    return true;
}
bool hasDigits( const string& toTest )
{
    for( auto e : toTest )
        if( isdigit(e) )
            return true;

    // else ... if reach here ...
    return false;
}



int main()
{
    cout << "This program tests if "
            "a string is a 'palindrome' ...\n\n";
    do
    {
        string input;
        for( ; ; )
        {
            input = takeInString( "Enter a line of text, without "
                                  "any numbers in it, to be "
                                  "tested:\n" );
            if( hasDigits( input ) )
            {
                cout << "\nInput can not have any numeric characters"
                     << ", please try again.\n\n";
            }
            else
                break;
        }

        //convert all letters to lowercase
        transform( input.begin(), input.end(), input.begin(), ::tolower );

        //after this is done, create two stacks ...
        //'forward' and 'reverse', and ...
        //use the STL list for the stack//
        Stack< char > forwardStack,
                      backwardStack;

        // now can populate 'forward' and 'backward' stacks
        for( auto e : input ) 
            if( isalpha(e) ) forwardStack.push( e );

        std::cout << "Forward ...  ";
        forwardStack.print();
        std::cout << "\n\n";


        for( auto it = input.rbegin(); it != input.rend(); ++ it )
            if( isalpha(*it) ) backwardStack.push( *it );

        std::cout << "Backward ... ";
        backwardStack.print();
        std::cout << "\n\n";


        //check to see if the stacks are equal
        cout << "\n'" << input << "' is"
             << (forwardStack == backwardStack ? "" : " not")
             << " a palindrome.\n\n";
     }
     while( more() );
}

By the way, you could have very simply just formed two new appropriate strings ... and then checked if the one was equal to the other reversed ... but then you would have missed all this fun of making your own stack class derived from your own single-link-list class :)

Edited 2 Years Ago by David W

Thanks so much for the help! It worked!!!

When studying STL with my C++ How to Program book, I created the two strings as you described, and checked if they are equal to each other.
However, the book asked me to do it also with stacks.

Here's the List class as of the working state:

//  List class-template definition

#ifndef List_h
#define List_h

#include <iostream>
#include <stdexcept>
#include "ListNode.h"


template <typename NODETYPE>
class List
{
public:

    //default constructor
    explicit List(): firstPtr(nullptr),lastPtr(nullptr),len(0)
    {}

    //destructor
    ~List()
    {
        emptyList();
        std::cout << "All nodes destroyed\n\n";
    }

    //insert node at front of List
    void insertAtFront(const NODETYPE& value)
    {
        ListNode<NODETYPE> *newPtr=getNewNode(value);   //new node
        if (len)                               //List  not is empty
        {
            //List is not empty
            newPtr->nextPtr=firstPtr;
            firstPtr=newPtr;
        }
        else
        {
            firstPtr=newPtr;
            lastPtr=newPtr;
        }
        ++len;
    }


    //insert node at back of List
    void insertAtBack(const NODETYPE& value)
    {
        ListNode<NODETYPE> *newPtr=getNewNode(value);   //new node

        if (len)
        {
            //new List has only one node
            lastPtr->nextPtr=newPtr;
            lastPtr=newPtr;
        }
        else
        {
            //list is empty
            lastPtr=firstPtr=newPtr;
        }
        ++len;
    }

    const NODETYPE& front() const
    {
        if (!len)
            throw std::out_of_range("Error! List is empty, so can NOT access front() ...");
        //else...
        return firstPtr->data;
    }


    const NODETYPE& back() const
    {
        if (!len)
            throw std::out_of_range("Error! List is empty, so can NOT access back() ...");
        //else...
        return lastPtr->data;
    }
    //delete node from front of list [return boolean to signify if operation is successful]
    bool removeFromFront(NODETYPE& value)
    {
        if (len)
        {
            ListNode<NODETYPE>* curPtr=firstPtr;
            firstPtr=firstPtr->nextPtr;
            delete curPtr;
            --len;
            if (!len)
                lastPtr=nullptr;
            return true;
        }

        //else if reach here...
        return false;
    }

    //delete node from back of list [return boolean to signify if operation is successful
    bool removeFromBack(NODETYPE& value)
    {
        if (len)
        {
            ListNode<NODETYPE>* curPtr=firstPtr,*prevPtr=nullptr;

            while (curPtr->nextPtr)
            {
                prevPtr=curPtr;
                curPtr=curPtr->nextPtr;
            }

            lastPtr=prevPtr;

            if (lastPtr)
                lastPtr->nextPtr=nullptr;
            else
                firstPtr=nullptr;

            delete curPtr;
            --len;
        }

        //else if reach here...
        return false;
    }

    //returns true if List is empty
    bool isEmpty() const
    {
        return !len;
    }

    //display contents of List
    void print() const
    {
        if (isEmpty())  //List is empty
        {
            std::cout << "The list is empty.\n\n";
            return;
        }

        //continue by printing the list's contents
        ListNode<NODETYPE> *currentPtr=firstPtr;

        std::cout << "The list is: ";
        while (currentPtr != nullptr)       //get element data
        {
            std::cout << currentPtr->data << ' ';
            currentPtr = currentPtr->nextPtr;
        }
        std::cout << "\n" << std::endl;
    }

    //copy constructor
    List<NODETYPE>(const List<NODETYPE>& old)
    {
        firstPtr=lastPtr=nullptr;
        len=0;

        //iterate over old ... and add copy of each to new list
        ListNode<NODETYPE>* curPtr=old.firstPtr;
        while (curPtr)
        {
            insertAtBack(curPtr->data);
            curPtr=curPtr->nextPtr;
        }
    }

    //move copy ctor ...
    List<NODETYPE> (const List<NODETYPE>&& old)
    {
        firstPtr=old.firstPtr;
        lastPtr=old.lastPtr;
        len=old.len;

        old.firstPtr=old.lastPtr=nullptr;
        old.len=0;
    }

    //overloaded assignment
    List<NODETYPE> operator=(const List<NODETYPE>& old)
    {
        //check to see if the list is the same, to avoid assigning to self
        if (this != &old)
        {
            //first ensure list being assigned to is empty
            emptyList();

            //iterate over old, and add copy of each to new list
            ListNode<NODETYPE>* curPtr=old.firstPtr;
            while (curPtr)
            {
                insertAtBack(curPtr->data);
                curPtr=curPtr->nextPtr;
            }
        }

        return *this;
    }

    //move overloaded assignment
    List<NODETYPE>& operator=(const List<NODETYPE>&& old)
    {
        //check to see if the list is the same, to avoid ssigning to self
        if (this != &old)
        {
            emptyList();

            firstPtr=old.firstPtr;
            lastPtr=old.lastPtr;
            len=old.len;

            old.firstPtr=old.lastPtr=nullptr;
            old.len=0;
        }

        return *this;
    }

    NODETYPE& operator[](size_t index)
    {
        if ( index < 0 || index >= size())
            throw std::out_of_range("Subscript out of range");

        //index is in valid range -
        //return a modifiable lvalue
        ListNode<NODETYPE> *curPtr=firstPtr;

        for (size_t i; i != index; ++i)
        {
            curPtr=curPtr->nextPtr;
        }

        return (curPtr->data);
    }

    //returns non-modifiable rvalue
    NODETYPE operator[](size_t index) const
    {
        if (index < 0 || index >= size())
            throw std::out_of_range("Subscript out of range");

        //subscript is in valid range -
        //return a non-modifiable lvalue
        size_t count=0;
        ListNode<NODETYPE> *currentPtr=firstPtr;

        while (count != index)
        {
            ++count;
            currentPtr=currentPtr->nextPtr;
        }

        return (currentPtr->data);
    }

    size_t size() const
    {
        return len;
    }

    void emptyList()    //PROBLEMATIC FUNCTION IF THE DECISION IN THE IF STATEMENT EVALUATES TO TRUE
    {
        if (len) //List is not empty
        {
            std::cout << "Destroying nodes ...\n";

            ListNode<NODETYPE> *curPtr=firstPtr;
            ListNode<NODETYPE> *tempPtr=nullptr;

            while (curPtr)
            {
                tempPtr=curPtr->nextPtr;
                delete curPtr;
                curPtr=tempPtr;
                --len;
            }

            firstPtr=lastPtr=nullptr;
        }
    }


private:
    ListNode<NODETYPE> *firstPtr;           //pointer to first node
    ListNode<NODETYPE> *lastPtr;            //pointer to last node
    size_t len;

    //utility function to allocate new node
    ListNode<NODETYPE> *getNewNode(const NODETYPE& value)
    {
        return new ListNode<NODETYPE>(value);
    }

};
#endif
This question has already been answered. Start a new discussion instead.