Error in erase function

#1

void erase(string key ){

	int idx = hashFn(key);
	Node<T>*temp = table[idx];
	Node<T>*prev = table[idx];
	while(temp!=NULL){
		if(temp->key==key){
			prev->next = temp->next;
			delete temp;
			return;
		}
		prev = temp;
		temp = temp->next;
	}
	return;
}

this function works properly only when the element to be deleted is at the last of linked list

#2

@ANIKET_DALAL, your code is not handling the case when the node to be deleted is the head of the linked list as in that case you have to change the table[idx] to head->next

void erase(string key){
	int idx = hashFn(key);
	Node<T>*temp = table[idx];
	Node<T>*prev = table[idx];
	if(temp->key==key){
		table[idx]=temp->next;
		delete temp;
		return;
	}
	while(temp!=NULL){
		if(temp->key==key){
			prev->next = temp->next;
			delete temp;
			return;
		}
		prev = temp;
		temp = temp->next;
	}
	return;
}

In case of any doubt feel free to ask :slight_smile:

#3

still its only working if there is only one element in LL(i.e. head) or for the last element. Not working if the element is in middle or element is head (where size of LL is >1)

#4

please share your code @ANIKET_DALAL, so i can check by myself

#5

#include < iostream >
#include < cstring >
using namespace std;

template < typename T>
class Node{

public:
string key;
T value;
Node*next;

Node(string key,T val){
	this->key = key;
	value = val;
	next = NULL;
}

~Node(){
	if(next!=NULL){
		delete next;
	}
}

};

template< typename T>
class Hashtable{

Node<T>**table;
int current_size;
int table_size;

int hashFn(string key){
	int idx = 0;
	int p = 1;
	for(int j=0;j<key.length();j++){
		idx = idx + (key[j]*p)%table_size;
		idx = idx%table_size;
		p = (p*27)%table_size;
	}
	return idx;
}

public:
Hashtable(int ts=3){
table_size = ts;
table = new Node*[table_size];
current_size = 0;
for(int i=0;i<table_size;i++){
table[i] = NULL;
}
}

void insert(string key, T value){
	int idx = hashFn(key); 
	Node<T>*n = new Node<T>(key,value);
	n->next = table[idx];
	table[idx] = n;
	current_size++;

	float load_factor = current_size/(1.0*table_size);
	//if(load_factor>0.7){
	//	rehash();
	//}
}



void rehash(){
	Node<T>**oldTable = table;
	int oldTableSize = table_size;
	table_size = 2*table_size;
	table = new Node<T>*[table_size];
	for(int i=0;i<table_size;i++){
		table[i] = NULL;
	}
	current_size = 0;
	for(int i=0;i<oldTableSize;i++){
		Node<T>*temp = oldTable[i];
		while(temp!=NULL){
			insert(temp->key,temp->value);
			temp = temp->next;	
		}
		if(oldTable[i]!=NULL){
			delete oldTable[i];
		}
	}
	delete [] oldTable;
}

T*search(string key){
	int idx = hashFn(key);
	Node<T>*temp = table[idx];
	while(temp!=NULL){
		if(temp->key==key){
			return &temp->value;
		}
		temp = temp->next;
	}
	return NULL;
}

void erase(string key){
	int idx = hashFn(key);
	Node<T>*temp = table[idx];
	Node<T>*prev = table[idx];
	if(temp->key==key){
		table[idx] = temp->next;
		delete temp;
		return;
	}
	while(temp!=NULL){
		if(temp->key==key){
			prev->next = temp->next;
			delete temp;
			return;
		}
		prev = temp;
		temp = temp->next;
	}
	return;
}

void print(){
	for(int i=0;i<table_size;i++){
		cout<<"Bucket "<<i<<"->";
		Node<T>*temp = table[i]; 
		while(temp!=NULL){
			cout<<temp->key<<"->";
			temp = temp->next;
		}
		cout<<endl;
	}
}

};

sir, i think the destructor is causing a problem in this when i comment out the destructor the code works fine. the destructor is deleting every thing after the element which is eqal to key
( as this destructor was made for rehash function).

#6

hi @ANIKET_DALAL,
before deleting temp you have to set temp->next=NULL;
because what happens is when you call delete temp it evokes destructor for temp which deletes the entire linked list if temp->next!=NULL
correct code :-

In case of any doubt feel free to ask :slight_smile: