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

[devonrevenge]

oh yeah of course

[fun2code]

Good. You got all of that yourself except how to judge when to stop iterating through the list.

That method of iterating until NULL (or some other certain value) is found will be key in other functions for finding a desired place in the list, like inserting elements in order, etc.

I have another task for you to try.
You have an addNode() for adding a node at the front of the list.
I guess you didn't like push_front! Doesn't matter of course, but now another function name is needed.

Write a function to add a node at the end of the list.
The common (boring) name is push_back, but choose what you wish.

You will need to do what is done in the displayList(), but you need to stop 1 node sooner. Iterate until conductor->next = NULL. Then conductor points to the last node in the list. Just tack a new node on right there!

[devonrevenge]

it only displays the last node, i suspect that i didn't re-connect the chain somehow but my mind got cloudier and cloudier and soon enough i couldn't remember if NULL is the front or the back, and who is behind whom.

#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)
{
list::node* newnode = new list::node;
newnode->num = number;
newnode->word = words;
while (conductor->link!=NULL)
  {
      conductor=conductor->link;
      if (conductor->link == NULL)
      {
          conductor->link = newnode;    //so the would be NULL is now a new node
          newnode->link = NULL; // and the newnode must now connect to NULL?
      } //either way it wont work if its not connected.
  }
 return newnode;
}



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


};

int main ()
{

list object;
list::node* base = NULL;
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 ");

base = object.push_back(base,11," that boy stood on the burning deck ");

object.displaylist (base);




   return 0;
}

[cire]

list::node* push_back (list::node *conductor,int number,string words)
{
list::node* newnode = new list::node;
newnode->num = number;
newnode->word = words;
while (conductor->link!=NULL)
  {
      conductor=conductor->link;
      if (conductor->link == NULL)
      {
          conductor->link = newnode;    //so the would be NULL is now a new node
          newnode->link = NULL; // and the newnode must now connect to NULL?
      } //either way it wont work if its not connected.
  }
 return newnode;
}

So, once conductor->link is NULL, you assign a value to it, which means it is no longer NULL, which means the loop continues. The pointer is advanced, so now conductor is == newnode, so you set its link to point to itself and then to NULL, finally causing the loop to stop.

You return a pointer to the last element in the list, when you should be returning a pointer to the first.

list::node* push_back (list::node *conductor,int number,string words)
{
    list::node* tail = conductor ;

    // navigate to the tail.
    while ( tail->link )
        tail = tail->link ;

    tail->link = new list::node ;
    tail=tail->link ;

    tail->num = number ;
    tail->word = words ;
    tail->link = nullptr ;

    return conductor ;
}

[devonrevenge]

i see what i did, thanks for explaining. i have to think the way you did it for a while though.

i guess i was a long way from finding that solution myself

[devonrevenge]

why does it return conductor? im going to see what happens if its void too.

i can see how it works but im not crystal just yet, i feel like i need to practice more, thanks cire.

[cire]

why does it return conductor?

Well, the code isn't quite complete. Perhaps if it were it would be more obvious. We need to handle the case where conductor is 0/NULL/nullptr. What do you think push_back should do in that case? Maybe it should just create a new list?

list::node* push_back( list::node * list, int number, string words )
{
    list::node* tail = list ;

    if ( tail == nullptr )
        list = tail = new list::node ;
    else
    {
        while ( tail->link )
            tail = tail->link ;

        tail->link = new list::node ;
        tail = tail->link ;
    }

    tail->num = number ; 
    tail->word = words ;
    tail->link = nullptr ;

    return list ;
}

int main()
{
    list::node * list = nullptr ;
    list = push_back(list, 6, "lay on the ground quite still  ") ;
    // ..
}

push_front already handles the nullptr case nicely.


If I were designing a list in this fashion (as opposed to making it a class like we should) I would be more inclined to pass a reference to a pointer to the head of the list so that it wouldn't be necessary for the caller to assign the return value to the list pointer when the head was modified. Making it a class, of course, would be a much better solution.

[devonrevenge]

oh i thought you just gave me the answer, i was strangley happy when it didnt work properly cos it didnt make sense anyway.

[devonrevenge]

this, this isnt what you meant by putting it in a class is it, though it is in a class

#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)
{
list::node* tail = conductor;
while (tail->link != NULL)
{
    tail = tail->link;
}

tail->link = new node;
tail->link = NULL;
tail->word = words;
tail->num = number;

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 object;
list::node* base = NULL;
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 ");

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

object.displaylist (base);




   return 0;
}

[Catfish2]

Finally.
Now all you need to do is store your base inside the class, and make your push_front() automatically use it. And then your code can look like:

list object;

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 ();

[fun2code]

@devonrevenge

Nice try but, as cire pointed out, making the assignments from inside the while loop causes problems.

In the push_back function the only thing we are using the while loop for is to locate the last node in the list. We can know we have reached the last node because it is the only node that has next = NULL (which signifies that there is no next node).

Hence:

while( conductor->link != NULL )
    conductor = conductor->link;

Will do the job. The while loop ends when conductor->link = NULL.
conductor will be pointing to the last node following this while loop.

So, finish this function here:

node* push_back (node *conductor,int number,string words)
{
node* newnode = new list::node;
newnode->num = number;
newnode->word = words;
newnode->link = ?;// don't forget to assign this. What value belongs here?
while (conductor->link!=NULL)
  {
      conductor=conductor->link;
   }

    // assign newnode to something here 
    
 return conductor;
}

