can you help me with linked lists? im close, so very close to grasping it.

[D80DSL3A]

You're welcome.
I wish I was a better teacher.
I keep making mistakes.

The push_back() above has a critical flaw. It can't be used to add the first node to a list.

int main()
{   
    node* front = NULL;
    push_back( front, 3 );// BOOM!! Program crashes!
}

Why?
Hint: Line #9 in the push_back().

I will think more on this and get back later.

[devonrevenge]

this is what im struggling to grasp...

node* push_back (node *conductor,int number,string words)
{
node* newnode = new list::node;
newnode->num = number;
newnode->word = words;
newnode->link = conductor;
while (conductor->link!=NULL)
  {
      conductor=conductor->link;
   }

    conductor = newnode;
    
 return conductor;
}

this works but i dont see whats pointing to NULL anymore.

newnode->link = conductor is identical to push_front.
so theres the new node at the front of the list.

so then we cycle down to the end of the list.
and link the would be NULL pointing linker to the new node sitting at the front.

thats a big loop in my head.

so when i push_back a new node how come it finds a null again?? wait is it beacuse it doesnt replace null it ops inbetween null and the end because of conductor->link??

so its still connected into a loop? just one node points to null somehow???

[D80DSL3A]

Line 6 is supposed to be: newnode->link = NULL;
There's the NULL at the end of the list.

[devonrevenge]

WHAAAT!? that makes logical sense to me, i put it straight in there, i was like cant be initialized to anyting esle, however i only get the last line of code as an output!!! if i put conductor in however i get all the code in the right place!!!

i wasnt understanding this at all, im glad its wrong again, cos it doesnt make sense (even though in this case it works)

[D80DSL3A]

What are you doing with the return value from push_back() ?
Don't use it. The function returns conductor, but only after it was iterated to point to the end of the list. Don't assign that to to your front node in main().

I've been playing around with the node class a bit and I came up with this nifty recursive displayList function.
It takes a character argument to tell which direction to display the list in:'f' = forward and 'r' = reverse:
Just call it with a node in main()

void node::displayList( char dir )
{
    if( dir == 'f' ) cout << x << " ";
    if( link ) link->displayList( dir );
    if( dir == 'r' ) cout << x << " ";
}

Or, how about this dandy recursive push_back() function for the node class?

void node::push_back( int X )
{
    if( link )
        link->push_back(X);
    else
        link = new node( X, NULL );
}

[devonrevenge]

wooow i will study these, thanks fun to code, im a beginner so everynow and again my basics are unstable, takes a lot longer to remember how simple things work if my brain is allready taxed

[devonrevenge]

the code dosnt work with your (correct im sure) version of push back, do you think it could be the rest of the code and not your function

[D80DSL3A]

I hope it's the rest of the code.

I've gone a bit rogue here in my effort to avoid creating a list class.
Thought I'd see how much I can do using the node class alone.
It's working for me, so here's what I have:

struct node
{
    int x;// the data payload
    node* link;// pointer to another node

    // functions
    void push_back( int X );
    void display( char dir );

    node(): x(0), link(NULL) {}
    node( int X, node* Link ): x(X), link(Link) {}
    ~node() {}
};

void node::push_back( int X )
{
    if( link )
        link->push_back(X);
    else
        link = new node( X, NULL );
}

void node::display( char dir )
{
    if( dir == 'f' ) cout << x << " ";
    if( link ) link->display( dir );
    if( dir == 'r' ) cout << x << " ";

     return;
}

// global functions
void cleanup( node* front )// iterative version
{
    while( front )
    {
        node* temp = front;
        front = front->link;
        delete temp;
    }
}

// for deleting the nodes
void cleanup_rec( node* iter )// recursive version
{
    if( iter )
    {
        cleanup_rec( iter->link );
        cout << "deleting x = " << iter->x << endl;
        delete iter;
    }

    return;
}

