1

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?

2
  • The above code is wrong. hashtable is an array, from where all the linked lists start. There is no useful logic saying that the next node will be the head of the list, as the head is the first node. – ChrisG Aug 26 '15 at 18:01
  • That code is correct. See my answer. – curiouskiwi Aug 26 '15 at 21:53
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.

1
  • Wow, thnx so much Brenda. You were so helpful. So just to be sure, when i declare the hashtable[x] i create an array of x nodes. Then if a certain node is already occupied, then the first line makes the node that we want to insert point to the current head of the linked list. Then the second line makes the new node that we want to insert the new head of the linked list ? – FOTIOS EMERY Sep 1 '15 at 7:31

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .