Two hash table questions

Question

I am working through SPELLER and have a few questions. When I create a new node node *newptr = malloc(sizeof(node)); do I need to say newptr1, newptr2, newptr3 and if so what is the best way of doing that?

My next question is more just to fully understand the code 100%. The last few lines of my code work but I'm just not completely sure I fully understand what it's doing. I left question marks where I would ask for a little help explaining what is happening.

Here is my code:

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <sys/resource.h>
#include <sys/time.h>


/*
***************************************************

Create a hash table with linked lists

A hash table is an array of buckets and each bucket is a linked list

Linked lists are made of nodes.  Each node has a value and a pointer to the next node.

*/



// Maximum length for a word
// (e.g., pneumonoultramicroscopicsilicovolcanoconiosis)
#define LENGTH 45

//Prototypes

int findPositionInAlphabet(const char *buffer);
void insert(int key, const char *buffer);

//Prototypes


int main(void){

    char *word = "justin";

    // hash the word into a spot
    //This will return the value of the position in the array of the first letter of word and
    //the position in the alphabet
    int positionInAlphabet = findPositionInAlphabet(word);

    // insert the word in table with hashed value
    insert(positionInAlphabet, word);


}//end main


int findPositionInAlphabet(const char *buffer)
{
    // assign a number to the alphaArray char of buffer from 0-25
    //This will take the letter make it lowercase then return it's numerical position in the alphabet
    //If the word was justin for example.  j is 106 and a is 97 so j minus a is 9 which in the array will
    //be the 10th character which is correct as the 9th slot in an array is the 10th position because
    //we start counting from 0
    return tolower(buffer[0]) - 'a';
}


void insert(int key, const char *buffer)//Pass in position in array and the word.  So an int and string
{

        typedef struct node
    {
        char word[LENGTH + 1];
        struct node *next;

    }
    node;

    /*
    The root will be an array the size of the alphabet plus one and all positions in it will be initialized
    to NULL. (Remember: the last element in a linked list always has to point to NULL or else we
    wouldn't know it was the end)
    */
    node *alphaArray[26] = {NULL};


    // try to instantiate or create a new node to insert word
    //At this point it has nothing to do with alphaArray as it hasn't been linked to anything yet

    node *newptr = malloc(sizeof(node));

    if (newptr == NULL)//Check to make sure the memory was allocated and a new pointer created
    {
        return;
    }

    strcpy(newptr->word, buffer);// place word in new node
    newptr->next = NULL;//Change pointer or "next" value to point to NULL

    printf("\n%s\n\n", newptr->word);


    if (alphaArray[key] == NULL)//Check if the value is equal to NULL at the array index from above
    {
       alphaArray[key] = newptr;//Change the value and pointer to the new node created newptr and that
                                //will be the new start of that buckets linked list

    }else{//If the array index is already pointing to a node

        node *predptr = alphaArray[key];//Create a new pointer of type node
                                        //and point it to alphaArray[key]

        while (true)//While the test remains true
        {

            if (predptr->next == NULL)//?????
            {
                predptr->next = newptr;//???????
                break;
            }


            predptr = predptr->next;//?????????
        }
    }
}

Answer 1

Hash tables are basically arrays of pointers, and the hash determines the index to use. Each of those pointers points to the first node of a linked list (or similar). A node of a linked list consists of data (the string) and a pointer to the next element. By convention, a NULL pointer means end of list. So you loop until you find the last element of the linked list (I just don't understand why you would want to do that, as that's O(n))

So your predptr variable is a cursor. You have it point to a node and advance it in the list by having it point to the next node. Move the condition into the while loop, that's where one would expect it, like while (predptr -> next != NULL). And maybe react on finding the word you're searching for (using like strcmp or similar) or after the loop. But if it is just for insertion, and you don't care about the position within the linked list (otherwise a tree instead of a linked list might be what you want), don't loop at all. Insertion in a linked list is easiest done at the front, just set the next pointer to the current list pointer, and replace that one with a pointer to the new node. One alternative for insertion at a specific point are pointers to pointers, as you then can treat an empty list like any other (if inserting at the front, it's much easier than that).