void print( node* iter, char dir )// forward if dir = 'f', reverse if dir = 'r'
{
    if( iter )
    {
        if( dir == 'f' ) cout << iter->x << " ";
        print( iter->link, dir );
        if( dir == 'r' ) cout << iter->x << " ";
    }
     return;
}

int main()
{
    // create list
    // push_front *4
    node* front = new node(1, NULL);
    front = new node(2, front);// these lines do a push_front
    front = new node(3, front);
    front = new node(4, front);

    // push_back*2
    front->push_back(5);// a node performing a push_back on itself!
    front->push_back(6);


    print( front, 'f' );// show it forward
    cout << endl;
    front->display('r');// show it backward

    // cleanup
    cleanup_rec( front );

    cout << endl;
    return 0;
}

Output:

4 3 2 1 5 6
6 5 1 2 3 4
deleting x = 6
deleting x = 5
deleting x = 1
deleting x = 2
deleting x = 3
deleting x = 4

As expected.

[devonrevenge]

for push back why wasnt creating a new node and getting the pointer that would point to NULL to point to the new node not working?#

list::node push_back (front, int, num)
{
list::node la = new list::node;
la->link =NULL
la->int=int;
la->num=num;
while (front->link != NULL)    
   {
       front=front->link;
   } 
    
    front->link = la;
    return la; //is it returned all linked or could i return front->link = la?
    
}

[D80DSL3A]

The function is returning a pointer to the last node in the list (the one just created with new right?).

Are you doing this in the main()?
front = push_back(front, 7);

If so, don't do that!

Call push_back() by itself. Throw away the return value (unless you WANT to save a pointer to the tail node that is).

ie: push_back(front, 7);// don't assign return value to front

Is that what's going on?

[devonrevenge]

yup -_- i was calling it wrong, i just forgot about that end of the code.

it doesnt work still, your canny link thing does though but i would like to have this in me=y head a lttle clearer

[D80DSL3A]

Of course.

Please post the entirety of your code so I can figure out what's wrong and we can get back on track here.

[devonrevenge]

here, again thanks for your help, more like tutoring here

#include <iostream>
#include <string>

using namespace std;
class list
{
public:



  struct node
  {
    int num;
    string word;
    node* link;
  };



list::node* push_front (list::node* front,int number,string word )
{
    list::node* temp = new list::node;
    temp->num = number;
    temp->word = word;
    temp->link = front;
    return temp;
}

list::node* push_back (list::node *conductor,int number,string words)
{
node* newnode = new list::node;
newnode->num = number;
newnode->word = words;
newnode->link = NULL;
while (conductor->link!=NULL)
  {
      conductor=conductor->link;
  }

conductor = newnode;
return conductor;
}



void displaylist (list::node *conductor)
{
  while(conductor!=NULL)
  {
  cout<<conductor->word;
  cout<<conductor->num<<endl;
  conductor = conductor -> link;
  cout<<endl;
  }
}


};

int main ()
{
list::node* base= NULL;
list object;



base = object.push_front(base,6," Lay on the ground quite still  ");
base = object.push_front(base,4," Find fresh underpants to try on ");
base = object.push_front(base,8," Keep like that day after day  ");
base = object.push_front(base,2," If you're attacked by a Lion ");
base = object.push_front(base,7," Pretend you are very ill ");
base = object.push_front(base,9," Perhaps the lion will go away ");

object.push_back (base,11," that boy stood on the burning deck ");
object.push_back(base,12, " a wolly scarf around his neck ");
object.push_back(base,13, " hat on his head ");
object.push_back(base,14," shoes on his feet ");
 object.push_back(base,15, " he wished he was wearing trunks instead ");


object.displaylist (base);




   return 0;
}

[naraku9333]

list::node* push_back (list::node *conductor,int number,string words)
{
node* newnode = new list::node;
newnode->num = number;
newnode->word = words;
newnode->link = NULL;
while (conductor->link!=NULL)
  {
      conductor=conductor->link;
  }

conductor = newnode;//should be conductor->link = newnode
return conductor;// return conductor->link //asuming you want to return last node
}

