Linked list of Linked lists in C

Question

I have a project in C that I need to create a chained hash table with linked lists. Actually as I see it is a linked list with linked lists as nodes. So the data structure of each node in each entry in hash table should be:

typedef struct node {
    int value;
    int counter;
    struct node *next;
} t_listnode;

and then the hash table that should contain the above nodes is stated as below:

typedef struct {
    t_listnode *head;
    t_listnode *tail;
} t_htentry;

I have drained my little brain (first time touching linked lists) and can't figure how to create the hash table and how to enter data in each entry. Any help would be highly appreciated.

Thank you!

Answer 1

This answer assumes you're using an outer linked list and an inner linked list:

First, to make your life easier, you should make some methods for your inner linked list node:

• insert(): Iterate to the end of the linked list and add a new node
• find(): Iterate through the list and see if your value is what you're looking for

Next, you'll want to implement the relevant methods for a Hash Table:

• get() or find(): hash the element you're looking for to get the index in the outer linked list, and then iterate through the inner linked list at that index to find the element you're looking for
• put() or insert(): hash the element you're looking for to get the index in the outer linked list, where you'll append to the end of the inner linked list at that index

Most importantly for a hash table, you'll want to create your hash() function. In this case, since your data appears to be an int, your hash function should take in an int and then hash that int to a given spot in the outer linked list.

Since you're using a linked list to represent the outer structure of the hash table, you will definitely want to create an at() method that iterates through the outer linked-list (t_htentry) and returns a pointer to the index of the inner linked list (in your case, a t_listnode node).

Example:

We want to add 10, 201, 302 into our hash table.

First step is to pre-allocate the t_htentry* hashtable[PRIME_NUMBER] to a prime size -- i.e., let's say we start with an array of size 5 (each index in the array is denoted by [ ]). The t_listnode* head is already in each of the t_htentry*'s, (each t_htentry* is denoted by ( ), the head nodes are denoted by *, and the tail nodes are denoted by t).

  0      1      2      3      4  -- indexes
[(*)]  [(*)]  [(*)]  [(*)]  [(*)] -- t_htentry*[] with t_listnode* head in each index
  |      |      |      |      |
  v      v      v      v      v  -- pointer
 (t)    (t)    (t)    (t)    (t) -- t_listnode* tail

Second step is to hash our first data point - 10.

int idx = hash(10); //-> 2

Third step is to locate idx (2) in our outer list. hashtable[idx] will give us a constant time lookup!

Fourth step is to now append a node with the data point 5 to that list.

// append value to hashtable[idx] (where "next" points to TAIL)
insert(hashtable[idx], 5);

[(*)]  [(*)]  [(*)]  [(*)]  [(*)]
  |      |      |      |      |
  |      |      v      |      |
  |      |     (5)     |      |
  |      |      |      |      |
  v      v      v      v      v
 (t)    (t)    (t)    (t)    (t)

Fifth step, we now proceed to our next data point, 201. Let's say 201 hashes to idx = 2 as well. (From this point on, I'm omitting drawing the [(t)]'s for all indices that don't have any data in them, but note that they are still there.)

idx = hash(201); //-> 2
t_listnode * spot = positionAt(hashtable, idx);
insert(spot, 201);

[(*)]  [(*)]  [(*)]  [(*)]  [(*)]
                |
                v
               (5)
                |
                v
               (2)
                |
                v
               (t)

Next step, we'll move to our last data point, 302. Let's say 302 hashes to idx = 0.

 idx = hash(302); //-> 0
 t_listnode * spot = positionAt(hashtable, idx);
 insert(spot, 302);

 [(*)]  [(*)]  [(*)]  [(*)]  [(*)]
   |             |
   v             v
 (302)          (5)
   |             |
   v             v
  (t)           (2)
                 |
                 v
                (t)

where,

hash would look like one of these examples

insert looks like

void insert(t_htentry * bucket, int value) {
  // copy spot to a new t_listnode* and iterate until spot->next is NULL
  // (i.e., t_htentry* tmp = bucket; tmp = bucket->head->next)
  // create a new node with t_listnode->value set to value
  // set the current spot's next to the new node
  // set the new node's next to the TAIL node
}

find looks like

bool find(hashtable, int value) {
  // hash "value" and go to hashtable[idx] as before
  // iterate through hashtable[idx]'s linked list as before using a copy
  // of that t_htentry*.
  // if the node that you're on has ->value == value, return true
  // else continue until you're at the end of the list, and return false
}

The performance for this implementation will be O(1) amortized for find and insert. It's important that you understand why.