Thread: **linked list

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

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

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

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