Double pointers as function arguments

One of the topics that confuse programmers the most about memory management is the usage of double pointers when modifying references (addresses) inside functions. This problem is often encountered when trying to modify non-random-access data structures, like linked lists, queues, stacks, trees, graphs, etc.

The explanation can be quite simple. I will do it by explaining how the removal of the head of a linked list is done.

Let’s assume we define list nodes like this:

typedef struct _node {
    int x;
    struct _node * next;
} node;

And we dynamically create three elements, always keeping a reference to the head with a pointer:

void insertNode(node ** head, int x){ ... }
void deleteNode(node ** head, int x){ ... }

int main()
{
    node * head;
    insertNode(&head, 55);
    insertNode(&head, 66);
    insertNode(&head, 77);
    deleteNode(&head, 55);
    return 0;
}

Graphically, this is how we can imagine the 3 nodes in the list. The value above each square is the address where each struct resides. Inside, the int value and the pointer to the next node.

Below, you can see the head pointer, which resides in memory address 0x721, and its value is the pointer to the 0x100 address, the first element in the list.

  0x100          0x203          0x982
---------      ---------      ---------
|   55  |      |   66  |      |   77  |
| 0x203 |  ->  | 0x982 |  ->  |  NULL | 
---------      ---------      ---------
    ^
    |
  0x721
---------
| 0x100 |
---------

Pointers are used to modify the element located in the address that the pointer holds. For example, we can use the head pointer to modify the element in the address 0x100 right now, but that’s it. What if we want to change the 0x100 address to 0x203, to make the second element in the list the new head? Using a simple pointer, we cannot. That’s why we need to use double pointers:

  0x100          0x203          0x982
---------      ---------      ---------
|   55  |      |   66  |      |   77  |
| 0x203 |  ->  | 0x982 |  ->  |  NULL | 
---------      ---------      ---------
    ^
    |
  0x721
---------
| 0x100 |
---------
    ^
    |
---------
| 0x721 |
---------

Now we’re talking! Since we called deleteNode after creating the 3 nodes, and we ask to delete the first element (the one that holds the value 55), the head pointer will have to be modified, and should now point to the second element in the list. Using the reference to the head pointer, we now can modify the address inside head: change 0x100 to 0x203. And everything was done inside deleteNode.

Assuming that we DO NOT free the memory of the first node on purpose, this is how our list will end up after deleting the first element:

  0x100          0x203          0x982
---------      ---------      ---------
|   55  |      |   66  |      |   77  |
| 0x203 |  ->  | 0x982 |  ->  |  NULL | 
---------      ---------      ---------
                   ^
                   |
  0x721            |
---------          |
| 0x203 |  --------
---------
    ^
    |
---------
| 0x721 |
---------

As you can see, the value inside the head pointer in address 0x721 has been modified: it now points to the address of the second node, which resides in address 0x203.

In summary: Whenever you need to modify memory addresses to make them point somewhere else, use double pointers. If you are just going to traverse a data structure and not modify anything, use a simple pointer.

And remember: the correct thing would be to free the memory of any element you decide to delete. You don’t want to end up with memory leaks all over the place.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: