Solving pointers problems

February 01, 2017

It’s not secret that the hardest part in C programming is working with pointers. They seem simple - “A pointer is a variable that contains the address of a variable” (K&R Chapter 5). But when you start working with it, it’s so easy to mess up with stars and ampersands and arrows and stuff.

Most of the times you can get away with some shallow understanding of pointers. Indeed, even in production code you rarely see anything other than taking a pointer from malloc and passing it to some functions. And that’s where you are caught on C programming interviews questions because people love to ask tricky pointer questions. Like, write a function to reverse a linked list or do an in-order traversal of the binary tree.

I actually failed one interview back in 2012 because I failed to write a function that reverts a linked list. Yeah, I was depressed. Since then I promised myself that I will figure out how this shit really works. So this is my pointers epiphany post.

I think that the key to solving any pointers problem is to draw them correctly. Let me show you an example of linked list because it has a lot of pointers:

Each element is 2 squares - one for the “payload” variable and another for the pointer variable. Last pointer value is, of course, NULL. Head of the list is a pointer and it’s drawn in a “box” as any other variable.

It’s of paramount importance to draw pointers in boxes as any other variables and showing with the arrow where the pointer value points because this representation will help you to understand pointers code.

For example, here is the code to iterate over a linked list:

struct list *cur = head;
while (cur) {
    printf("cur is %p, val is %d\n", cur, cur->n);
    cur = cur->next;
}

You can kind of understand it by intuition but do you really understand why and how cur = cur->next works? Draw a picture!

cur = cur->next is doing its magic because arrow operator in C translates to this: cur = (*cur).next. First, you are dereferencing a pointer - that gives you a value under the pointer. Second, you get the value of next pointer. Third, you copy that value to the cur. This is how it allows you to jump over the pointers.

If it doesn’t click, don’t worry. Take your time, draw it yourself and make it sink.

Now, when it seems easy, let’s look at the double pointer or pointer to pointer.

Here is the same iteration but with double pointers:

struct list **pp = &head;
while (*pp) {
    cur = *pp;
    printf("cur is %p, val is %d\n", cur, cur->n);
    *pp = &(cur->next);
}

And here is the representation of it:

Double pointers are useful because they allow you to change the underlying pointer and value. Here is the illustration of why it’s possible:

Note, that *pp is a pointer, but it’s a different “box” than pp. pp points to the pointer, while *pp points to value.

All of this may not sound useful at first but, without double pointers, some code is much harder to read and some not even possible.

Take for example task of removing an element from a linked list. You have to iterate over the list to find the element to delete, then you have to delete it. Deleting an element from linked list is an update of adjacent pointers. This includes head pointer because you may need to remove the first element.

If you iterate over elements with a simple pointer, like in my first example, you have to have cur and prev pointers to make the previous pointer around deleted element. That’s OK, but you also need a special case if prev pointer is the head because head must be updated. Here is the code:

void list_remove(int i, struct list **head)
{
    struct list *cur = *head;
    struct list *prev = NULL;
    while (cur->next) {
        if (cur->n == i) {
            if (prev) {
                // Make previous pointer around deleted element
                prev->next = cur->next;
            } else {
                // prev == NULL means we removing head,
                // so shift head to next element.
                *head = cur->next;
            }
            free(cur);
        }

        // Iterating...
        prev = cur;
        cur = cur->next;
    }
}

It works but seems a bit complicated - it requires comments explaining what’s happening here. With double pointers it looks like a breeze:

void list_remove_pp(int i, struct list **head)
{
    struct list **pp;
    struct list *cur;

    pp = head;
    while (*pp) {
        cur = *pp;
        if (cur->n == i) {
            *pp = cur->next;
            free(cur);
        }
        pp = &((*pp)->next);
    }
}

Because we use double pointers, we don’t have a special case for head - with pp we can modify it just as any other pointer in the list.

So the next time you’ll find yourself struggle with some pointer problem - draw a picture showing pointers as any other variable and you’ll find the answer.

Just remember, there is no magic here - pointer is just a usual variable, but you work with it in an unusual way.