Pset 5 Speller Linked List Nodes

Question

I thought I got pointers but I don't fully understand a function that gets a new node for a linked list. I understand the theory behind Hash tables and chaining with linked lists but when it comes to implementing it in C, the syntax gets me confused.

// Represents a node in a hash table
typedef struct node
{
    char word[LENGTH + 1];
    struct node *next;
}
node;

// Hash table
node *table[N];

From what I understand, table is an array (of size N) that contains pointers to nodes, so each element in the array will eventually contain a memory address (e.g. 0x123) but does not contain the struct itself.

// Gets a node for a singly linked list
node *getNode(char *value)
{
    node *pNode = malloc(sizeof(node));
    if (pNode == NULL)
    {
        printf("Could not allocate memory for linked list node\n.");
        return pNode;
    }
    strcpy(pNode->word, value);
    // Set next to NULL pointer
    pNode->next = NULL;

    return pNode;
}

Consequently I don't understand pNode->next = NULL as doesn't node *pNode initialise the variable as a pointer to a node (which is just an address) and not the node struct. I would've thought it would be written as node pNode = malloc... as the next field within the struct would be a pointer to another node in the linked list.

Answer 1

Maybe there are a couple things that you haven't grasped yet.

First, creating a var and initializing a var are two very different actions.

A statement like node *pnode; creates a node var called pnode, a pointer to a node, which stores the address of a node. It is NOT initialized. Pointers are never initialized by default.

The statement node *pnode = NULL; both creates and initializes the pointer, by setting the value stored in the pointer to NULL.

The statement node *pnode = malloc(sizeof(node)); will create the var pnode, allocate the memory for a node, and will initialize pnode by storing the address of the node in pnode. However, it does NOT initialize any of the structure elements inside the node. That means that pnode->next remains uninitialized and just contains the garbage data that was in that physical memory location at the time. pnode->next still needs to be initialized with NULL or a valid memory address.

Does it make more sense now?