Then I will have another task for you.

I see that you have created a list class, defined the node structure in it, added a 2nd data member, etc...
While this is where we are going, at this point I think it introduces unnecessary complication.

I'd prefer to keep our model of a link list simple, so we can focus on how it works.

@cire. The advice you give is good but I think that you are introducing new concepts too quickly.

Let's step back a moment, OK?
What is required at minimum to create and use a link list?

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

int main()
{
    node* front = new node;
    front->x = 3;
    front->link = NULL;
    
    // we have created a (1 node) list!

       return 0;
}

We belong at baby step #4 away from this right now.

@devonrevenge. When you get that push_back() working right then
we will look at a a way to make it more efficient. OK?

EDIT: When I look at the above code for baby step 1 I see that I missed a baby step!
I should have gone from this:

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

int main()
{
    node* front = new node;
    front->x = 3;
    front->link = NULL;

    if( front != NULL )
        cout << "x = " << front->x << endl;

       return 0;
}

To this:

struct node
{
    int x;// the data payload
    node* link;// pointer to another node
    node(): x(0), link(NULL) {}
    node( int X, node* Link ): x(X), link(Link) {}
};

int main()
{
    // create a one node list
   node*  front = new node(3, front);
    
    // display its contents
    if( front != NULL )
        cout << "x = " << front->x << endl;

       return 0;
}

To this:

struct node
{
    int x;// the data payload
    node* link;// pointer to another node
    node(): x(0), link(NULL) {}
    node( int X, node* Link ): x(X), link(Link) {}
};

int main()
{
    // create a four node list
    node* front = NULL;
    front = new node(3, front);// we don't actually need a push_front() yet.
    front = new node(4, front);// we're doing it here directly.
    front = new node(5, front);
    front = new node(6, front);    

    // we have created a (4 node) list!
    // let's see it - write a displayList() if you don't want this cluttering up main()
    node* iter = front;
    while( iter != NULL )
    {
        cout << "x = " << iter->x << endl;
        iter = iter->link;
    }

       return 0;
}

Actually, the next thing needed here is a cleanup() function for deleting the nodes when we are done with them.
Note: This global cleanup() function will become the basis for a list class destructor later.

EDIT2:
Notice that with the new node structure constructor, a push_front() may now be written as:

node* push_front( node* front, int X )
{
    return new node( front, X );
}

It's hard to get much simpler than that!

[devonrevenge]

can someone tell me why this function did not work?

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

list::node* temp = new list::node;
temp = conductor->link;
conductor=conductor->link;
conductor->link=NULL;
conductor->word = words;
conductor->num = number;
return conductor;

}

is it because im connecting to the wrong end

wait temp = conductor was supposed to be conductor->link = temp but it dont workify anyhow.

[cire]

You didn't preserve a pointer to the head (first element) of the list and you leaked your memory right after you allocated it.

temp = new list::node ;  // temp points to newly allocated memory.
temp = conductor->link;   // temp no longer points to newly allocated memory. 

[Catfish2]

Minor point: with that while() you don't need the if().

The code doesn't work because... you're simply throwing away the data that temp points to.

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

    list::node* temp = new list::node;
    // temp = conductor->link;
    conductor->link = temp; // it's the other way around
    conductor=conductor->link;
    conductor->link=NULL;
    conductor->word = words;
    conductor->num = number;
    return conductor;
}

[fun2code]

RESET

Complete this function:

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

    //something = newnode; ONE LINE goes here     
    
 return conductor;
}

[devonrevenge]

didnt see you changed your post up there fun2code, thanks for the help, and incredible patience, i feel a bit slow on this one.

EDIT; wow for the return new node thing!!

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; //:D
while (conductor->link!=NULL)
  {
      conductor=conductor->link;
  }

    conductor->link = newnode;

   return conductor;

}

is this supposed to work? ithink i might have an error elsewhere if it is, i been at this ALL day :O

[devonrevenge]

why does it show only two of the last?? its not hooked up to summink again is it :P

[devonrevenge]

:D

{
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;
}

theres something i realy cant get the feeling of, i should have tried to draw the whole thing, its working out which way theyre linking and where im putting what new node...ive been trying to put square pegs in round holes for five hours, its a good puzzle though.

[fun2code]

The problem is that we changed conductor within the function, and then returned this changed value.

I'm sorry. I'm the one who is slow here.
The value of front will not be changed by a push_back() operation.
push_back() does not need to return anything here!
It should be:

void push_back( node* conductor, int number )
{
    node* newnode = new node;
    newnode->num = number
    newnode->link = NULL;
    while (conductor->link!=NULL)  
        conductor=conductor->link;

    conductor->link = newnode;
    return;
}

Which would be called like so:

int main()
{
    node* front = NULL;
    front = push_front( front, 3 );// list = 3
    front = push_front( front, 4 );// list = 4 3
    push_back( front, 5 );// list = 4 3 5
    return 0;
}

[devonrevenge]

my thanks for all your help fun2code, you seem like a professional teacher, or maybe a sentient AI?

either way maybe i wouldnt have understood this all by myself + google as soon as i have :D, am gonna have a play with them now and then get some undeserved sleep and start again tmrw