Hashtables Chaining with Doubly Linked Lists - Dieptranivsr/DroneIVSR GitHub Wiki

Implementing hash table using Chaining through Doubly Linked List is similar to implementing Hashtable using Singly Linked List. The only difference is that every node of Linked List has the address of both, the next and the previous node. This will speed up the process of adding and removing elements from the list, hence the time complexity will be reduced drastically.

Example:

If we have a Singly linked list:
1 -> 2 -> 3 -> 4
If we are at 3 and there is a need to remove it, then 2 need to be linked with 4 and as from 3, 2 
can’t be accessed as it is singly linked list. So, the list has to be traversed again i.e O(n), 
but if we have doubly linked list i.e.

1 <-> 2 <-> 3 <-> 4
2 & 4 can be accessed from 3, hence in O(1), 3 can be removed.

Below is the implementation of the above approach:

// C++ implementation of Hashtable
// using doubly linked list
#include <bits/stdc++.h>
using namespace std;

const int tablesize = 25;

// declaration of node
struct hash_node {
    int val, key;
    hash_node* next;
    hash_node* prev;
};

// hashmap's declaration
class HashMap {
public:
    hash_node **hashtable, **top;

    // constructor
    HashMap()
    {
        // create a empty hashtable
        hashtable = new hash_node*[tablesize];
        top = new hash_node*[tablesize];
        for (int i = 0; i < tablesize; i++) {
            hashtable[i] = NULL;
            top[i] = NULL;
        }
    }

    // destructor
    ~HashMap()
    {
        delete[] hashtable;
    }

    // hash function definition
    int HashFunc(int key)
    {
        return key % tablesize;
    }

    // searching method
    void find(int key)
    {
        // Applying hashFunc to find
        // index for given key
        int hash_val = HashFunc(key);
        bool flag = false;
        hash_node* entry = hashtable[hash_val];

        // if hashtable at that index has some
        // values stored
        if (entry != NULL) {
            while (entry != NULL) {
                if (entry->key == key) {
                    flag = true;
                }
                if (flag) {
                    cout << "Element found at key " << key << ": ";
                    cout << entry->val << endl;
                }
                entry = entry->next;
            }
        }
        if (!flag)
            cout << "No Element found at key " << key << endl;
    }

    // removing an element
    void remove(int key)
    {
        // Applying hashFunc to find
        // index for given key
        int hash_val = HashFunc(key);
        hash_node* entry = hashtable[hash_val];
        if (entry->key != key || entry == NULL) { 
            cout << "Couldn't find any element at this key " << key << endl;
            return;
        }

        // if some values are present at that key &
        // traversing the list and removing all values
        while (entry != NULL) {
            if (entry->next == NULL) {
                if (entry->prev == NULL) {
                    hashtable[hash_val] = NULL;
                    top[hash_val] = NULL;
                    delete entry;
                    break;
                }
                else {
                    top[hash_val] = entry->prev;
                    top[hash_val]->next = NULL;
                    delete entry;
                    entry = top[hash_val];
                }
            }
            entry = entry->next;
        }
        cout << "Element was successfully removed at the key " << key << endl;
    }

    // inserting method
    void add(int key, int value)
    {
        // Applying hashFunc to find
        // index for given key
        int hash_val = HashFunc(key);
        hash_node* entry = hashtable[hash_val];

        // if key has no value stored
        if (entry == NULL) {
            // creating new node
            entry = new hash_node;
            entry->val = value;
            entry->key = key;
            entry->next = NULL;
            entry->prev = NULL;
            hashtable[hash_val] = entry;
            top[hash_val] = entry;
        }
      
        // if some values are present
        else {
            // traversing till the end of
            // the list
            while (entry != NULL)
                entry = entry->next;

            // creating the new node
            entry = new hash_node;
            entry->val = value;
            entry->key = key;
            entry->next = NULL;
            entry->prev = top[hash_val];
            top[hash_val]->next = entry;
            top[hash_val] = entry;
        }
    cout << "Value " << value << " was successfully added at key " << key << endl;
    }
};

// Driver Code
int main()
{
    HashMap hash;
    hash.add(4, 5);
    hash.find(4);
    hash.remove(4);
    return 0;
}

Output:

Value 5 was successfully added at key 4
Element found at key 4: 5
Element was successfully removed at the key 4
⚠️ **GitHub.com Fallback** ⚠️