Understanding String as member of class and linked list

[riversr54]

I know this topic is not a new one since I've been stumped by it before, but I'm still having trouble understanding exactly what the issue is and what to do to resolve it. I'm going to try to describe the problem instead of posting all the necessary code. The goal of this project is to write a Linked List with a search function.

First I created a simple Employee class, two data items, one int and one string. Second I created a Node class that has one data member, an Employee object. After populating an instance of the Employee class, it is placed in a Node which is added to my Linked List. Everything is good to this point. I can see the Nodes on the list and can see the data in the Employee objects in the Nodes.

Now to my search function. The function should search the list, looking for matching Employee information and then return a pointer to the Employee object. It does find the correct node, but here's the problem. When I get that pointer back, the Employee object has good data in the int member but nothing in the string data.

From past investigations of a similar problem, I know that this has to do with the nature of strings and how they are stored but I can't seem to wrap my head around the "Why?" and how to properly fix this problem.

Any help/instruction/education on this would be greatly appreciated.

Life Long Programming Learner

[helios]

Post the definition of Node and the code that copies the Employee into the Node.

[riversr54]

Code for Employee, Node and LinkedList are below. Everything seems to work find except the returned object from the findData function, near the bottom of the LinkeList class. Lastly is the code from main where I use the above classes, insert data and then search for it.

Employee Class

#pragma once
#include <iostream>
using namespace std;

class Employee
{
public:
	string mName;
	int mEmpId;

public:
	Employee()
	{
		//default constructor
	}
	~Employee()
	{
		//default deconstructor
	}
	void setName(string name)
	{
		mName = name;
	}
	void setID(int id)
	{
		mEmpId = id;
	}

	bool operator<(const Employee other)
	{
		if (this->mEmpId < other.mEmpId)
			return true;
		else
			return false;
	}

	bool operator>(const Employee other)
	{
		if (this->mEmpId > other.mEmpId)
			return true;
		else
			return false;
	}

	bool operator==(const Employee other)
	{
		if (this->mEmpId == other.mEmpId)
			return true;
		else
			return false;
	}

	friend ostream& operator<<(ostream& os, const Employee emp)
	{
		os << emp.mName << ": " << emp.mEmpId << endl;
		return os;
	}

};

Node Class

#pragma once
template <class T>
class NodeT
{
private:
	T mData;
	NodeT<T>* mNext = nullptr;

public:

	template <typename> friend class LLT;


	NodeT()
	{
		mData = 0;
		mNext = nullptr;
	}

	~NodeT()
	{}

	NodeT(T data)
	{
		mData = data;
	}

	NodeT(int data, NodeT* next)
	{
		mData = data;
		mNext = next;
	}

};

Linked List Class

#pragma once

#include "NodeT.h"
#include <iostream>
using namespace std;

template <class T>
class LLT
{
private:
	NodeT<T>* mHead;
	NodeT<T>* mTail;
public:

	LLT()
	{
		mHead = nullptr;
		mTail = nullptr;
	}

	~LLT()
	{}

	void addToHead(T data)
	{
		if (isEmpty())
		{
			mHead = new NodeT<T>(data);
			mTail = mHead;
		}
		else
		{
			NodeT<T>* tmp = new NodeT<T>(data);
			tmp->mNext = mHead;
			mHead = tmp;
		}
	}

	void removeFromHead()
	{
		NodeT<T>* tmp = mHead;
		mHead = mHead->mNext;
		delete tmp;
	}

	T getHeadData()
	{
		return mHead->mData;
	}

	void addToTail(T data)
	{
		if (isEmpty())
		{
			mHead = new NodeT<T>(data);
			mTail = mHead;
		}
		else
		{
			NodeT<T>* tmp = mTail;
			mTail = new NodeT<T>(data);
			tmp->mNext = mTail;
		}
	}

	void insertData(T data)
	{
		if (isEmpty())
		{
			mHead = new NodeT<T>(data);
			mTail = mHead;
		}
		else if (data < mHead->mData)
		{
			addToHead(data);
		}
		else if (data > mTail->mData)
		{
			addToTail(data);
		}
		else
		{
			NodeT<T>* tmp = mHead;					//start at head
			while (data > tmp->mNext->mData)	//compare data to next data
			{
				tmp = tmp->mNext;				//move to next node
			}
			NodeT<T>* newNode = new NodeT<T>(data);		//create new node
			newNode->mNext = tmp->mNext;		//new node point to orig. next
			tmp->mNext = newNode;				//prev node point to new node
		}
	}

