Dictionary Implementation using HashTable with external chaining using Linked List | Add a Node | Update a Node | Delete a Node
Problem Statement:Implement all the functions of a dictionary (ADT) using hashing and handle collisions using separate chaining using linked list. Data: Set of (key, value) pairs, Keys are mapped to values, Keys must be comparable, Keys must be unique. Standard Operations: Insert (key, value), Find(key), Delete(key)
Note:- Scroll horizontally to see the full line of code.
#include <iostream>
using namespace std;
class node
{
string key;
string value;
node *next;
public:
node(string key, string value)
{
this->key = key;
this->value = value;
next = NULL;
}
friend class Dictionary;
};
class Dictionary
{
node *hashTable[10];
public:
Dictionary()
{
for (int i = 0; i < 10; i++)
{
hashTable[i] = NULL;
}
}
int hashFunction(string key);
void addNode(string key, string value);
void search(string key);
void display();
void deleteNode(string key);
void update(string key, string value);
};
int Dictionary::hashFunction(string key)
{
int address = 0;
for (int i = 0; i < key.length(); i++)
{
address += key[i];
}
// cout << "Address for " << key << " is " << address << endl;
return address % 10;
}
void Dictionary::addNode(string key, string value)
{
int address = hashFunction(key);
node *temp = new node(key, value);
if (!hashTable[address])
{
hashTable[address] = temp;
return;
}
else
{
node *current = hashTable[address];
while (current->next)
{
current = current->next;
}
current->next = temp;
return;
}
}
void Dictionary::display()
{
for (int i = 0; i < 10; i++)
{
if (hashTable[i])
{
node *current = hashTable[i];
while (current)
{
cout << "Key: " << current->key << endl;
cout << "Value: " << current->value << endl;
cout << endl;
current = current->next;
}
cout << endl;
}
}
}
void Dictionary::search(string key)
{
int address = hashFunction(key);
int count = 0;
node *current = hashTable[address];
while (current)
{
if (current->key == key)
{
count++;
cout << "Key: " << current->key << endl;
cout << "Value: " << current->value << endl;
cout << "no. of comparisions are: " << count << endl;
return;
}
else
{
current = current->next;
count++;
}
}
if (!current)
{
cout << "Key doesn't exist!!!" << endl;
}
}
void Dictionary::deleteNode(string key)
{
int address = hashFunction(key);
// if node to be deleted is only node in linked list
if (!hashTable[address]->next)
{
node *current = hashTable[address];
delete (current);
current = NULL;
hashTable[address] = NULL;
cout << "Entry Deleted Successfully!!!" << endl;
return;
}
node *current = hashTable[address];
node *parent = NULL;
while (current)
{
if (current->key == key)
{
node *temp = current;
// if node to be deleted is leaf node in linked list chain
if (!current->next)
{
if (parent)
{
parent->next = NULL;
}
delete (current);
current = NULL;
cout << "Entry Deleted Successfully!!!" << endl;
return;
}
// if node to be deleted is inbetween in linked list chain
while (current->next)
{
parent = current;
current = current->next;
}
temp->key = current->key;
temp->value = current->value;
parent->next = NULL;
delete (current);
current = NULL;
cout << "Entry Deleted Successfully!!!" << endl;
return;
}
else
{
parent = current;
current = current->next;
}
}
if (!current)
{
cout << "Key doesn't exist!!!" << endl;
}
}
void Dictionary::update(string key, string value)
{
int address = hashFunction(key);
node *current = hashTable[address];
while (current)
{
if (current->key == key)
{
current->value = value;
cout << "Entry Updated Successfully!!!" << endl;
return;
}
else
{
current = current->next;
}
}
if (!current)
{
cout << "Key doesn't exist!!!" << endl;
}
}
int main()
{
Dictionary dict;
char cont = 'y';
string key, value;
while (cont == 'y')
{
cout << "<----------Menu----------->" << endl;
cout << "1.Enter Entries." << endl;
cout << "2.Display Dictionary." << endl;
cout << "3.Search Entry." << endl;
cout << "4.Delete Entry." << endl;
cout << "5.Update Entry." << endl;
int choice;
cout << "Enter Choice: ";
cin >> choice;
switch (choice)
{
case 1:
int n;
cout << "How many entries do you want to add? : ";
cin >> n;
for (int i = 0; i < n; i++)
{
cout << "Enter Key: ";
cin >> key;
cout << "Enter Value: ";
cin >> value;
dict.addNode(key, value);
cout << endl;
}
break;
case 2:
cout << "<----------Dictionary------------->" << endl;
dict.display();
cout << "-----------------------------------" << endl;
break;
case 3:
cout << "Enter key to be searched: ";
cin >> key;
dict.search(key);
cout << "-----------------------------------" << endl;
break;
case 4:
cout << "Enter key to be deleted: ";
cin >> key;
dict.deleteNode(key);
cout << "-----------------------------------" << endl;
break;
case 5:
cout << "Enter key to be updated: ";
cin >> key;
cout << "Enter updated value of key: ";
cin >> value;
dict.update(key, value);
cout << "-----------------------------------" << endl;
break;
default:
cout << "Invalid Choice!!!" << endl;
break;
}
cout << "Do you want to continue? (y/n) : ";
cin >> cont;
}
cout << "Program Ended Successfully!!!" << endl;
return 0;
}
Comments
Post a Comment