**linked list

This is a discussion on **linked list within the C++ Programming forums, part of the General Programming Boards category; i have a question, i have an assignment that im supposed to do involving a linked list, i've looked into ...

  1. #1
    cereal killer dP munky's Avatar
    Join Date
    Nov 2002
    Posts
    655

    **linked list

    i have a question, i have an assignment that im supposed to do involving a linked list, i've looked into them a little and have some knowledge, but my prof. wants me to use a pointer to a pointer??? im supposed to write a function w/a prototype like this

    void BuildPhoneBook(PhoneBook **headPP, const char *str)

    the 1st parameter is (im assuming) a pointer to a pointer to the 1st node in the linked list, the second is the info that will go in that particular node. im clueless where to start...

    NO!, im not asking you to do my homework, i just need a shove in the right directioin
    guns dont kill people, abortion clinics kill people.

  2. #2
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,607
    Well, how well do you understand pointers? Jumping into linked lists without a good understanding of pointers is like doing calculus with no algebra background.

    Here's a quick tutorial. I'll assume that you know a pointer is just an address value and what it means to dereference a pointer. Based on that, all you really need to know is that all function parameters in C are "passed by value". That means that any changes that a function makes to parameter vars are not reflected in the calling parameter. For example
    Code:
    void foo(int n)
    {
        n = 5;
    }//foo
    
    int main()
    {
        int i = 0;
    
        foo(i);
    
        printf("%d",i);
        //Output: "0"
    
        return 0;
    }//main
    Here, foo() does not change the value of i.
    Ok, so maybe you knew all this to begin with. Well, lets extend this to pointers...
    Code:
    void foo(int *n)
    {
        n = NULL;
    }//foo
    
    int main()
    {
        int i = 0;
        int *p = &i;
        
        printf("address before: %x\n",p);
        
        foo(p);
    
        printf("address after: %x\n",p);
    
        //Output: <the address's will be the same>
    
        return 0;
    }//main
    As you can see, the pointer is passed by value, therefore any changes done in foo() are not reflected in main().
    So what if we really want the function to make a change to a parameter that is seen outside the function? The awnser is to pass in a pointer to whatever it is you want the function to modify. So to modify our original foo()....
    Code:
    void foo(int *n)
    {
        *n = 5;
    }//foo
    
    int main()
    {
        int i = 0;
        
        foo(&i);
    
        printf("%d",i);
        //Output: "5"
    
        return 0;
    }//main
    Here, foo() was able to modify the value of i in main(). This is called pass by reference (via a pointer in C). So to extend the concept to pointers, if you want to pass a pointer by reference then you have to have a pointer to a pointer:
    Code:
    void foo(int **n)
    {
        *n = NULL;
    }//foo
    
    int main()
    {
        int i = 0;
        int *p = &i;
        
        printf("address before: %x\n",p);
        
        foo(&p);
    
        printf("address after: %x\n",p);
        //Output: <address after will be 0>
    
        return 0;
    }//main
    Phew.....so why have "PhoneBook **headPP"? So you can modify the value of headPP within BuildPhoneBook().
    If you didn't learn (or remember) anything, maybe I put someone else's learn on

    gg

  3. #3
    cereal killer dP munky's Avatar
    Join Date
    Nov 2002
    Posts
    655
    ok, here's what i have so far, im not sure if this is correct???
    Code:
    void BuildPhoneBook(PhoneBook **headPP, const char *str)
    {
    	PhoneBook *header = headPP; //first node in list
    	
    	PhoneBook *conductor; //used to point to each node
    	
    	header = new PhoneBook; 
    	
    	header->next = NULL;
    
    	conductor = headPP;
    
    	if(conductor != NULL)
    	{
    		while(conductor->next != NULL)
    		{
    			conductor = conductor->next;   
    	    }
    	}
    
    }
    maybe im just going about this the wrong way, but the only way i've seen linked lists done is w/the single pointer???
    Last edited by dP munky; 03-04-2003 at 05:48 PM.
    guns dont kill people, abortion clinics kill people.

  4. #4
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,607
    Revisit pointers in your class book/notes and study my tutorial. Notice that foo(int **n) had "*n = " somewhere in it, but your function does not have "*headPP = " anywhere in it.

    Also, you need to understand things like:
    - how is an empty list represented?
    - when I add a new node to the list, do I add to the end of the list or the begginning? (hint: "**headPP" awnsers this one)

    gg

  5. #5
    cereal killer dP munky's Avatar
    Join Date
    Nov 2002
    Posts
    655
    im still kinda lost, i've reviewed what you posted and i understand passing by referecne(i think) but im not seeing what you mean?
    Code:
    void BuildPhoneBook(PhoneBook **headPP, const char *str)
    {
    	*headPP = new PhoneBook;
    
    	PhoneBook *conductor;
    
    	conductor = headPP;
    
    	if(conductor != NULL)
    	{
    		while(conductor->next != NULL)
    		{
    			conductor = conductor->next;   
    	    }
    	}
    
    }
    guns dont kill people, abortion clinics kill people.

  6. #6
    Registered User whistlenm1's Avatar
    Join Date
    Jan 2002
    Posts
    124
    assuming the same as codeplug check this link out

    Linked List
    Man's mind once streched by a new idea, never regains its original dimensions
    - Oliver Wendell Holmes

    In other words, if you teach your cat to bark (output) and eat dog food (input) that doesn't make him a dog. It would have to chase cars, chew bones, and have puppies before I'd call it Rover ;-)
    - WaltP

  7. #7
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,607
    You're getting closer, but you need to really think about and understand every single line that you write. For example, what were you thinking <don't read sarcastically> when you wrote:
    Code:
    conductor = headPP;
    conductor is of type PhoneBook* and headPP is of type PhoneBook** - why whould you assign vars of differing "type" like that?

    The only reason headPP is passed in is so that the caller of the function has a pointer to the list once you are done building it. Starting thinking about actually building the list and then worry about "*headPP = <something>" later.

    Think along these lines:
    Code:
    while (not done building the list)
    {
       create a new node to add to the list
       add the new node to the list by prepending it to the list (newnode->next = head; head = newnode)
    }
    Don't make me do your homework, cuz I will

    gg

  8. #8
    cereal killer dP munky's Avatar
    Join Date
    Nov 2002
    Posts
    655
    nah, i wont, thanks for all the help though, sorry im not picking this up real quick(not really in the programming mood today) im slowly gettin it though, i fixed my initializer thing....anyway, back to work
    guns dont kill people, abortion clinics kill people.

  9. #9
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,607
    Keep it up. I can't stress enough how important it is to really understand pointer semantics like the back of your hand. Once you have that down, applying what you know is alot easier. Read up on that link that whistlenm1 posted, thats good stuff. Decompose the code line by line and understand it. Post here if there is anything you don't understand or need clarification on.

    gg

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Link List math
    By t014y in forum C Programming
    Replies: 17
    Last Post: 02-20-2009, 05:55 PM
  2. instantiated from here: errors...
    By advocation in forum C++ Programming
    Replies: 5
    Last Post: 03-27-2005, 08:01 AM
  3. How can I traverse a huffman tree
    By carrja99 in forum C++ Programming
    Replies: 3
    Last Post: 04-28-2003, 05:46 PM
  4. List class
    By SilasP in forum C++ Programming
    Replies: 0
    Last Post: 02-10-2002, 04:20 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM

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