Thread: Linked List problems

Hi,

I have this simple file that is supposed to create a Node struct to form a linked list. Basically what I want is for the user to be able to enter as many strings as he or she wants and for each new string the program creates a new "Node" and assigns 'nvalue' to the string and the 'ptr' of the last node, which is a node pointer, to point to the new node. Here is the code that I have implemented so far (just testing out basics), but it won't compile:

Code:

#include <cstdlib>
#include <iostream>
#include <string>

using namespace std;

struct Node
{
    string nvalue;
    Node *ptr;
}

int main(int argc, char *argv[])
{ // line 14
    Node myNode;
    cin >> myNode.nvalue;
    cout << "You inputted: " << myNode.nvalue;

    System("Pause");
    return 0;
}

Error:

Code:

14 test.cpp new types may not be defined in a return type 
14 test.cpp extraneous `int' ignored 
14 test.cpp `main' must return `int' 
14 test.cpp return type for `main' changed to `int'

Code:

struct Node
{
    string nvalue;
    Node *ptr;
};

Is there any good technique when creating multiple Nodes? Like when inside of a while loop that keeps looping until the user stops inputting data and each time creating a new node for each input, how would I best go about creating and naming those nodes?

Code:

int c = 0;
while(getline(cin, temp)) 
{
  Node myNode; // this would be overwritten each time
  myNode.nvalue = temp;
}

I can't have arrays because there is no way of telling how many nodes there will be - the user keeps inputting data until he or she decides they are done.

With a linked list you should be creating nodes dynamically, since they will be owned by the list and might outlive the function that creates them. That means using new to create a node. That also means you should delete nodes that are removed from the list and also delete the nodes in the list when it is destroyed.

I'm having a lot of trouble figuring out how to code this. My test program creates two Nodes then attempts to point the variable "Node *ptr" of the first node to the second node. Here is what I have:

Code:

#include <cstdlib>
#include <iostream>
#include <string>

using namespace std;

struct Node
{
    string nvalue;
    Node *ptr;
};

int main(int argc, char *argv[])
{
    Node myNode;
    cin >> myNode.nvalue;
    cout << "Node 1 nvalue: " << myNode.nvalue;

    Node myNode2;
    cin >> myNode2.nvalue;
    cout << "Node 2 nvalue: " << myNode2.nvalue;

    myNode.ptr = myNode2;

    system("Pause");
    return 0;
}

Here is the error message:

Code:

23 test.cpp cannot convert `Node' to `Node*' in assignment

I've been reading a lot of linked list tutorials but they have just made me even more confused. Is ->next a built in function? I keep seeing stuff like temp = temp->next but I never see any other reference to ->next. What exactly does "->" mean? Does anyone know of a good tutorial for linked lists?

Thanks! Now my test program works. I still have one main problem that is not technical but design oriented: how do I create an indefinite amount of nodes? Like I said above, the program is going to keep executing inside a while loop until the user ends the input. For each line of input the program will create a new node associated with the input. But I can't use arrays because the program won't know how many elements there are going to be. Otherwise I would do something like:

Code:

Node myNodes = new Node[20];
int c = 0;
string temp;
while(getline(cin, temp))
{
  myNodes[c] = new Node;
  myNodes[c].nvalue = temp;
  myNodes[(c-1)].ptr = &myNodes[c];
}

The above code may not be entirely correct, it is just a rough example.

Nevermind my last question, I found a good tutorial that explains linked lists well.

Ok, another question. I created this header file but I am not sure that the structuring is correct:

queue.h

Code:

#ifndef QUEUE
#define QUEUE
#include <string>

class queue
{
    public:
        queue(void);
        bool push(std::string ss);
        std::string pop(void);
        std::string first(void) const;
        std::string last(void) const;
        bool err(void);

    private:
        struct Node
        {
            string nvalue;
            Node *pNext;
            Node *pPrev;
        };

        Node *pHead, *pTail;
};

#endif

It also gives me a compile error at line 22 (bolded):

Code:

'string' does not name a type

string is a member of namespace std.
so put std::string instead

Doh, I don't know how many times I have done that.

New problem: My attempt at creating new Node objects from inside an instance of the class is not working. Here is my code:

queue.h

Code:

/*
    Nick Bakewell
    10/10/07
*/
#ifndef QUEUE
#define QUEUE
#include <string>

class queue
{
    public:
        queue(void);
        bool push(std::string ss);
        std::string pop(void);
        std::string first(void) const;
        std::string last(void) const;
        bool err(void);

    private:
        struct Node
        {
            std::string nvalue;
            Node *pNext;
            Node *pPrev;
        };

        Node *pHead, *pTail, *myNode;
};

#endif

And my driver:

Code:

#include <cstdlib>
#include <iostream>
#include <string>
#include "queue.h"

using namespace std;

int main(int argc, char *argv[])
{
    queue myQueue();
    
    for(int i = 0; i < 5; i++)
    {
        myQueue.myNode = new Node; // line 14
        cin >> myQueue.myNode->nvalue; // line 15
        myQueue.AddNode(myQueue.myNode); // line 16
    }
[...]

The compiler is giving me this error:

Code:

14main.cpp request for member `myNode' in `myQueue', which is of non-class type `queue ()()' 
14 main.cpp `Node' has not been declared 
15 main.cpp request for member `myNode' in `myQueue', which is of non-class type `queue ()()' 
16 main.cpp request for member `AddNode' in `myQueue', which is of non-class type `queue ()()' 
16 main.cpp request for member `myNode' in `myQueue', which is of non-class type `queue ()()'

queue.cpp

Code:

/*
    Nick Bakewell
    10/10/07
*/
#include <iostream>
#include <cstdlib>
#include <string>
#include "queue.h"

using namespace std;

queue::queue()
: pHead(NULL), pTail(NULL), myNode(NULL)
{}

bool queue::push(string ss)
{
    if(pHead == NULL)
    {
        pHead = myNode;
        myNode->pPrev = NULL;
    }
    else
    {
        pTail->pNext = myNode;
        myNode->pPrev = pTail;
    }
    pTail = myNode;
    myNode->pNext = NULL;

    return true;
}

string queue::pop()
{
    Node *pTemp;
    pTemp = pTail;

    pTail = pTail->pPrev;
    pTail->pNext = NULL;

    return "\nPop: " + pTemp->nvalue + "\nNew last value: " + pTail->nvalue + "\n";
}
    
string queue::last()
{
    return pTail->nvalue;
}

string queue::first()
{
    return pHead->nvalue;
}

bool queue::err()
{
    return false;
}

>> queue myQueue();
That should be queue myQueue; otherwise it declares a function.

In your push function you need to use new to create a new node. In your pop function you need to use delete to delete the node you remove. Don't use new to create the node in main.

Also, you call AddNode in main, but there is no AddNode in your queue.

So I should delete pTemp inside of pop after I use it in the return statement?

For my main method, you are saying that it should be structured like this?

Code:

int main(int argc, char *argv[])
{
    queue myQueue;
    string temp;

    for(int i = 0; i < 5; i++)
    {
        cin >> temp;
        myQueue.push(temp);
    }
[...]

Then push would look like:

Code:

bool queue::push(string ss)
{
    myNode = new Node;
    myNode->nvalue = ss;

    if(pHead == NULL)
    {
        pHead = myNode;
        myNode->pPrev = NULL;
    }
    else
    {
        pTail->pNext = myNode;
        myNode->pPrev = pTail;
    }
    pTail = myNode;
    myNode->pNext = NULL;

    return true;
}

I appreciate all of the help you're giving me and i'm sorry if I take a while to grasp this concept.