Having trouble understanding Linked List in C

Question

#define SIZE 100000

// 1. hash_function() is a function that return an int

// 2. snowflake_node 
typedef struct snowflake_node {
  int snowflake[6];
  struct snowflake_node *next; 
} snowflake_node;

// 3. main
int main(void) {
  static snowflake_node *snowflakes[SIZE] = { NULL }; 
  snowflake_node *snow;
  int n, i, j, hash_code;

  scanf(“%d”, &n);  
  for (i = 0; i < n; i++) {
    snow = malloc(sizeof(snowflake_node));
    if (snow == NULL) {
      fprintf(stderr, ”malloc error\n”);
      exit(1);
    }  
    for (j = 0; j < 6; j++)
      scanf(“%d”, &snow->snowflake[j]);
  
    hash_code = hash_function(snow->snowflake);
    snow->next = snowflakes[hash_code];

    // 4. This confuses me
    snowflakes[hash_code] = snow;  
  }  

  return 0; 
}

So, I am still trying to grasp how I can implement a Linked List in C. I quite understand that each node in a Linked List has a pointer to the next.

What confuses me is that number 4 part. Let's say that the first Snow has the hash_code of 21. This is going to be pointer to it.

It turns out that the second Snow also has the hash_code of 21. If we apply it to the code:

snowflakes[hash_code] = snow

Does that mean we replace the current Snow with the new one, instead of chaining them all together?

Answer 1

snowflakes array:

static snowflake_node *snowflakes[SIZE] = {NULL};

In-memory view of snowflakes array would be something like this:

snowflakes
     +----+
[0]  |  --|----> NULL
     +----+
[1]  |  --|----> NULL
     +----+
[2]  |  --|----> NULL
     +----+
       .
       .
       .
       .
     +----+
[N]  |  --|----> NULL
     +----+

 where value of N is (SIZE - 1).

Assume that, in the first iteration of for loop, allocating memory to pointer snow, the pointer returned by malloc() is 100 :

snow            snowflake_node
   +----+       +-------------------+
   | 100|------>|  |  |  | .... |   |
   +----+       +-------------------+
               100

Assume hash_function() returns value 2 for argument snow->snowflake:

hash_code = hash_function(snow->snowflake);
// hash_code value is 2

In this statement:

snow->next = snowflakes[hash_code];

snow->next will be assigned NULL because snowflakes[2] is NULL.

Now, this statement will execute:

snowflakes[hash_code] = snow;

which will assign the value of snow pointer to snowflakes[2] pointer. The snowflakes array in-memory view would be something like this:

snowflakes
     +----+
[0]  |  --|----> NULL
     +----+
[1]  |  --|----> NULL
     +----+     +-------------------+
[2]  | 100|---->|  |  |  | .... | --|-->NULL 
     +----+     +-------------------+
       .       100                |
       .                          +-> next pointer of snowflake_node
       . 
       .
     +----+
[N]  |  --|----> NULL
     +----+

Now, assume that, in the second iteration of for loop, the pointer returned by malloc() is 200:

snow            snowflake_node
   +----+       +-------------------+
   | 200|------>|  |  |  | .... |   |
   +----+       +-------------------+
               200 

and hash_function() returns value 2 for argument snow->snowflake.

In this statement:

snow->next = snowflakes[hash_code];   // value of hash_code is 2

snow->next will be assigned the value of pointer snowflakes[2] which is 100 as the pointer snowflakes[2] pointing to memory location 100.

this statement:

snowflakes[hash_code] = snow;

will assign the value of snow pointer to snowflakes[2] pointer. The snowflakes array in-memory view would be something like this:

snowflakes
     +----+
[0]  |  --|----> NULL
     +----+
[1]  |  --|----> NULL
     +----+     +-------------------+   +-------------------+
[2]  | 200|---->|  |  |  | .... |100|-->|  |  |  | .... | --|---> NULL 
     +----+     +-------------------+   +-------------------+
       .       200                      100
       .
       . 
       .
     +----+
[N]  |  --|----> NULL
     +----+

Answer 2

This declaration

static snowflake_node *snowflakes[SIZE] = {NULL};

declares a hash table of the size SIZE. Each entry of the table represents a singly linked list that is designed to store nodes with the same calculated hash value. Initially all the linked lists are empty because their pointers to header nodes are initialized by null pointers.

Each new node of the selected entry of the hash table (of the selected linked list)

hash_code = hash_function(snow->snowflake);

is added to the beginning of the list. That is its data member next is set to point to the current header node of the selected list

snow->next = snowflakes[hash_code];

and then the new node becomes the header node

snowflakes[hash_code] = snow;

That is the selected entry of the hash table now contains a pointer to the newly added node for the calculated hash value.

To make the code more clear you could write a separate function named like for example push or push_front that would add a new node for the selected linked list according to the calculated hash value.

Try to do that yourself as an exercise.

Answer 3

Look at the pair of statements:

snow->next = snowflakes[hash_code];
snowflakes[hash_code] = snow;

The first one sets the next field of the new node to the head of the list at snowflakes[hash_code]. The second one sets snowflakes[hash_code] to the new node. So any existing linked list pointed to by the old snowflakes[hash_code] now follows the new node. Nothing is lost. This is a "push" operation: The new node is "pushed" onto the head of the list.