[D80DSL3A]

naraku9333 nailed it on the head.

Change line 12 per narakus note line 12 and you will find that your peogram works perfectly.

OMG I am so pissed right now!

I had a great post prepared, and it was long.
I hit the "preview" button and the browser replies with "permission denied". I found I was suddenly not logged in and my post was lost.

I don't have the energy to redo it. Sorry.

Some advice: ALWAYS copy your post to notepad or something before hitting that preview button! (I'm pissed because this has happened to me 4 times in the last 2 days.

The other way I've found in which a post ca be instantly and irretrievably lost is to hit the backspace key (thinking that you are going to delete the last character you entered) but somehow the focus left the editing window, so the backspace is interpreted as the shortcut for "go back one page" in the browser!! And then your post is gone!

[Lowest0ne]

//asuming you want to return last node

A wrong assumption. push_back accepts a pointer to node, but it creates it's own pointer (it isn't by reference). The only way to maintain a list is to return the function's pointer.

I would change the output function a little:

void displaylist (list::node *conductor)
{
  while(conductor!=NULL)
  {
    cout << conductor << ": "
         << conductor->word << ", "
         << conductor->num << "."
         << "  Next -> "conductor->link << endl;
    conductor = conductor -> link;
    cout<<endl;
  }
}

A little more educational that way, to see the addresses these things point to. Especially useful if you want to start deleting nodes in the middle of the list.

[devonrevenge]

-BOOM-Success, and the double bonus is i understand too, we return conductor->link because thats what newnode is now XD

thanks guys perhaps when im really good i can return the favour by compiling loads of simple stuff for you :)




okay fun2code, i got one of those over sensitive touch pads so thats not such a bad idea.


in uk pissed means drunk too LOL

[naraku9333]

LowestOne wrote:

The only way to maintain a list is to return the function's pointer.

I return a pointer to the created node.

@devonrevenge
I'd say your list is more of a c-style list (not that it's a bad thing) but you will run into problems if you try to push front after push_back as you aren't keeping track of the front pointer. Since you are obviosly coding c++ class list you should encapsulate the push_front/back functions as class member functions and a front pointer member variable. Then there is no need to return anything from them.

[D80DSL3A]

nraku9333 is right about the need to "encapsulate" the front* within the class.

As for the return types of push_front() and push_back(), there is (as naraku pointed out) no need to return anything since we will manage the front pointer within these functions.
Also: http://www.cplusplus.com/reference/stl/list/push_front/ shows the STL versions of these functions return void.

Shall we go with that?

I have prepared a list class for starters. (copying post to clipboard now)

Please check this out.
Anyone else, please feel free to comment on this.

Taking the step suggested by cire and others some 50 posts ago this thread, I suggest for starters:

#include <iostream>
#include <string>

using namespace std;
class list
{

public:

    struct node
    {
        int num;
        string word;
        node* link;
        node(): link(NULL) {}// default ctor
        // this ctor will be quite helpful
        node( int Number, string Word, node* Link ): num(Number), word(Word), link(Link) {}
    };

    //*** functions ***
    void push_front(int number,string word );// no need to return pointers anymore
    void push_back(int number,string words);

    void displaylist(void);

    // ctor
    list(): front(NULL) {}

private:
    node* front;// this will point to 1st node, replacing base in main()
};

void list::push_front(int number,string word )
{
//    node* temp = new node;
//    temp->num = number;
//    temp->word = word;   ** code needed without the "special" node ctor **
//    temp->link = front;
//    front = temp;

    front = new node(number, word, front);// code WITH the "special" node ctor

    return;
}

void list::push_back(int number,string word)
{
//    node* newnode = new node;
//    newnode->num = number;
//    newnode->word = word;    ** yuck **
//    newnode->link = NULL;
    node* newnode = new node(number, word, NULL);

    // handle case of empty list
    if( front == NULL )
    {
        front = newnode;
        return;
    }

    // list has 1 or more nodes already - this part will be getting simpler soon
    node* iter = front;
    while (iter->link!=NULL)
        iter = iter->link;

    iter->link = newnode;
    return;
}

