How to add a new node in the linked list

Question

Now that I am done with pset5 I would like to understand how to add a new node to a linked list. While building the pset, I blindly used Zamyla's guidelines on how to add a new node to a linked list and it works just finds but I want to really comprehend the mechanism behind it.

Code I use to add new node:

new_node -> next = hashtable[i];
hashtable[i] = new_node; 

Can someone please thoroughly explain how the above code makes sense, meaning that how can this code add a new node without losing the list?

Answer 1

Here's how it works. Your hashtable is an array of node*s (an array of pointers to nodes).

Let's say that hashtable[1] is pointing to a node containing the word "apple" at address 0x1001. You have just created a new node for the word "apples" (at address 0x1002) and it hashes to the same bucket (1). So you need to add that node to the linked list.

The current status:

hashtable[1] is a pointer to 0x1001

We want to add the new_node 0x1002 to that list so:

new_node->next = hashtable[1];  //  0x1002->next points to 0x1001
hashtable[1] = new_node;        //  hashtable[1] now points to 0x1002

ie

hashtable[1] = a list of  "apples" -> "apple"

Now we want to add "applesauce", so we create a node and it has address 0x1010.

new_node->next = hashtable[1]  // 0x1010->next points to 0x1002
hashtable[1] = new_node       // 0x1002 now points to 0x1010

result:

hashtable[1] has list of "applesauce" -> "apples" -> "apple"

Here is one of the slides from the discussion about linked lists. Perhaps it helps too?

point new_node next to the top of the list, then point head to the new node

In that picture, you have just pointed new_node->next to the first item in the list (i.e., new_node->next = hashtable[i]. The next step (not shown) is to change "head" to point to the new_node (i.e., hashtable[i] = new_node)

-Brenda.