Dynamic Array of Linked List question

[rylarson]

I am using a dynamic array of linked lists as a data structure to help avoid collisions in a hash table. I want to dynamically allocate the size of the array of linked lists, but I dont know how to initialize them both, for example, if you wanted a dynamically allocated array, I could just say

char * array;
array = new char[50];

however, what I have now looks something like this:

 private:
              node ** hasht;

and in the constructor for that class, I have this:

hashtable::hashtable(int size = 13)
{	
	hasht = new node * [SIZE];
	for(int i = 0; i < size; ++i;)
	{
		hasht[i] = NULL;
    }
    table_size = SIZE;
}

so i define hasht as a new node, just like i normally would, but then i still have int size pointing to my node. How do i define that as an array size, or does this constructor already do that?

[kbw]

I think you need to breakdown your types further.

Your hash table stores data of some type I'll call bucket_type in an array of buckets I'll call bucket_list_type. And the hash table is an array of pointers to these bucket lists I'll call hash_table_type.

If your hash table were a template class, parameterised by the bucket_type, using standard containersm a definition would look like:

template <typename T>
class HashTable
{
public:
    HashTable(size_t tablesize = 13);

private:
    typedef T bucket_type;
    typedef std::vector<bucket_type> bucket_list_type;
    typedef std::vector<bucket_list_type*> hash_table_type;

    hash_table_type _table;
};

Even if you don't use standard types, the typedefs help you think about what types you're dealing with. The contructor of the table becomes:

template <typename T>
HashTable<T>::HashTable(size_t tablesize)
  : _table(tablesize)
{
    for (size_t i = 0; i < tablesize; ++i)
    {
        _table = new bucket_list_type();
    }
}

There is drawback with using a vector for bucket_list_type and a list may be a better choice.