void list::displaylist(void)
{
    node* iter = front;
    while(iter!=NULL)
    {
    cout << iter->word;
    cout << iter->num << endl;
    iter = iter->link;
    cout << endl;
    }
}
//** end of list class member function definitions **


int main ()
{
    list object;// now the object contains the list. No list::node* needed here.

    object.push_front(6," Lay on the ground quite still  ");
    object.push_front(4," Find fresh underpants to try on ");
    object.push_front(8," Keep like that day after day  ");
    object.push_front(2," If you're attacked by a Lion ");
    object.push_front(7," Pretend you are very ill ");
    object.push_front(9," Perhaps the lion will go away ");

    object.push_back(11," that boy stood on the burning deck ");
    object.push_back(12, " a wolly scarf around his neck ");
    object.push_back(13, " hat on his head ");
    object.push_back(14," shoes on his feet ");
    object.push_back(15, " he wished he was wearing trunks instead ");

    object.displaylist();

   return 0;
}

This compiles and runs without any warnings or errors.
(copies post to clipbboard again)

This class is quite glaringly lacking a destructor!
I'll post back with that!

EDIT:
prototype: ~list();
definition:

list::~list()
{
    unsigned N = 0;// a frill
    while( front )
    {
        node* temp = front;
        front = front->link;// who cares now?
        delete temp;
        ++N;// counting nodes
    }
    cout << "*** deleted list with " << N << " nodes" << endl;
}

I just tested this. No problems here.

EDIT2:

in uk pissed means drunk too LOL

That's funny!
I am aware of that uk usage, but because that is not the usual usage here in the states, I didn't even think of it!

[D80DSL3A]

Bonus function for the new list class!

I'm guessing that the number accompanying the word in each node is to indicate the order in which the sentences should appear, when sorted in order by that number.
If this is so, then you will like this.
An in-place sort for this link list could get messy.
But, if we insert them in order as they are added to the list it is easy:

So we have (hot off the press and barely tested!):

//insert nodes in ascending order
void list::insert_asc(int number,string word)
{
    // now find where it goes
    if( front == NULL )// new front because list is empty
        push_front(number, word);
    else if( number < front->num )// new front because it belongs there
        push_front(number, word);
    else
    {// find where it goes in the list.
        node* iter = front;
        while( (iter->link != NULL) && (number > iter->link->num) )
        iter = iter->link;

        // iter now points to the node before the insertion point
        iter->link = new node(number, word, iter->link);
    }

    return;
}

So, if you replace the push_back, push_front calls in main() with this:

int main ()
{
    list object;// now the object contains the list. No list::node* needed here.

    object.insert_asc(6," Lay on the ground quite still  ");
    object.insert_asc(4," Find fresh underpants to try on ");
    object.insert_asc(8," Keep like that day after day  ");
    object.insert_asc(2," If you're attacked by a Lion ");
    object.insert_asc(7," Pretend you are very ill ");
    object.insert_asc(9," Perhaps the lion will go away ");

    object.insert_asc(11," that boy stood on the burning deck ");
    object.insert_asc(12, " a wolly scarf around his neck ");
    object.insert_asc(13, " hat on his head ");
    object.insert_asc(14," shoes on his feet ");
    object.insert_asc(15, " he wished he was wearing trunks instead ");

    object.displaylist();

   return 0;
}

You should get this:

  If you're attacked by a Lion 2

 Find fresh underpants to try on 4

 Lay on the ground quite still  6

 Pretend you are very ill 7

 Keep like that day after day  8

 Perhaps the lion will go away 9

 that boy stood on the burning deck 11

 a wolly scarf around his neck 12

 hat on his head 13

 shoes on his feet 14

 he wished he was wearing trunks instead 15

*** deleted list with 11 nodes

Now, that's a lot to digest so I'll hang back for awhile.