CODEWITHSUNDEEP
c++linked-listhashtable
user1965283
user1965283

Reputation: 147

Hash-table - Array of Linked-list - C++

I'm trying to create a Hash-table by using an array on linked-nodes (making a linked list). But I'm having difficulties inserting a value into the Hash-table. When I run it, I get this:

http://gyazo.com/3a28a70e66b3ea34e08223e5948f49c0.png

Here is my code:

#include <iostream>
using namespace std;

class Node {
public:
  int num;
  Node * next;
};

class intHashTable {
private:
  int size;
  Node ** table;
public:
  intHashTable(int size);  // construct a new hash table with size elements
  ~intHashTable();     // delete the memory for all internal components
  void insert(int num);    // insert num into the hash table, no effect
               // if num is already in table
  void remove(int num);    // remove num from the hash table, no effect if not in table
  int lookup(int num);     // return 1 if num is already in table, 0 otherwise
  void print(void);        // print the elements of the hash table to the screen
};

// construct a new hash table with nelements elements
intHashTable::intHashTable(int nelements)
{
  size = nelements;
  table = new Node*[size];
  for ( int i = 0; i < size; i++ ) {
    table[i] = NULL;
  }
}

intHashTable::~intHashTable()
{
   for(int i=0; i<size; i++)
   {
      Node* temp = table[i];
      while(temp != NULL)
      {
         Node* next = temp->next;
         delete temp;
         temp = next;
      }
   }
   size = 0;
   delete[] table;
}

void intHashTable::insert(int num){
    int location = ((unsigned)num) % size;
    Node *runner = table[location];
    if(runner == NULL ){
    runner->num = num;
     }else{
        while(runner != NULL ){
            runner = runner->next;
        }
        runner->num = num;
    }
   }

int main(){
    intHashTable a (10);
    a.insert(2);
    return 0;
}

Upvotes: 3

Views: 15180

Answers (4)

AndersK
AndersK

Reputation: 36092

the logic here is wrong

int location = ((unsigned)num) % size;
Node *runner = table[location];

if(runner == NULL ) // if null u dereference it!
{
 runner->num = num;
}
else
{
  while(runner != NULL ) {  // u loop until null
    runner = runner->next;
  }
  runner->num = num;  // once u reach null u dereference it!
}

i would suggest instead:

first a ctor for your Node

class Node {
public:
  int num;
  Node * next;

  Node( int _n ) : num(_n), next(NULL) { } 
};

and then

if ( runner != NULL )
{
   while ( runner->next != NULL )
   {
      runner = runner->next;
   }
   runner->next = new Node( num );
}
else
{
  table[location] = new Node( num ); 
}

Upvotes: 2

UmNyobe
UmNyobe

Reputation: 22920

Node *runner = table[location];
runner = runner->next;
if(runner == NULL )

You never verified whether table[location] is null. But during construction of your hashtable, there are no nodes inside the node table (you set yourself every entry to null).

The problem with your code is that you never think about allocating your node. You should be doing

Node* toInsert = new Node;
toInsert->next= NULL;
toInsert->num = num;

if(table[location]==NULL){
   table[location] = toInsert;  
}
else{
    Node *runner = table[location];
    while(runner->next != NULL){
         runner = runner->next;
    }
    runner->next = toInsert;
}

Upvotes: 1

Mats Petersson
Mats Petersson

Reputation: 129524

This code certainly won't work:

if(runner == NULL ){
runner->num = num;

If runner is NULL, then you should never dereference it (using * or -> on it).

Upvotes: 1

Reunanen
Reunanen

Reputation: 8031

After construction of intHashTable, all the elements of table are still NULL. However, in the function insert, one element is dereferenced:

Node *runner = table[location];
runner = runner->next;

This makes the program crash, because it is illegal to dereference a null pointer.

Upvotes: 3

Related Questions