I have the following classes, SLList, an integer datatype-based linked list and DLList, a template-based linked list. My problem is that SLList is working perfectly, but as soon as i modify it to be used as a template, i get errors, more specifically LNK 2019, i.e. linking errors. I avoided the use of pointers and have been up all night trying to fix it. Please help:

SLList.h:

#ifndef SLLIST_H
#define SLLIST_H

#include <iostream>

using namespace std;

class ListNode
{
public:
	int data;
	ListNode *next;
	ListNode *previous;
	ListNode(){next = previous = NULL;}
	ListNode(int d, ListNode *p = NULL, ListNode *n = NULL)
	{
		data = d;
		previous = p;
		next = n;
	}
};

class SLList
{
private:
	ListNode *head, *tail;
	int length;
public:
	SLList();
	~SLList();
	bool isEmpty();
	bool isInlist(int data);
	void addToHead(int data);
	void addToTail(int data);
	int removeTail();
	int removeHead();
	bool deleteData(int data);
	void clearList();
	friend ostream &operator<<(ostream &os, SLList& list);
};

#endif

SLList.cpp:

#include "SLList.h"

using namespace std;


SLList::SLList()
{
	tail = head = NULL;
}


SLList::~SLList()
{
	while(!isEmpty())
		removeTail();
}


bool SLList::isEmpty()
{
	if(this->head == NULL)
		return true;
	else
		return false;
	//return (head == NULL) ? true : false;
}


bool SLList::isInlist(int data)
{
	ListNode *temp = head;

	while(temp != NULL && temp->data != data)
		temp = temp->next;

	return (temp == NULL) ? false : true;
}


void SLList::addToHead(int data)
{
	head = new ListNode(data, NULL, head);
	
	if(tail == NULL)
		tail = head;
	else
		head->next->previous = head;
}


void SLList::addToTail(int data)
{
	if(isEmpty())
		head = tail = new ListNode(data);
	else{
		tail->next = new ListNode(data, tail);
		tail->next->previous = tail;
		tail = tail->next;
	}
}


int SLList::removeHead(){
	if(!isEmpty())
	{
		ListNode *temp = head;
		int tempData = temp->data;

		if(head == tail)
			head = tail = NULL;
		else {
			head = head->next;
			head->previous = NULL;
		}

		delete temp;
		return tempData;
	} else
		exit(1);
}


int SLList::removeTail(){
	if(!isEmpty()){
		int tempData = tail->data;

		if(tail != head){
			ListNode *temp = tail;
			tail = tail->previous;
			tail->next = NULL;
			delete temp;
		} else {
			delete tail;
			head = tail = NULL;
		}
		return tempData;
	} else
		exit(1);
}


bool SLList::deleteData(int data)
{
	ListNode *temp = head;

	while(temp != NULL && temp->data != data)
		temp = temp->next;

	if(temp == NULL)
		return false;
	else{
		temp->previous->next = temp->next;
		temp->next->previous = temp->previous;
		delete temp;
		return true;
	}
}


void SLList::clearList(){
	while(!isEmpty())
		removeTail();
}


ostream& operator<<(ostream &os, SLList& l)
{
	if(!l.isEmpty())
	{
		ListNode *temp = l.head;
		for(int i = 1; temp != NULL; i++)
		{
			os << i << ".\t" << temp->data << endl;
			temp = temp->next;
		}
	} else
		os << "No data in list." << endl;

	return os;
}

DLList.h:

#ifndef DLLIST_H
#define DLLIST_H

#include <iostream>

using namespace std;

template <class T>
class ListNode
{
	T data;
	ListNode *next;
	ListNode *previous;
	ListNode(){next = previous = NULL;}
	ListNode(T d, ListNode *p = NULL, ListNode *n = NULL)
	{
		data = d;
		previous = p;
		next = n;
	}
};

