You are essentially trying to code the beginning of a hash-table using arr as your hash-table and then using Forward-Chaining to handle any collisions. In your case since you have n unique values using your hash of nums[i] % n and n buckets, you will not have any collisions so you will have a 1-node list at each of the arr[i] locations.
To begin with since class LL contains the node *head member, you do not need to declare and allocate pointers and then nodes with LL **arr; you simply need to allocate for LL *arr; allocating one instance of class LL for each bucket as your hash-table. Then InsertForChaining() will allocate and insert a new head node each time chaining any existing nodes. You do that as:
Chaining (std::vector<int>&nums) {
n = nums.size();
arr = new LL[n];
for (int i = 0; i < n; i++) {
int storage = nums[i] % n;
arr[storage].InsertForChaining (nums[i], i);
}
}
You are drastically over-complicating how you do Forward-Chaining. Your InsertForChaining() reduces to:
class LL {
public:
node *head = NULL;
void InsertForChaining (int data,int i) {
node *t = new node;
t->data = data;
t->index = i;
t->next = head;
head = t;
}
};
When you write a class that allocates with new, makes sure you write a destructor to delete the memory you have allocated, otherwise you will leak memory. A simple destructor is all that is needed, e.g.
~Chaining() {
for (int i = 0; i < n; i++) {
while (arr[i].head) {
node *victim = arr[i].head;
arr[i].head = arr[i].head->next;
delete victim;
}
}
delete[] arr;
arr = nullptr;
}
(note: how in each of the functions the removal of the one level of indirection to accommodate the change of LL **arr to LL *arr.)
Your search() function need only iterate until it finds the node with data matching key. If you reach the end of the list before key is matched, then you return your -1. That reduces search() to:
int search (int key) {
node *p = arr[key%n].head;
while (p && p->data != key)
p = p->next;
return p ? p->index : -1;
}
You can add a short function to output the contents of your hash-table to confirm the stored values. Just loop over each bucket and iterate from arr[i].head until nullptr is reached. That can be done with:
void prnlist () {
std::cout.put ('\n');
for (int i = 0; i < n; i++) {
node *t = arr[i].head;
std::cout << "arr[" << i << "]:";
while (t) {
std::cout << " (" << t->data << ", " << t->index << ")";
t = t->next;
}
std::cout.put ('\n');
}
}
Whenever you write functionality into your code, you should test it with short unit tests. In main() simply print the table and search for each value in your vector to ensure it is found in your table. Only produce output from your tests if an error occurs. For example:
int main(void) {
std::vector<int>v1 = {1,2,3,4,5,6,7,8,9};
std::cout << "hello start\n";
Chaining c1(v1);
c1.prnlist();
std::cout << "\nvalidating search of each value.\n";
for (const auto i : v1)
if (c1.search(i) == -1)
std::cerr << "error: " << i << " not found in table.\n";
std::cout << "(validation done)\n";
std::cout << "\nhello\n";
}
You will want to read Why should I not #include <bits/stdc++.h>? and Why is “using namespace std;” considered bad practice?. Building good habits early is easier than breaking bad ones later...
Another little nit is there is no need to output a string literal and then endl, e.g.
cout<<"hello start"<<endl;
Instead, simply include '\n' as part of the string literal, e.g.
std::cout << "hello start\n";
Putting it altogether, you could do:
#include <iostream>
#include <vector>
class node {
public:
int data;
int index;
node *next;
};
class LL {
public:
node *head = nullptr;
void InsertForChaining (int data,int i) {
node *t = new node;
t->data = data;
t->index = i;
t->next = head;
head = t;
}
};
class Chaining {
public:
LL *arr;
int n;
Chaining (std::vector<int>&nums) {
n = nums.size();
arr = new LL[n];
for (int i = 0; i < n; i++) {
int storage = nums[i] % n;
arr[storage].InsertForChaining (nums[i], i);
}
}
~Chaining() {
for (int i = 0; i < n; i++) {
while (arr[i].head) {
node *victim = arr[i].head;
arr[i].head = arr[i].head->next;
delete victim;
}
}
delete[] arr;
arr = nullptr;
}
void prnlist () {
std::cout.put ('\n');
for (int i = 0; i < n; i++) {
node *t = arr[i].head;
std::cout << "arr[" << i << "]:";
while (t) {
std::cout << " (" << t->data << ", " << t->index << ")";
t = t->next;
}
std::cout.put ('\n');
}
}
int search (int key) {
node *p = arr[key%n].head;
while (p && p->data != key)
p = p->next;
return p ? p->index : -1;
}
};
int main(void) {
std::vector<int>v1 = {1,2,3,4,5,6,7,8,9};
std::cout << "hello start\n";
Chaining c1(v1);
c1.prnlist();
std::cout << "\nvalidating search of each value.\n";
for (const auto i : v1)
if (c1.search(i) == -1)
std::cerr << "error: " << i << " not found in table.\n";
std::cout << "(validation done)\n";
std::cout << "\nhello\n";
}
Example Use/Output
$ ./bin/chaining_vector
hello start
arr[0]: (9, 8)
arr[1]: (1, 0)
arr[2]: (2, 1)
arr[3]: (3, 2)
arr[4]: (4, 3)
arr[5]: (5, 4)
arr[6]: (6, 5)
arr[7]: (7, 6)
arr[8]: (8, 7)
validating search of each value.
(validation done)
hello
Memory Use/Error Check
In any code you write that dynamically allocates memory, you have 2 responsibilities regarding any block of memory allocated: (1) always preserve a pointer to the starting address for the block of memory so, (2) it can be freed when it is no longer needed.
It is imperative that you use a memory error checking program to ensure you do not attempt to access memory or write beyond/outside the bounds of your allocated block, attempt to read or base a conditional jump on an uninitialized value, and finally, to confirm that you free all the memory you have allocated.
For Linux valgrind is the normal choice. There are similar memory checkers for every platform. They are all simple to use, just run your program through it.
$ valgrind ./bin/chaining_vector
==15924== Memcheck, a memory error detector
==15924== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==15924== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==15924== Command: ./bin/chaining_vector
==15924==
hello start
arr[0]: (9, 8)
arr[1]: (1, 0)
arr[2]: (2, 1)
arr[3]: (3, 2)
arr[4]: (4, 3)
arr[5]: (5, 4)
arr[6]: (6, 5)
arr[7]: (7, 6)
arr[8]: (8, 7)
validating search of each value.
(validation done)
hello
==15924==
==15924== HEAP SUMMARY:
==15924== in use at exit: 0 bytes in 0 blocks
==15924== total heap usage: 13 allocs, 13 frees, 73,980 bytes allocated
==15924==
==15924== All heap blocks were freed -- no leaks are possible
==15924==
==15924== For counts of detected and suppressed errors, rerun with: -v
==15924== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
Always confirm that you have freed all memory you have allocated and that there are no memory errors.
Look things over and let me know if you have further questions.
