Hash Table inserting values in reverse [C]

Question

I was following a tutorial on hash tables, and I created this code below. The problem is that when I try to insert values, I succeed but if I print the table, it seems that the lists are in reverse.

At first, I thought that I was passing the wrong value to the function printhashtable() but it doesn't seem so, as it prints all the correct elements, but in reverse. If, for an instance, I passed the last element of the list, with the condition i!= NULL, I would get an empty print.

What I think now is that I am somehow giving the tail pointer, and the 'next' field actually goes backwards.

    #include <stdio.h>
#include <stdlib.h>

int a;
int b;
int count_collisions;

// Linked list
typedef struct _list{
    int value;
    struct _list *next;
} list;


// Hash Table Structure
typedef struct _hash_t {
    int size; // Table Size
    list** table; // Table elements
} hash_t;


// Creating the HASH function
int hash(int x, int a, int b, int len) {
int h;
h=((((a*x)+b)%999149)%len);
return h;
}


// Creating the table
hash_t* CreateTable(int size) {

hash_t* newtab;

if (size < 1) return NULL; // This size is not valid

newtab = malloc(sizeof(hash_t));  // ALlocate memory for the table structure
if (newtab == NULL) return NULL; // Checking if the malloc went good

newtab->table = malloc(sizeof(list*)*size); // Allocating memory for the table
if (newtab->table == NULL) return NULL; // Checking if the malloc went good

int i;
for (i=0; i<size; i++) {
    newtab->table[i] = NULL; // Initialize the elements of the table
}

newtab->size = size; // Setting the size of the table

return newtab;
}


// Searching for a value
list* Search(int x, hash_t* hashtable) {

list* list;
int hashval = hash(x, a, b, hashtable->size);

if (hashtable == NULL) {
    return NULL;
}

for (list = hashtable->table[hashval]; // We start from the correct list, using the hash function
     list != NULL; list = list->next) {
    if (list->value == x) {
        return list;
    }
}

return NULL;
}


 // Insert a value
void Insert(int x, hash_t* hashtable) {

list* list;
int hashval = hash(x, a, b, hashtable->size);

list = malloc(sizeof(list)); // Allocate memory for the list
list->value = x;
list->next = hashtable->table[hashval];
hashtable->table[hashval] = list;

}


// Function that prints a list
void printList (list* list) {
struct _list* i;
for (i=list; i!= NULL; i = i->next) {
    printf("%d ", i->value);
}
}



// Function that prints hashtable
void printHashTable(hash_t* hashtable, int size) {
int i;
for (i=0; i<size; i++) {
    printf("\nPosition: %d | list: ", i);
    printList(hashtable->table[i]);
}

}



int main () {

int size;
scanf("%d", &size);
scanf("%d", &a);
scanf("%d", &b);

hash_t* table = CreateTable(size);
int i, x;
for (i=0; i<size; i++) {
    scanf("%d", &x);
    Insert(x, table);
}

printf("Hash Table created is: ");
printHashTable(table, size);

printf("\n");


return 0;
}

Example test set:

Input:

5    // 5 elements
2    // a = 2
4    // b = 4
3    // h(3) = 0
12   // h(12) = 8
97   // h(97) = 8
18   // h(18) = 0
98   // h(98) = 0

Output:

// hash table:
//  0 -> 3 18 98
// 1 -> NULL
// 2 -> NULL
// 3 -> NULL
// 4 -> NULL
// 5 -> NULL
// 6 -> NULL
// 7 -> NULL
// 8 -> 12 97
// 9 -> NULL

What I get at 0 and 8 is:

0 -> 98 18 3
8 -> 97 12

What could be wrong? Thanks in advance P.S. Sorry for my bad english

EDIT: I think that maybe in the Insert function I don't separate the cases in which the list is empty or not. Am I right?

Answer 1

From your insert function:

list->value = x;
list->next = hashtable->table[hashval];
hashtable->table[hashval] = list;

you assign list->next as the current list, and then assign the hash table entry to be your newly made list. This is an insert at head.

Your list is built up like (showing table[0] only):

0 -> 3
0 -> 18 3
0 -> 98 18 3