Wednesday, October 12, 2011

Using Pointers to Pointers for Linked Lists

I was reading up on Linked Lists and came across a great description on the meaning of Pointers to Pointers. As pointers and I have a love/hate relationship, I found this post very insightful and easy to understand. In the code I wrote to create and print a Linked List, I found it necessary to use a Pointer to a Pointer because the pointer to the "head" node of a singly linked list needs to be defined (and accessible) by the main() routine.
#include <iostream>
#include <cstdlib>

using namespace std;

typedef struct Node {
    int value;
    struct Node *next;
    struct Node *prev;
} NodeType;

void addNode(struct Node **head, int value);
void printList(char *listName, struct Node *head);

int main() {
    NodeType *head;
    head = (struct Node*)NULL;

    addNode(&head, 1);
    addNode(&head, 10);

    printList("myList", head);

    return 0;
}

void addNode(struct Node **head, int value) {
    NodeType *temp;
    NodeType *cur;

    temp = (NodeType*)malloc(sizeof(NodeType));
    temp->next = NULL;
    temp->prev = NULL;
    if(*head == NULL) {
        *head = temp;
        temp->value = value;
    } else {
        for(cur = *head; cur->next != NULL; cur = cur->next);
        cur->next = temp;
        temp->prev = cur;
        temp->value = value;
    }
}

void printList(char *listName, struct Node *head) {
    NodeType *temp;
    cout << listName << endl;
    for(temp = head; temp != NULL; temp = temp->next) {
        cout << temp->value << endl;
    }
    cout << "End" << endl;
}