	void deleteData(T data)
	{
		if (data < mHead->mData || data > mTail->mData)
		{
			//do nothing
		}
		else
		{
			NodeT<T>* tmp = mHead;
			while (data != tmp->mNext->mData)
			{
				tmp = tmp->mNext;
			}
			tmp->mNext = tmp->mNext->mNext;
		}
	}

	void displayList()
	{
		cout << endl << "List Contents" << endl;
		NodeT<T>* tmp = mHead;
		while (tmp != nullptr)
		{
			cout << tmp->mData << endl;
			tmp = tmp->mNext;
		}
	}

	NodeT<T>* findNTL()
	{
		NodeT<T>* tmp = mHead;
		NodeT<T>* prev = nullptr;

		while (tmp != nullptr)
		{
			if (tmp->mNext != nullptr)
			{
				prev = tmp;
			}
			tmp = tmp->mNext;
		}
		return prev;
	}


	void removeFromTail()
	{
		NodeT<T>* prev = findNTL();
		NodeT<T>* tmp = mTail;		//save pointer to original tail so it can be deleted
		mTail = prev;
		prev->mNext = nullptr;
		delete tmp;
	}



	T* findData(NodeT<T>* tmp, T data)
		//Call with nullptr to start at Head
		//Uses recursion
	{
		if (tmp == nullptr)
			tmp = mHead;

		if (tmp->mData == data)
		{
			return &tmp->mData;
		}
		else
		{
			if (tmp->mNext == nullptr)
			{
				T notFound;
				return notFound;
			}
			else
			{
				findData(tmp->mNext, data); //recursive call
			}
		}
	}


	bool isEmpty()
	{
		if (mHead == nullptr && mTail == nullptr)
		{
			return true;
		}
		else
		{
			return false;
		}
	}

	bool isOneNodeT()
	{
		if (mHead == mTail && mHead != nullptr)
		{
			return true;
		}
		else
		{
			return false;
		}
	}

};

Main code

int main()
{
	LLT<Employee> empList;

	Employee emp1;
	emp1.mName = "Joe";
	emp1.mEmpId = 111;

	empList.insertData(emp1);

	Employee empID;
	empID.mEmpId = 222;

	Employee* tmpEmp = empList.findData(nullptr, empID);

//this is where the problem occurs, the pointer to the returned Employee object has the int value but the string value is empty
}

[helios]

1. On line 170 you're discarding the result of the recursive call and then the function continues down a code path without a return statement.
2. I honestly don't understand why the compiler is not giving you an error. On line 166 you're returning a T from a function that returns a T *.
3. This isn't as important, but NodeT appears to assume that T = int in a couple places.

[dhayden]

- removeFromHead() should set tail if it removes the last item.
- insertData() will fail if the new item is a duplicate of the head or tail.
- deleteData() will crash if the list is empty or has 1 item. Also it needs to set head and/or tail.
- removeFromTail() will crash if the list has 0 or 1 item. Also it needs to set head if it removes the last item.

Since mHead == nullptr is a boolean expression. isEmpty() could simply be

bool isEmpty()
{
     return mHead != nullptr;
}

The same sort of thing applies to the comparison operators.

You can simplify the code a lot by creating a special "find" method:

    // Find T in the list, or find where it should go.
    // Return a reference to the pointer to that place
    // (mHead, or some node's next pointer).
    NodeT < T > * &find(const T &data)

With this, insertData(), deleteData and findData() become very simple.

#include <iostream>
using namespace std;

class Employee
{
  public:
    string mName;
    int mEmpId;

  public:
      Employee()
    {
	//default constructor
    }
    Employee(const string &name, int id) : mName(name), mEmpId(id) {}
    
     ~Employee()
    {
	//default deconstructor
    }
    void setName(string name)
    {
	mName = name;
    }
    void setID(int id)
    {
	mEmpId = id;
    }

    bool operator<(const Employee other)
    {
	return (this->mEmpId < other.mEmpId);
    }

    bool operator>(const Employee other)
    {
	return (this->mEmpId > other.mEmpId);
    }

    bool operator==(const Employee other)
    {
	return (this->mEmpId == other.mEmpId);
    }

    friend ostream & operator<<(ostream & os, const Employee emp)
    {
	os << emp.mName << ": " << emp.mEmpId << endl;
	return os;
    }

};

template < class T > class NodeT {
  private:
    T mData;
    NodeT < T > *mNext = nullptr;

  public:

    template < typename > friend class LLT;

    NodeT() {
	mData = 0;
	mNext = nullptr;
    }

    ~NodeT() {
    }

    NodeT(T data) {
	mData = data;
    }

    NodeT(int data, NodeT * next) {
	mData = data;
	mNext = next;
    }

};

