I have a linkedList class and I need to convert it into a hash table through an
ID: 3638621 • Letter: I
Question
I have a linkedList class and I need to convert it into a hash table through an array.
these are the functions I need to implement:
class speedTable
{
private:
studentList * table; //an array of studentLists
int tableSize; //size of the array
public:
speedTable(int size);
~speedTable();
void add(student s);
//remove student with given id from data structure
void remove(int id);
//locate and return the student with given id from the data structure
student getStudent(int id);
//Create a new array of size newsize and rehash
//all items in the old table into the new table.
//Free (delete) the old array and point the table
//variable at the new array.
void resize(int newsize);
}
this is my linkedList code:
#include <string>
#include <iostream>
#include <vector>
#include <iomanip>
#include <cassert>
#include "student.h"
using namespace std;
//student list is a doubly linked list of students.
template <class Type>
class linkedList
{
public:
template<class Type>
class node
{
public:
Type data;
node<Type> * next;
node<Type> * prev;
node(Type x)
{
data = x;
next = NULL;
prev = NULL;
}
};
node<Type> * head, *first;
friend ostream& operator<<<Type>(ostream& os, const linkedList<Type>& x);
public:
~linkedList();
linkedList();
bool empty();//return true if the list is empty, false if not.
void push(Type s);//insert student s into the front of the linked list
Type pop();//remove and return the student at the front of the list
bool removeStudent(int id);//locate and remove the student with given ID number
Type getStudent(int id);//locate and return a copy of the student with given ID number
//arrange students into increasing based on either ID or name. If
//variable 'field' has value "id", sort into increasing order by id.
//If 'field' has value "name", sort into alphabetical order by name.
void sort(string field);
//a test function to simply display the list of students to the screen
//in the order they appear in the list.
void display();
int returnCount();
Type *list;
};
template <class Type>
linkedList<Type>::linkedList()
{
head = NULL;
}
template <class Type>
linkedList<Type>::~linkedList()
{
}
template <class Type>
int linkedList<Type>::returnCount()
{
if (head == NULL)
return 0;
else
{
int count = 0;
node<Type> * current = head;
while( current != NULL )
{
count++;
current = current->next;
}
return count;
}
}
template<class Type>
void linkedList<Type>::push(Type s)
{
node<Type> * somenode = new node<Type>(s);
somenode->next = head;
if( head != NULL )
head->prev = somenode;
head = somenode;
}
//remove and return front item from list
template <class Type>
Type linkedList<Type>:: pop()
{
if( head == NULL )
{
cout<<"Cannot pop item from empty list"<<endl;
}
else if( head->next == NULL )
{
Type output = head->data;
delete head;
head = NULL;
return output;
}
else
{
node<Type> * temp = head;
head = head->next;
head->prev = NULL;
Type output = temp->data;
delete temp;
return output;
}
}
template <class Type>
bool linkedList<Type>::empty()// Function to check if the list is empty
{
int empty=returnCount();
if(empty == 0)
{
cout<< " The list is empty "<<endl;
return true;
}
else return false;
}
template <class Type>
void linkedList<Type>::display()
{
node<Type> * current = head;
while( current != NULL )
{
cout<< current->data <<endl;
current = current->next;
}
}
template <class Type>
Type linkedList<Type>::getStudent(int id)
{
node<Type> *current; //ptr to current node
current = head; //point to first
while (current!= NULL)
{
if (current->data.getId() == id)
return current->data;
else //otherwise move to the next node
current = current->next;
}
}
template <class Type>
bool linkedList<Type>::removeStudent(int id)
{
node<Type> *current; //ptr to current node
current = head; //point to first
while (current!= NULL)
{
if (current->data.getId() == id)
{
//found it, let it equal temp
node<Type> * temp = current;
if (temp->prev == NULL)
{
head = head->next;
head->prev = NULL;
delete temp;
return true;
}
else
{
node<Type> * previous, * next;
previous=temp->prev;
next = temp->next;
previous->next=next;
next->prev=previous;
delete temp;
return true;
}
}
else //otherwise move to the next node
current = current->next;
}
return false;
}
template<class Type>
void linkedList<Type>::sort(string field)
{
int c = returnCount();
//create an array of size returnCount.
Type studentArray[100];
node<Type> * current = head;
for(int i = 0; i < c; i++)
{
studentArray[i] = current->data;
current = current->next;
}
int k, j, count;
Type tmp;
bool flag;
count = c;
for (k = 0; k< count; k++)
{
flag = false;
for (j = 0; j< count - k - 1; j++) //bubble the i-th largest element to the right position
{
//swap list[j] and list[j+1] if they are out of order
if ( field.compare("id") ==0)
{
if (studentArray[j].getId() > studentArray[j+1].getId())
{
tmp = studentArray[j];
studentArray[j] = studentArray[j+1];
studentArray[j+1] = tmp;
flag = true;
}
}
else if ( field.compare("name") == 0)
{
string n = studentArray[j].getName();
string m = studentArray[j+1].getName();
if (n.compare(m) > 0)
{
tmp = studentArray[j];
studentArray[j] = studentArray[j+1];
studentArray[j+1] = tmp;
flag = true;
}
}
}
if (!flag) //if swapping, then the list is sorted
break;
}
current = head;
for(int i = 0; i < c; i++)
{
current->data = studentArray[i];
current = current->next;
}
}
#endif