template <class T>
class DLList
{
private:
	ListNode<T> *head, *tail;
	int length;
public:
	DLList();
	~DLList();
	bool isEmpty();
	bool isInlist(T data);
	void addToHead(T data);
	void addToTail(T data);
	T removeTail();
	T removeHead();
	bool deleteData(T data);
	void clearList();
	friend ostream &operator<<(ostream &os, DLList<T>& list);
};

#endif

DLList.cpp:

#include "DLList.h"

using namespace std;

template <class T>
DLList<T>::DLList()
{
	tail = head = NULL;
}

template <class T>
DLList<T>::~DLList()
{
	while(!isEmpty())
		removeTail();
}

template <class T>
bool DLList<T>::isEmpty()
{
	if(this->head == NULL)
		return true;
	else
		return false;
}

template <class T>
bool DLList<T>::isInlist(T data)
{
	ListNode<T> *temp = head;

	while(temp != NULL && temp->data != data)
		temp = temp->next;

	if(temp == NULL)
		return false;
	else
		return true;
}

template <class T>
void DLList<T>::addToHead(T data)
{
	head = new ListNode<T>(data, NULL, head);

	if(tail == NULL)
		tail = head;
	else
		head->next->previous = head;
}

template <class T>
void DLList<T>::addToTail(T data)
{
	if(isEmpty())
		head = tail = new ListNode<T>(data);
	else{
		tail->next = new ListNode<T>(data, tail);
		tail->next->previous = tail;
		tail = tail->next;
	}
}

template <class T>
T DLList<T>::removeHead(){
	if(!isEmpty())
	{
		ListNode<T> *temp = head;
		T tempData = temp->data;

		if(head == tail)
			head = tail = NULL;
		else {
			head = head->next;
			head->previous = NULL;
		}

		delete temp;
		return tempData;
	} else
		exit(1);
}

template <class T>
T DLList<T>::removeTail(){
	if(!isEmpty()){
		T tempData = tail->data;

		if(tail != head){
			ListNode<T> *temp = tail;
			tail = tail->previous;
			tail->next = NULL;
			delete temp;
		} else {
			delete tail;
			head = tail = NULL;
		}
		return tempData;
	} else
		exit(1);
}

template <class T>
bool DLList<T>::deleteData(T data)
{
	ListNode<T> *temp = head;

	while(temp != NULL && temp->data != data)
		temp = temp->next;

	if(temp == NULL)
		return false;
	else{
		temp->previous->next = temp->next;
		temp->next->previous = temp->previous;
		delete temp;
		return true;
	}
}

template <class T>
void DLList<T>::clearList(){
	while(!isEmpty())
		removeTail();
}

template <class T>
ostream& operator<<(ostream &os, DLList<T>& l)
{
	if(!l.isEmpty())
	{
		ListNode<T> *temp = l.head;
		for(int i = 1; temp != NULL; i++)
		{
			os << i << ".\t" << temp->data << endl;
			temp = temp->next;
		}
	} else
		os << "No data in list." << endl;

	return os;
}

app.cpp

#include "DLList.h" //replace with SLList

using namespace std;

int main()
{
	typedef DLList<int> List; //replace with typedef SLList List;
	List intList;
	intList.addToHead(1);
	intList.addToHead(3);
	intList.addToHead(7);
	intList.addToHead(9);
	intList.addToHead(11);
	intList.addToHead(4);
	intList.addToHead(12);
	intList.addToHead(54);
	intList.addToHead(67);
	intList.deleteData(3);

	cout << intList;
	return 0;	
}

the exact errors is 'Error 1 error LNK2019: unresolved external symbol' for every function declared in main.

your code is not organized correctly. Although it is traditional to organize definitions into header files and implementation into .cpp files this will not work effectively for tempates. As you have found a compiler will generally accept this but it will not ge by the linker. The reason for this is that the definition of the function template has not been instantiated. In order for a template to be instantiated, the compiler must know which definition should be instantiated and for what template arguments it should be instantiated.

