linked list logic

This is a discussion on linked list logic within the C++ Programming forums, part of the General Programming Boards category; im finally at the chapter that deals with linked lists. and to me, its confusing. i cant grasp exactly whats ...

  1. #1
    Registered User xion's Avatar
    Join Date
    Jul 2003
    Posts
    63

    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?
    Last edited by xion; 02-09-2005 at 02:21 AM.

  2. #2
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    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.
    Last edited by quzah; 02-09-2005 at 02:44 AM.
    Hope is the first step on the road to disappointment.

  3. #3
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >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.
    My best code is written with the delete key.

  4. #4
    Registered User
    Join Date
    Apr 2003
    Posts
    2,662
    *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:
    Attached Images Attached Images  
    Last edited by 7stud; 02-09-2005 at 05:54 PM.

  5. #5
    Registered User xion's Avatar
    Join Date
    Jul 2003
    Posts
    63
    thanks guys. got it.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. linked list question
    By mikeman in forum C Programming
    Replies: 1
    Last Post: 11-30-2008, 01:56 PM
  2. singly linked to doubly linked
    By jsbeckton in forum C Programming
    Replies: 10
    Last Post: 11-06-2005, 07:47 PM
  3. Please Help - Problem with Compilers
    By toonlover in forum C++ Programming
    Replies: 5
    Last Post: 07-23-2005, 11:03 AM
  4. How to use Linked List?
    By MKashlev in forum C++ Programming
    Replies: 4
    Last Post: 08-06-2002, 08:11 AM
  5. Linked list with two class types within template.
    By SilasP in forum C++ Programming
    Replies: 3
    Last Post: 02-09-2002, 06:13 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21