#include <iostream>

template < class T > class LLT {
private:
    NodeT < T > *mHead;
    NodeT < T > *mTail;

    // Find T in the list, or find where it should go.
    // Return a reference to the pointer to that place
    // (mHead, or some node's next pointer).
    NodeT < T > * &find(const T &data)
    {
	NodeT<T> **pp, *p;
	for (pp = &mHead; (p = *pp); pp = &p->mNext) {
	    if (! (p->mData < data)) break;
	}
	return *pp;
    }

    
public:

    LLT() {
	mHead = nullptr;
	mTail = nullptr;
    }

    ~LLT() {
    }

    void addToHead(T data)
    {
	if (isEmpty()) {
	    mHead = mTail = new NodeT < T > (data);
	} else {
	    NodeT < T > *tmp = new NodeT < T > (data);
	    tmp->mNext = mHead;
	    mHead = tmp;
	}
    }

    void removeFromHead()
    {
	NodeT < T > *tmp = mHead;
	mHead = mHead->mNext;
	if (mHead == nullptr) mTail = nullptr;
	delete tmp;
    }

    // list must not be empty
    T getHeadData()
    {
	return mHead->mData;
    }

    void addToTail(T data)
    {
	if (isEmpty()) {
	    mHead = mTail = new NodeT < T > (data);
	} else {
	    NodeT < T > *tmp = mTail;
	    mTail = new NodeT < T > (data);
	    tmp->mNext = mTail;
	}
    }

    void insertData(T data)
    {
	NodeT < T > *newNode = new NodeT < T > (data);
	NodeT<T> * &pos = find(data);

	// Link it in
	newNode->mNext = pos;
	pos = newNode;
	
	// If it went at the beginning then pos pointed to mHead
	// so mHead was updated, but if it's the new tail, then
	// you have update mtail.
	if (mTail == nullptr || &mTail->mNext == &pos) {
	    mTail = newNode;
	}
    }

    void deleteData(T data)
    {
	NodeT<T> * &pos = find(data);
	if (pos == nullptr) return; // not found

	if (pos == mTail) {
	    mTail = findNTL();
	}
	NodeT<T> *tmp = pos;
	pos = pos->mNext;
	delete tmp;
    }

    void displayList()
    {
	cout << endl << "List Contents" << endl;
	for (NodeT < T > *tmp = mHead; tmp; tmp = tmp->mNext) {
	    cout << tmp->mData << endl;
	}
    }

    // Find next to last item.
    NodeT < T > *findNTL() {

	NodeT < T > *prev = nullptr;

	for (NodeT < T > *tmp = mHead; tmp != nullptr; tmp = tmp->mNext) {
	    if (tmp->mNext != nullptr) {
		prev = tmp;
	    }
	}
	return prev;
    }

    void removeFromTail()
    {
	if (mTail) {
	    deleteData(mTail->data);
	}
    }

    T *findData(T data)
    {
	NodeT<T> * &pos = find(data);
	return (pos ? &pos->mData : nullptr);
    }

    bool isEmpty()
    {
	return (mHead == nullptr);
    }

    bool isOneNodeT()
    {
	return (mHead == mTail && mHead != nullptr);
    }

};

int
main()
{
    LLT < Employee > empList;

    Employee emp1("Joe", 111);
    empList.insertData(emp1);

    Employee emp2("Jane", 222);
    empList.insertData(emp2);
    Employee dummy;
    dummy.mEmpId = 222;
    empList.displayList();

    Employee *tmpEmp = empList.findData(dummy);
    if (tmpEmp) {
	cout << *tmpEmp << '\n';
    } else {
	cout << "Not found\n";
    }
}

[riversr54]

Thanks for all the feedback, some suggestions for good improvements to my code, but I don't think anyone answered my original question.

At lines 150-170 in my LinkedList class, the function returns a pointer to the T data type. The problem is that when T is an Employee object, the returned pointer points to an Employee object that does in fact have the correct int data but the string member is empty or points to a string that is no longer available.

Given all the other great suggestions for my code, can someone provide me with some insight into why this happens and what do do about it?

Regards,

[riversr54]

CORRECTION to my problem statement:

The Employee object that is returned by pointer from the findData function contains no valid data. I'm sure that this is somehow related to the object being deleted but I can't seem to identify why/where that happens.

[riversr54]

FOUND MY PROBLEM

helios (above) hit the nail on the head

It's a simple oversight in my code:

1. On line 170 you're discarding the result of the recursive call and then the function continues down a code path without a return statement.

I failed to have the recursive call to findData return the pointer to the object.

Thanks again for all the suggestions. I will definitely make some of those changes.