Pset5 load, accessing head node in linked list

Question

I've decided on a hash table for load in pset5. There is one thing that I have no clue how to implement, though.

Here is my load function. When a collision occurs, I need to be able to access the old node my new node is colliding with, so I can link them and create a singly linked list. I wrote a comment to indicate where I need help and give more detail.

  /**
   * Loads dictionary into memory.  Returns true if successful else false.
   */
bool load(const char* dictionary)
{
   // open the dictionary and check if it opens correctly
   FILE* diction = fopen(dictionary, "r");
   if (diction == NULL)
{
    printf("Could not load dictionary.\n");
    unload();
    return false;
}

//the array that will store the dictionary
char* theArray[65536];

//setting to null
for(int k = 0; k < 65536+1; k++)
{
    theArray[k] = NULL;
}
//scanning through the dictionary word by word.
while(fgetc(diction)!= EOF)
{
    node* node_1 = calloc(1, sizeof(node));

    node_1->next = NULL;



    fscanf(diction, "%s", node_1->word);
   //this is used later for size function
    sizer++;


    //hashing (returns value up to 65536)
    int hashValue = hash_it(node_1->word);
//if the location at the array is NULL, put the node there
if(theArray[hashValue] == NULL)
{
    theArray[hashValue] = node_1->word;
}
else //if a node exists at the location.
{

    /*
    I know here I need to put the new node after the existing one(s) by setting the last node's pointer(next)
    to point to the new one
    I need something like "get the node at theArray[hashValue], 
    and get its pointer (next) to point to the new node I want to add."
    */
}

}

return true;

}

The hash function that I used can be found here: https://www.reddit.com/r/cs50/comments/1x6vc8/pset6_trie_vs_hashtable/ I used 65536 throughout the load function, because that is the maximum value the Hash function produces.

Answer 1

There are two approaches to this. If you want to add the new node to the end of the list, you need to walk the list to the end. Create a while loop that looks for the last element in the list. In other words, node->next == null. When you get there, set node->next = new node.

The more efficient method is to add the new node to the beginning of the list. Set new_node->next = first node in the list, and then set root->next = new node.

If this answers your question, please click on the check mark to accept. Let's keep up on forum maintenance. ;-)