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