Linked list and dynamic allocation frustration c++

Question

Here's the reference code:

#include <iostream>
using namespace std;

class linkedList {

    struct listNode{ //a node of a list
        int value;
        struct listNode *next;
    };

    listNode *head;

    public:
    linkedList(){
        cout << "hello1\n";
        head = NULL;
    };

    linkedList(listNode* a){
        cout << "hello2\n";
        head = a;
    };

    ~linkedList();
    listNode* getHead() {return head;}

    void appendNode(int);

    //inline Search function due to unable to function outside of class definition
    listNode* rangeSearch(int a, int b){
            //listNode to search
            listNode *search = head;
            //listNode* toReturn = new listNode;
            //listNode to return list of values that are found within range
            linkedList *found = new linkedList;

            while(search){
                //if the current value is within range, then add to list
                if(search->value >= a && search->value <= b){
                    //append searched value onto found
                    found->appendNode(search->value);
                    //after appending, go to next value
                }
                search = search->next;
            }

            return found->getHead();
        }

    void display();
};



int main()
{
    cout << "Programmer  : n\n";
    cout << "Description : \n";
    linkedList* list = new linkedList;
    int x = 12;
    //values to search
    int s1 = 10, s2 = 14;

    // adds 2 to each number on list for 5 times 
    for(int i = 0; i < 5; i++){
        list->appendNode(x);
        x += 2;
    }

    //create something to hold pointer of found to be deleted when done using

    //print list
    cout << "Original set of numbers in linked list: ";
    list->display();
    cout << "\nThe following are the values withing ranges: " << s1 << " and " << s2 << ":\n";

    //EDITED:
    //list->rangeSearch(s1,s2);
    linkedList foundList(list->rangeSearch(s1,s2));
    foundList.display();
    //End of edit 6:40PM 7/18/13

    cout << "\nHere are the original set of numbers in linked list (again): ";
    list->display();
    delete list;
    return 0;
}


void linkedList::appendNode(int newValue)
{
    listNode *newNode = new listNode();  // To point to a new node
    listNode *nodePtr;  // To move through the list

    // Allocate a new node and store newValue there.
    newNode->value = newValue;
    newNode->next = 0;

    // If there are no nodes in the list
    // make newNode the first node.
    if (!head)
        head = newNode;
    else  // Otherwise, insert newNode at end.
    {
        // Initialize nodePtr to head of list.
        nodePtr = head;

        // Find the last node in the list.
        while (nodePtr->next)
            nodePtr = nodePtr->next;

        // Insert newNode as the last node.
        nodePtr->next = newNode;
    }
}

void linkedList::display() {
    for(listNode* p = head; p != NULL; p = p->next)
        cout << p->value << ' ';
}

linkedList::~linkedList()
{
    cout << "\ndestructor called";
    listNode *nodePtr;   // To traverse the list
    listNode *nextNode;  // To point to the next node

    // Position nodePtr at the head of the list.
    nodePtr = head;

    // While nodePtr is not at the end of the list...
    while (nodePtr != NULL)
    {
        // Save a pointer to the next node.
        nextNode = nodePtr->next;

        // Delete the current node.
        delete nodePtr;

        // Position nodePtr at the next node.
        nodePtr = nextNode;
    }
}

So a couple of questions here. First, why is it when I try to put the rangeSearch member function outside of the class definition, the compiler gives an error saying listNode* type is not recognized?

Second, this has to do with destructors. In this program, 2 instances (list & found list) were created but only 1 destructor was called. Can someone explain why? My intuition tells me that the dynamically allocated pointer to linkedList object did not get destructed. However, I don't know why. The reason I had to use dynamically allocated memory is primarily because I want to pass the pointer back to the main function. If I don't, when rangeSearch exits, the pointer will be passed back to main but whatever list the pointer had would be deconstructed after return ptr; (assume ptr is a pointer to a linkedList declared in rangeSearch) which will cause my program to crash because, now the address has nothing in it and I'm trying to call... nothing.

Well, as usual I would appreciate whoever the great Samaritan out there who would be more than willing to educate me more about this.

Answer 1

First, you are having an issue with scoping. In C++, the curly braces define a new scope, so you are defining listNode inside the class linkedlist. If you want to access it, you'd have to use the scoping operator as such linkedlist::listNode

I don't entirely understand your second question. I only see one call to delete, so why do you think two destructors will be called? The destructors are only called when you call delete, so unless you specify that you want to destroy it, it's still going to be there.

Although I don't entirely understand your question, I see that you returned a pointer to the head in rangeSearch, but you don't assign it to anything. What this means is that you will have a memory leak; you allocated memory for the found, but then don't do anything with it. Actually since you only return the head, you still wouldn't be able to delete it if you did assign something to it, because you wouldn't have access to linked list itself.

Answer 2

linkNode is nested inside of linkedList. Move listNode outside of the linkedList class, and you won't get the first error. Or you can use it's full declaration, linkedList::listNode. Also, if you leave linkNode nested, you will have to make it public.

In main, you can just say

linkedList list;

instead of

linkedList* list = new linkedList;

rangeSearch() is returning a value, but that value is never being assigned to anything in main(). rangeSearch() is allocating a linkedList, but it never gets deleted.