Error creating a simple linked list class

[beanmiester]

I've spent the better part of two hours going over my code line by line and I cannot find the problem for the life of me.

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

class NumberList
{
    struct ListNode
    {
        int value;
        ListNode *next;
    public: 
        ListNode(int val, ListNode * nextp = NULL)
        {
            value = val;
            next = nextp;
        }
    };

    ListNode * head;
public:
    NumberList()
    {
        head = NULL;
    }

    void print();
    void add(int value);
};

void NumberList::add(int value)
{
    if (head == NULL)
        head = new ListNode (value);
    else
    {
        //list not empty, find the last node

        ListNode *last = head;
        while (last->next != NULL)
            last = last->next;

        //add new value after last node
        last->next = new ListNode (value);
    }
}

int main()
{
    //create a list object
    NumberList numList;
    //add some values to the list
    for (int k = 1; k <= 4; k++)
        numList.add(10*k);

    //print the list
    numList.print();
    cout << endl << endl;

    return 0;

}

Here's the error I get when I try to compile.

*error LNK2019: unresolved external symbol "public: void __thiscall NumberList::print(void)" (?print@NumberList@@QAEXXZ) referenced in function _main*

I also get this, but I believe they are caused by the same error in my numList.print.

1>D:\CS-160\pc17try2\Debug\pc17try2.exe : fatal error LNK1120: 1 unresolved externals

Any help would be great, I've looked through my book and video notes and I don't believe I should be having any issues; very confused.

[chrisnick10]

Try changing the constraints on your 'for-loop' inside the main.

[beanmiester]

The loop looks fine to me, I'm not sure what you want me to change..

I've fiddled with changing the numbers and variables around but the error still pops up.

Are you sure the problem is even in the for loop? My IDE doesn't show me which problem the line is on and I'm starting to think it might be somewhere else.

[NathanOliver]

you are calling the print function on line 56 but you never defined it.

[chrisnick10]

I guess I was wrong. The only thing I have to add, for me at least, is that when there's a reference error in main with a function, it's usually the result of me thinking that I already declared/defined a smaller function (such as print or constructors).

[beanmiester]

Isn't it defined in line 26?

[beanmiester]

I spaced out and forgot to do the print function.

I fixed that and now I'm getting the same error in a different spot.

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

class ListNode
{
public:
    ListNode(double v, ListNode *p)
    {
        value = v; next = p;

    }

private:
    double value;
    ListNode *next;
    friend class LinkedList; //linkedlist has friend status
};

class LinkedList
{
public:
    void add(double x);
    bool isMember(double x);
    LinkedList( ) { head = NULL;}
    void print();
    void rPrint(){ rPrint(head);}
    ~LinkedList();
    void remove(double x);
    void reverse( );
    int search(double x);
    void insert(double x, int pos);
private:
    ListNode * head;
    static void rPrint(ListNode *pList);
};
//LinkedList::insert insert a given value at a specified position
void LinkedList::insert(double x, int pos)
{
    //cases where the new value goes at the beginning
    //or when the list is emptyy are handled seprately
    if ( pos == 0 || head == NULL)
    {
        head = new ListNode(x, head);
        return;
    }
    //figure out how many nodes to skip before splicing
    //in a new node
    ListNode *p = head; //p is used to walk down the list
    int numberToSkip = 1;

while (numberToSkip <= pos)
{
    if (p->next == NULL || numberToSkip == pos)
    {
        p->next = new ListNode(x, p->next);
        return;
    }
    p = p->next;
    numberToSkip++;
}
}

//linkedlistsearch
//searches the linked list for a given calue and returns its position in the list if found. otherwise it returns -1
int LinkedList::search(double x)
{
    int position = 0;
    ListNode *p = head; //used to search through nodes
    while (p)
    {
        if (p->value == x) return position;
        p = p ->next;
        position ++;
    }
    return -1; //not found
}

//linkedlist::remove removes a value passes as parameter form the linked list
void LinkedList::remove(double x)
{
    ListNode *garbage; //use to delete nodes
    if (head == NULL) return;

    //is x in the head?
    if (head->value == x)
    {
        garbage = head;
        head = head->next;
        return;
    }

    //x not in the head, find it
    ListNode *p = head;
    while (p->next != NULL && p->next->value != x)
    {
        p = p->next;
    }
    //p->next == NULL or p->next->value is x
    if (p->next == NULL) return; //did not find it
    else 
    {
        //delete the x
        garbage = p->next;
        p->next = garbage->next;
        delete garbage;
    }
}
//recursive print function prints all elements on a list passed as parameter
void LinkedList::rPrint(ListNode *pList)
{
    if (pList == NULL) return;
    else 
    {
        cout << pList->value<< " ";
        rPrint(pList->next);
    }

}

