4

I am working on a hashing project and is currently having difficulty with an array of linked-lists. My linked-list can only store 1 item, so I've created a Pair class with 2 member variables(string key and string value) and various member functions. My question is how can I make Pair work with my Linked-list class? My assumption is to do the following: If I wanted to add data into my linked list class I would create a function with the parameter - void insert(Pair data) - will this help me insert 2 items in my list? Here is my c++ code, can someone proof-read it for me and help me spot some errors.

#ifndef List_h
#define List_h

#include "Node.h"
#include "Pair.h"
#include<string>

using namespace std;

class List{
private:
    int size;
    Node<string>* headPtr;

public:
    List(); //default constructor
    List(const List& anotherList); //copy constructor -iffy, I'm not sure if my definition for this function is correct-
    virtual ~List(); //destructor
    void insert(Pair data); //insert item
    bool remove(Pair data); //remove item
    bool find(Pair data); //find item
    int getSize(); //size of list
    bool isEmpty(); //checks if list is empty
    void clear(); //clear list
};
#include "List.cpp"
#endif

.cpp

//inserting data to list
void List::insert(Pair data){

        Node<string>* newptr = new Node<string> (); //create new node
        newptr->setItem(data); //set character into node
        newptr->setNext(headPtr); //sets the ptr to headptr(null)
        headPtr = newptr; //headptr points to the node you've just created
        size++; //increment the size
}


 //clears the entire list
void List::clear(){
    Node<string>* delPtr = headPtr; //delPtr points to the top of the list
    while(delPtr != nullptr){
        headPtr = delPtr->getNext(); //sets the head pointer to the next node
        delPtr->setNext(nullptr); //begins the process of removing the data from the top of the list here
        delete delPtr;
        delPtr = headPtr; //sets the delPtr to the headptr after deleting this way we will continue to delete data from the list until the list is empty
    }

    headPtr = nullptr;
    delPtr = nullptr;
    size = 0;
}

 //destructor
List::~List() {
    clear();
}

Here is how my Pair.h file looks:

#ifndef _Pair_h
#define _Pair_h

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

class Pair{
private:
    string key;
    string value;
protected:
    void setKey(const string& key);

public:
    Pair();
    Pair(string aValue, string key);
    string getValue() const;
    string getKey() const;
    void setValue(const string& aValue);

};

#include "Pair.cpp"
#endif

Here is my Node.h file:

#ifndef _NODE
#define _NODE


template<class ItemType>
class Node
{
private:
   ItemType item; // A data item
   Node<ItemType>* next; // Pointer to next node

public:
   Node();
   Node(const ItemType& anItem);
   Node(const ItemType& anItem, Node<ItemType>* nextNodePtr);
   void setItem(const ItemType& anItem);
   void setNext(Node<ItemType>* nextNodePtr);
   ItemType getItem() const ;
   Node<ItemType>* getNext() const ;
}; // end Node

#include "Node.cpp"
#endif

With all that said, my best guess is that when I do create an array of lists in my dictionary ADT, my private members would be:

List* hashtable[size];

const int size = 31; //31 is a arbitrary prime number for the hashtable

14
  • If you want your List class to work with different types use templates. Also show your Node class since it is not clear how you handle instance of Pair in the setItem method and why you don't use Node<Pair>*. Also do you really need array of linked lists? Maybe array of pairs would be enough? Commented Dec 25, 2015 at 3:40
  • Can someone take a look at my copy constructor it doesn't seem to work properly @NikolayKondratyev Commented Dec 25, 2015 at 3:57
  • I need an array of linked lists for my hashtable to avoid collisions @NikolayKondratyev Commented Dec 25, 2015 at 3:58
  • If you need to avoid collisions then list won't have only 1 item, it should handle all the items with the same hash. Does your code even compile? As I have thought newptr->setItem(data); looks wrong. Commented Dec 25, 2015 at 4:01
  • How would you fix newptr->setItem(data); @NikolayKondratyev Commented Dec 25, 2015 at 4:04

1 Answer 1

1

Make a new nlist = new List(); (creating a new list object), set nlist headptr = anotherList.headptr.getItem() and continue to copy the ITEMS pointing to the anotherList nodes to your nlist nodes then return nlist;

newchainPtr->setNext(nullptr); seems unnecessary and you should check for NULL from anotherList instead. An array OF linked lists means an array of linked list objects, the nodes are a part of the list object.

Look up DEEP copy if this confuses you and you'll spot it. Make sure to free up any unused memory. Hope this helps!

Sign up to request clarification or add additional context in comments.

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.