Unfortunately, in your example, these two pieces of information are in files that are compiled separately. Therefore, when your compiler sees the calls to the functions it has no definition in sight to instantiate this functions, it just assumes that such a definition is provided elsewhere and creates a reference (for the linker to resolve) to that definition. Also, when the compiler processes the file DLList.cpp, it has no indication at that point that it must instantiate the template definition it contains for specific arguments.

The common solution to the previous problem is to use the same approach that we would take with macros or with inline functions: We include the definitions of a template in the header file that declares that template. For our example, we can do this by adding

#include "DLList.cpp"

at the end of DLList.h or by including DLList.cpp in every dot-C file that uses the template. A third way, of course, is to do away entirely with DLList.cpp and rewrite DLList.h so that it contains all template declarations and template definitions. That is your first task. having done that you might find other problems with you solution. I leave that to you...

commented: Very good reasoning and explanation of problem is provided. +2

As one of the requirements of the assignment, i need to keep different implementation and header files :(.
However, when I tried adding
#include "DLList.cpp" at the end of DLList.h file, i got 'function template has already been defined for every function in the .cpp file. How do I fix this. I usually try to code specific classes and this is my first time with templates.

Thanks anyways!!

As one of the requirements of the assignment, i need to keep different implementation and header files :(.
However, when I tried adding
#include "DLList.cpp" at the end of DLList.h file, i got 'function template has already been defined for every function in the .cpp file. How do I fix this. I usually try to code specific classes and this is my first time with templates.

Thanks anyways!!

Well that is intersting as this method of code organisation will not work properly with templates and is not generally the acceted method of doing it!

Try placing include guards around the code in the .cpp file.

e.g.

#ifdef DLLIST_CPP
#define DLLIST_CPP

...
template function defintions
...

#endif

Thge generally accepted way of doing this is to do away with the include file altogether and define the functions directly in the header as per inlines and macros. this is called the inclusion method and is probably what you should aim for.

OK, that took care of every single error i had! Thanks!

BUT, now i'm in a fix with the overloaded operator<<! Its giving me linking errors with it and i can;t seem to see north here since it is the only error i have been left with.

the error i mentioned:

Error 1 error LNK2019: unresolved external symbol "class std::basic_ostream<char,struct std::char_traits<char> > & __cdecl operator<<(class std::basic_ostream<char,struct std::char_traits<char> > &,class Hotel const &)" (??6@YAAAV?$basic_ostream@DU?$char_traits@D@std@@@std@@AAV01@ABVHotel@@@Z) referenced in function _main App.obj Homework3

The error inplies that the desired operator overload has not been instantiated. Friendship can have an effect on template instantiation. Think about why you have made the output operator overload a friend.

That is all I am going to say... ;)

The error inplies that the desired operator overload has not been instantiated. Friendship can have an effect on template instantiation. Think about why you have made the output operator overload a friend.

That is all I am going to say... ;)

Well, I've been banging heads for days now and have not been able to fix this. Also, I came accross a new problem. Since I use Char * for the guest names, they are deleted as soon as the local variable is destroyed. Can someone please point me in the right direction!

PS: I believe homework help is provided ONLY when a person shows some work. I have done almost everything and just need these two bugs fixed. please help!

The error inplies that the desired operator overload has not been instantiated. Friendship can have an effect on template instantiation. Think about why you have made the output operator overload a friend.

That is all I am going to say... ;)

Well, I've been banging heads for days now and have not been able to fix this. Also, I came accross a new problem. Since I use Char * for the guest names, they are deleted as soon as the local variable is destroyed. Can someone please point me in the right direction!

PS: I believe homework help is provided ONLY when a person shows some work. I have done almost everything and just need these two bugs fixed. please help!

First I need to appologise to everyone for venting out like this. Secondly, I have been able to fix the data issue, my mind was just clouded with frustation.

However, I still need someone to tell me how to fix the >> operator. A million thanks in advance.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.