Thanks Richard, well I felt better for literally 5 minutes. Now I've
reached my next stumbling block. I'm trying to make the list functions
generic. I did have something like this in my append function:
int list_append ( LinkedList **list, void *data ) {
LinkedList *new_item;
if ( (new_item == (LinkedList *)malloc(sizeof(LinkedList))) ==
NULL ) {
return -1;
}
new_item->data = data
...
(btw, I don't know why the pointer to a pointer (ie **list) lets me
return the list pointer in the function arguments without having to
use a return statement... I just know it works because I've seen
others do it! Arrrgh!)
Ok, so I'll try to explain it. Assume you already have a linked list with
one or more elements. Assume further that the variable you use to keep
track of your linked list was declared like this:
int main (void)
{
LinkedList * my_list;
...
list_append(&my_list, stuff);
...
}
In memory, this will look like this:
Object of type LinkedList
+---------+ +---------+---------+
my_list:| ---|----->|data :next ---|-----> (next node)
+---------+ +-------|-+---------+
Object of type pointer |
to LinkedList V
+---------+
|some data|
+---------+
The variable my_list has an address in memory. You can access it like
this:
&a
This address is just a way of locating my_list in memory. The address
itself has a type in C. That type is pointer to (whatever it's the
address of). In this case that would be pointer to (pointer to LinkedList)
We can store that address in a variable, as long as the variable also
has type pointer to pointer to LinkedList, like this:
LinkedList ** address_of_my_list = &my_list;
An argument to a function is very much like a variable in the function,
that has already been initialized with a value from outside the function.
So when you define your function list_append:
int list_append ( LinkedList **list, void *data )
You are specifying that it will have an argument of type pointer to
pointer to LinkedList and, just as above, you can initialize that argument
with the address of your my_list variable when you call the function:
list_append(&my_list, some_data);
Now when list_append() is called like this, the layout of the data
structures in memory will be like this:
Object of type pointer to
pointer to LinkedList
+---------+
list:| | (this is the argument to list_append)
+-------|-+
|
|
V Object of type LinkedList
+---------+ +---------+---------+
my_list:| ---|----->|data :next ---|-----> (next node)
+---------+ +-------|-+---------+
Object of type pointer |
to LinkedList V
+---------+
|some data|
+---------+
Notice that this looks almost exactly the same as before. That's because
all that happened is that a pointer to the variable my_list was stored
in the argument named list.
Now list_append() presumably will add the new data to the front of the
list. Probably like this:
1 LinkedList * new_item;
2 new_item = malloc(sizeof *new_item); /* allocate a new LinkedList */
if (new_item != NULL)
{
3 new_item->data = data;
4 new_item->next = *list;
5 *list = new_item;
}
Now lets consider what each numbered line does:
(1) LinkedList * new_item;
This line defines a new object of type pointer to LinkedList called
new_item. The value of this variable is undefined. It doesn't point
to anything in the program yet.
+---------+
new_item:| ---|-----> ?
+---------+
(2) new_item = malloc(sizeof *new_item);
This line allocates a new object big enough to be a LinkedList struct
and stores its address in new_item. (i.e. new_item is set to point at
the new LinkedList node). The members of the LinkedList node (data and
next) have undefined values. They are pointers, but don't point at any
known object yet.
+---------+ +---------+---------+
new_item:| ---|----->|data :next ---|-----> ?
+---------+ +-------|-+---------+
|
V
?
(3) new_item->data = data;
This line makes the data member of the LinkedList node point to the
data that was passed as an argument to list_append():
+---------+ +---------+---------+
new_item:| ---|----->|data :next ---|-----> ?
+---------+ +-------|-+---------+
|
V
+---------+
(the argument called 'data') |new data |
+---------+
(4) new_item->next = *list;
This is where things start to get interesting, and it may be helpful
to break this line down further. From the last big diagram up before
the code, we know that list looks like this in memory:
+---------+
list:| | (this is the argument to list_append)
+-------|-+
|
V
+---------+ +----
my_list:| ---|----->| ...
+---------+ +----
now *list simply means "the thing that list is pointing to". You can
see that list is pointing to the object named my_list, which was
declared OUTSIDE the list_append() function. The line of code we
are considering is (once again):
(4) new_item->next = *list;
So now you should be able to see that this means "copy the value of
the thing list is pointing to into the 'next' member of the LinkedList
node". Since the thing list is pointing to is the variable my_list,
new_item->next will point to whatever my_list is pointing to:
+---------+ +---------+---------+
new_item:| ---|----->|data :next ---|-----+
+---------+ +-------|-+---------+ |
| |
V |
+---------+ |
|new data | |
+---------+ |
|
+---------+ |
list:| | +---------------------+
+-------|-+ |
| |
| |
V V
+---------+ +---------+---------+
my_list:| ---|----->|data :next ---|-----> (next node)
+---------+ +-------|-+---------+
|
V
+---------+
|some data|
+---------+
(5) *list = new_item;
Finally, this line copies the value of new_item into the thing that
list is pointing to. (i.e., it makes my_list point to the same thing
that new_item is pointing to):
+---------+ +---------+---------+
new_item:| ---|----->|data :next ---|-----+
+---------+ +-------|-+---------+ |
^ | |
| V |
| +---------+ |
| |new data | |
| +---------+ |
+-----+ |
+---------+ | |
list:| | | +---------------------+
+-------|-+ | |
| | |
| | |
V | V
+---------+ | +---------+---------+
my_list:| ---|---+ |data :next ---|-----> (next node)
+---------+ +-------|-+---------+
|
V
+---------+
|some data|
+---------+
Now this probably looks like a mess, but you can see that we have
now changed the value of my_list, which was declared in main().
Once the function list_append() is finished and returns, the
value in my_list will still be the updated value. The variable
new_item and the argument list will disappear when list_append()
returns, since they are local to the function list_append(). So
after list_append() returns, the objects in memory will look like
this:
+---------+ +---------+---------+
my_list:| ---|----->|data :next ---|-----+
+---------+ +-------|-+---------+ |
| |
V |
+---------+ |
|new data | |
+---------+ |
|
+---------------------+
|
|
V
+---------+---------+
|data :next ---|-----> (next node)
+-------|-+---------+
|
V
+---------+
|some data|
+---------+
