Lab46 Wiki

> I got a bit hung up with the pointers.
>

This seems to be the start of the fun. I hope you're spending lots of time drawing pictures… because this is a highly abstract concept that seems to blows people's minds until they cross some threshold of time trying to wrap their heads around it.

As you can probably guess, all this stuff is pointer-heavy, and it is only going to increase as time goes by (I intentionally have been taking it slow on the pointer usage, trying to ease everyone in).

But ultimately, remember a pointer is just a memory variable. It doesn't directly contain data, it contains an address. So in that way it is not different than any other variable (it has a name, an address, and contents). For some reason people get it warped in their heads that pointers are somehow different, and therefore difficult… part of the purpose of this course is to break down and through that self-imposed mental barrier, and until that happens, everything is wild and seemingly getting wilder. Then post-enlightenment, everything seems amazing.

> I need help understanding how the user input works.. 
>

User input is done the same as any existing user input you've done– via scanf().

The trick is, you need to do all input prior to, and entirely outside of these linked list functions- the aim is for functions like insert(), append(), and getNode() to be generic so that we can use them in all manners of situations.

> For example the function prototype you gave us.. 
> Node *append(Node *start, Node *given, Node *newNode); I don't quite
> understand the values being passed in.. same with the **indicated
> for the *getnode function.
>

append() (and insert() too, for that matter) take 3 parameters:

1. a pointer to the start of the list
2. a pointer to the node we wish to perform the operation on (insert before, append after)
3. a pointer to a newly allocated node we wish to insert or append into the list (at the “given” location)

In the case of getNode(), we are taking an “indicated” node out of the list (severing its connections to/from the list, but in no way leaving the list broken. For technical reasons (a function can only return one thing), we pass in “indicated” as a double pointer, to enable “pass by reference/address” for our pointer.

Here is what append would do…

Let's say we had the following list (built from previous calls to insert() and append():

    start -> 5 -> 2 -> 12 -> 27 -> 1 -> NULL

And we wanted to append a new node after the node containing 12.

We'd ask the user what node they wanted to append after (applying positions to each of the nodes… the one with the 12 in it, assuming we start from 0, would be node #2 (not to be confused with the node containing 2, that is node #1). We would loop from the start of the list using a temporary node pointer (tmp), stopping once we arrive at our intended destination.

                       tmp
                        |
                        V
    start -> 5 -> 2 -> 12 -> 27 -> 1 -> NULL

We'd then ask the user what we'd like in our new node (let's say a 23). Allocate memory for the node, and put that input in the node.

Our scenario would then look like this (notice tmp2 is not connected to the list at all):

                       tmp
                        |
                        V
    start -> 5 -> 2 -> 12 -> 27 -> 1 -> NULL

               tmp2 -> 23

We now have what we need to call append():

    start = append(start, tmp, tmp2);

… we pass it the start of the list, a pointer to the node we wish to append after, and a pointer to the new node we wish to place in the list after the given location.

At no time can we leave any portion of the list unconnected… if it is broken, access to it is lost. We have a memory leak. So care must be taken in the steps pursued in accomplishing each list operation.

In this case, our newNode pointer should start the connection into the list by pointing its next pointer to the node following the given pointer (given's next). Once we do that, the list scenario should look like this:

                      given
                        |
                        V
    start -> 5 -> 2 -> 12 -> 27 -> 1 -> NULL
                              ^
              newNode -> 23 __/

newNode is not yet IN the list, however– if we were to fly through the list starting at start, and going until we're NULL, we'd never encounter that 23.

So once we have something pointing at the rest of the list, we are free to disconnect the pointer between given and given's next, and reassign it point to newNode. Then we have the following:

                      given
                        |
                        V
    start -> 5 -> 2 -> 12      27 -> 1 -> NULL
                        |      ^
                        V      |
             newNode -> 23 ____/

And voila, we have a connected list (all the above diagrams, including step-by-step changes in arrows, should be regularly drawn out on paper as you work on these, to get a better feel for the steps necessary).

We can then return a pointer to the start of the list (a local node pointer called start)

Back in the calling function, we assign the return value from append() to a local node pointer (which also happens to be called start).

> What is the difference
> between a regular function and a
> pointer [to a] function [(aka function pointer)] such as *append();
>

Well, a pointer points to something.

We can have pointers to variables, and pointers to functions.

Those functions you mentioned are not function pointers… they are functions returning pointers (again, a pointer is just like any other variable). They are just like any other function you've ever made (they take parameters, they return a value).

A function pointer (just for reference) would be something like this:

Node *(*operation)(Node *, Node *, Node *);

This would be a function prototype for a function pointer called operation (notice the parenthesis specifically hugging an asterisk to the function name).

Function pointers, as they are meant to point to some other function, need to match the type, or “fingerprint” of the function. As my example will point operation() at either insert() or append(), its return type and parameters need to be the same.

To point operation() at append(), we merely have to do this:

operation = &append;

Then we can call operation() as a function, and it'll call whatever function it points to (append() at present, but if we had pointed it at insert() it would call that one instead):

start = operation(start, tmp, tmp2);

We don't (yet?) need any function pointers in our linked list stuff… this was just a “the more you know” informational segment, attempting to show you how much of a non-issue pointers are– they are merely variables that contain addresses (they point to things, vs. contain things).