//linkedlist::print prints all elements on the list.
void LinkedList::print()
{
    ListNode *p = head; //use to walk down list
    while (p != NULL)
    {
            cout << p->value << " ";
            p = p->next;
    }
}
//linkedlistadd adds a given value to the list
void LinkedList:: add(double x)
{
    head = new ListNode(x, head);
}

//linkedlist::ismember checks to see if a given values is a member of the list
bool LinkedList::isMember(double x)
{
    ListNode *p = head; //use p to walk through list
    while (p != NULL)
    {
        if (p->value == x) return true;
        else
            p = p->next;
    }
    //list is exhausted without finding x
    return false;
}
int main()
{
    //explain program to user
    cout << "This program allows you to construct a list by specifying"
        "list members\n and their positions on the list.";
    //create empty list
    LinkedList list1;
    //demonstrate insert by position
    for (int k = 1; k <= 5; k++)
    {
        cout << "\nenter a number followed by a position: ";
        int x, pos;
        cin >> x >> pos;
        list1.insert(x,pos);
        cout << "\nCurrent list membership is: ";
        list1.rPrint();
    }
    system("pause");
    return 0;
}

error LNK2019: unresolved external symbol "public: __thiscall LinkedList::~LinkedList(void)" (??1LinkedList@@QAE@XZ) referenced in function _main

Any pointers would be appreciated.

[tinstaafl]

Try this ~LinkedList(){} at line 28.

[JasonHippy]

Tinstaafl's suggestion will at least get rid of the error the compiler is producing. But because your linked list class uses the new keyword to dynamically allocate memory for each node, you really should be freeing that memory in the linked list classes destructor. Otherwise you have a memory leak!

So instead of using an empty destructor, you should consider putting some code in there to free up the memory that was allocated. Simply deleting the head will not be enough, you'll need to walk through the linked list and delete each node. Something like this:

    while(head->next) // equivalent to while(head->next!=NULL)
    {
        ListNode* next = head->next;
        delete head;
        head=next;
    }
    delete head;

For your simple program, the amount of memory that is leaked is very small and is instantly cleaned up by the system as soon as your program ends. In fact it probably doesn't even register as a memory leak at all because the instance of your linked list class is destroyed when it goes out of scope right at the end of your program. And the little memory that was allocated by the class should be automatically freed-up by the system shortly afterwards. But you should be aware that if your class was being used in a larger, more complicated, real-world program. Particularly if the program has to run for a prolonged period of time and has to deal multiple instances of the linked list, storing large datasets each time it was used, then a memory leak like this could quickly become a real problem!

One of the golden rules of C++ is that any memory that is dynamically allocated using new must be freed by a call to delete. Failure to do this results in memory leaks.

The only exception to this is if you are using some form of smart-pointer to point to dynamically allocated memory (std::auto_ptr, std::shared_ptr, std::unique_ptr etc.). Smart-pointers are specialised pointer classes which can clean up after themselves. So as soon as they go out of scope, they will automatically free up the memory they point to. Or if there are multiple smart pointers pointing to a dynamically allocated block of memory, the memory is not freed until the last pointer goes out of scope. (The exact behaviours of the different smart-pointers vary, but that's more or less what they do in a very roundabout, generalised way.)

But if you aren't using some form of smart pointer to point to dynamically allocated memory; if you are using raw pointers, it is up to you to sort out calling delete at the appropriate point in your code!

BTW:
If you want to see the memory leak in action in your program, keep the destructor empty, comment out what you have for main and temporarily use the following code:

int main()
{
    for(int i=0;i<10000;++i) // Lets create your class 10,000 times
    {
        LinkedList list1;

        for(int k=0;k<1000; ++k) // and fill each instance with 0-999
        {
            list1.insert(k,0);
        }
    }
    return 0;
}

Now before compiling and running the modified program, hit ctrl + shift + escape to bring up the Windows task manager, switch to the 'Process' tab and select the 'CPU' column to sort all running processes by the amount of CPU time they are using (so the ones using the most CPU are at the top of the list). You also need to be able to see the 'Memory (private working set)' column too, so you might need to go into 'view->select columns' to be able to see that column if it's not already visible... Can't remember if it shows by default! :/

Anyway, with task manager set up, switch to VS and try running your a debug build of your program and watch the task manager window to see how much memory gets eaten up!
Note: Have your project set to a debug build, start debugging using F5. (A release build will probably run too quickly for you to be able to see the problem in the task manager).
On my PC the memory usage hits over 708Mb. Which is pretty obscene!

After doing that, try adding some code to the destructor to clean up the memory (my suggested code works fine). Then run another debug build using F5. The added destructor code will mean that the program takes a little longer to run its course, but the memory usage will stay really low. (360Kb on my machine).

Once you're done with that, you can remove my main() code and uncomment yours to get back to where you were.

Shocking wasn't it? So there we have it... A practical lesson in memory leaks and how to avoid them! :)