Pset 5 Speller Linked List Nodes

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.

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?

• Ah I see, thank you for clarifying that. So initially we want to loop through our hash table to set all the pointers to null, then when we call `getNode` we want to update the pointer in the table to point at the newly created node. So does that make pNode just a temporary pointer in essence? I've tried making a schematic in order to try understand this better, is that along the right lines? – docnocturnal Jan 24 '20 at 23:17