Thread: linked list logic

im finally at the chapter that deals with linked lists. and to me, its confusing. i cant grasp exactly whats going on here. heres the code from the book that im trying to understand...

Code:

//////////////////////////////////////////
struct link        //one element of list
{
    int data;    //data item
    link* next;    // pointer to the next link
};
////////////////////////////////////////////
class linklist    //a list of links
{
private:
    link* first;        //pointer to the first link
public:
    linklist()            //no-arg constructor
    {
        first = NULL;    //no first link
    }
    void additem(int d);    //add data item (one link)
    void display();            //display all links
};
//------------------------------------------
void linklist::additem(int d)        //add item
{
    link* newlink = new link;        //make a new link
    newlink->data = d;                //give it data
    newlink->next = first;            //it points to the next link
    first = newlink;                //now first points to this
}
//------------------------------------------
void linklist::display()            //display all links
{
    link* current = first;    //set ptr to first link
    while( current != NULL )        //quit on last link
    {
        cout << current->data << endl;        //print data
        current = current->next;        //move to next link
    }
}
///////////////////////////////////////////////////

int main()
{
    linklist li;        //make linked list

    li.additem(25);        //add four items to the list
    li.additem(36);
    li.additem(49);
    li.additem(64);

    li.display();    //display entire list
    return 0;
}

now, at the additem(int) function it creates a new link, assigns d to the struct member data. what i dont get is what happens after that. *next points to the *first which is set to NULL by the
constructor. then first = newlink? wouldnt just make the newlink point to itself?

upon making the first link li.additem(25), this points to NULL. and first variable is set to point to '25'. and upon adding '36', it points to 25, and then having first point to '36'. LOL did i get this right?

Code:

first = NULL;

newlink->next = first; // = NULL;

first = newlink; // first = newlink, newlink->next = NULL;

[edit]
Have you ever seen those red plastic monkeys that come in a little barrel? Start with one, in your right hand. Now pick up one in your left. Hang the one in your right hand off of it. Now pick up one in your right hand. Hang the ones in your left hand on it. Repeat this until you run out of monkeys, or they hit the floor, which ever comes first.
[/edit]

Quzah.

>Have you ever seen those red plastic monkeys that come in a little barrel?
That's much better than my pocket full of change method. I think I'll adopt the barrel of monkeys method. Thanks quzah.

*next points to the *first which is set to NULL by the
constructor.

Initially, maybe you shouldn't think of 'next' as pointing anywhere--it's just assigned null.

*next points to the *first which is set to NULL by the
constructor. then first = newlink? wouldnt just make the newlink point to itself?

No. Look what would happen if you did the same thing with integers:

int next;
int first = 0;
int newlink = 10;

next = first;
first = newlink;

Is next equal to newlink?

In your linked list, newlink is a pointer and it is given an address by the new operator:

link* newlink = new link;

Lets just suppose that address in memory is the number 1000, so newlink is pointing at location 1000. Then, the line:

newlink->next = first;

sets next equal to null since first is null. Finally, the line:

first = newlink;

makes first point to the location 1000 in memory. Here is a diagram of what is happening: