RSS

Tag Archives: Data structure

Linked Lists and Pointers – struct node**

As I was reading up on linked lists is C and C++, I challenged myself to write an implementation for the data structure itself (i.e. the nodes) and the list operations (push, pop, etc). On my first go, I wrote the following:

struct node
{
    int data;
    struct node* next;
};

void push (struct node* head, int data)
{
    struct node* newNode = malloc(sizeof(struct node));

    newNode->data = data;
    newNode->next = head;

    head = newNode;
}

The node implementation is correct, of course, but the implementation for push is wrong. Any guesses?

Here is the correct implementation for push:

void push (struct node** head, int data)
{
    struct node* newNode = malloc(sizeof(struct node));

    newNode->data = data;
    newNode->next = *head;

    *head = newNode;
}

My guess would be that your first question upon reading this code is: “What is this struct node** business?” Well, that was my question, and it took me a few articles to figure it out. I first came across the problem in a programming interview book, Programming Interviews Exposed, but it took me until reading Nick Parlante’s article on Linked Lists in the Stanford CS Library to really understand it. I’ll save you the trouble of reading the whole document (although it is worth a read), but the gist of it is this.  When you pass a parameter to a function, whether it’s a primitive, composite (array), struct, or pointer, the function allocates its own stack memory for each of the parameters upon the function call, just as it does for any other local variable.  What this means for our purposes is that the first (incorrect) implementation of push only changes the value of the local variable head and not the value of the pointer that you originally passed, because in this case, head is a pointer to the struct data, not a pointer to the pointer-to-struct.  If you instead pass struct node** head, head then is a pointer to the pointer-to-struct.  By dereferencing head, you then can change the memory address stored at that memory location.

Moral of the story?  Pass a pointer to the data typeof the data that you want to change.  So if that’s an int, pass an int*, if that’s a pointer-to-int, pass an int**.  Seems easy enough…hope I follow my own advice!

 
Leave a comment

Posted by on January 2, 2012 in General, Programming

 

Tags: , , , , , , , , , ,