calgorithmdata-structureshashtablesingly-linked-list

Having trouble understanding Linked List in C


#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?


Solution

  • 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
         +----+