C++

Forum

 
 
Linked List with templates

sarvcr (16)
Question Solved. Look at SeePlus comment if you have a problem like this.


Hi! Long story short, I've been struggling way more than I'd like to admit to understand how to work with linked lists using templates. When they taught me about templates, they used vectors. I thought that it wasn't gonna be that diferent, but couldn't adapt it to linked lists.

I've search on the internet too, but for some reason, I just can't adapt it to my code.

I made a version pretty similar to what I need (just smaller) to make this post.
I know there are solutions for this on the intenet, but I've not been able to make it work for me. I'd really appreciate if you could help me out on this.

That's pretty much what I need. I need a list where I can store several types of objects for my project, so I made a simplified version of it.

Edit: Currently using Visual Studio 2022
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
 
#include <iostream>
#include <sstream>
using namespace std;

template <class T> class List;
template <class T>
class Node {
private:
	T data;
	Node<T> next;
	Node<T> previous;
public:
	Node(T, Node<T>, Node<T>);
	virtual ~Node();

	T getData();
	Node<T>* getNext();
	Node<T>* getPrevious();

	void setData(T);
	void setNext(Node<T>*);
	void setPrevious(Node<T>*);
};

template <class T>
Node<T>::Node(T info, Node<T> nx, Node<T> prv)
	:data(info), next(nx), previous(prv) {}
template <class T>
Node<T>::~Node() {}
template <class T>
T Node<T>::getData() { return data; }
template <class T>
Node<T>* Node<T>::getNext() { return next; }
template<class T>
Node<T>* Node<T>::getPrevious() { return previous; }
template<class T>
void Node<T>::setData(T info) { data = info; }
template<class T>
void Node<T>::setNext(Node<T>* nx) { next = nx; }
template<class T>
void Node<T>::setPrevious(Node<T>* prv) { previous = prv; }

template<class T>
class List{
private:
	Node<T>* head;
	Node<T>* temporal;
	Node<T>* tail;
	int numberOfElements;
public:
	List();
	virtual ~List();

	void add(const T&);
	void remove(int);
	bool empty();

	int getNumberOfElements();

	void printList();
};

template<class T>
List<T>::List():head(NULL),temporal(NULL),tail(NULL),numberOfElements(0) {}
template<class T>
List<T>::~List(){}
template<class T>
void List<T>::add(const T& info){
	if (empty) {
		head = new Node<T>(info, NULL, NULL);
		numberOfElements++;
	}
	else {
		temporal = head;
		while (temporal->getNext() != NULL) {
			temporal = temporal->getNext();
		}
		Node<T>* newNode = new Node<T>(info, NULL, temporal);
		temporal->setNext(newNode);
		numberOfElements++;
	}
}
template<class T>
void List<T>::remove(int position){
	temporal = head;
	for (int i=0;i<position;i++){
		temporal = temporal->getNext();
	}
	temporal->getPrevious()->setNext(temporal->getNext());
	temporal->getNext()->setPrevious(temporal->getPrevious());
	delete temporal;
	numberOfElements--;
}
template<class T>
bool List<T>::empty() { return head == NULL; }
template<class T>
int List<T>::getNumberOfElements() { return numberOfElements; }
template<class T>
void List<T>::printList(){
	cout << "----------Printing List---------\n";
	for (int i = 0; i < numberOfElements; i++) {
		temporal = head;
		cout << temporal->getData() << endl;
		temporal = temporal->getNext();
	}
}

class Person {
private:
	string name;
	string id;
public:
	Person(string, string);
	virtual ~Person();

	friend ostream& operator <<(ostream& out, Person& p) {
		out << "Name: " << p.name << "\tID: " << p.id << endl;
		return out;
	}
};
Person::Person(string n, string i):name(n),id(i) {}
Person::~Person(){}


int main() {
	List<int> list1;
	List<Person> list2;
	for (int i = 0; i < 10; i++) {
		list1.add(i * 3);
	}
	Person per1("A", "1");
	Person per2("B", "2");
	Person per3("C", "3");
	Person per4("D", "4");
	Person per5("E", "5");

	list2.add(per1);
	list2.add(per2);
	list2.add(per3);
	list2.add(per4);
	list2.add(per5);


	list1.printList();
	list2.printList();



	return 0;
}


This isn't compiling and I can't understand why.
Last edited on
jonnin (11331)
which is true:
1) I want to make my own linked list class to learn about templates and linked lists and such or

2) I need a list where I can store several types of objects for my project, so I made a simplified version of it.

If the answer is 1, we can try to fix this one.
if the answer is 2, use c++'s list <list> which does all the work for you. Containers are aggravating to roll your own, which is why they added them to C++, so everyone can use the same debugged and well crafted ones rather than everyone roll out a new version slightly different. If you are dredging up code from the web for this, you are really grabbing someone's schoolwork and its likely junky in one way or another, because anyone else would use the c++ built in one. You might find a quality one in C, as that language does not provide it for the coder; that will compile and work in c++ but it won't be templated, of course.
Last edited on
sarvcr (16)
Both are true, but I'll say 1) is the most relevant here.
I need this for my project, but I want to make my own linked list class so I can learn about templates and then be able to implement my own Linked List Class.
jonnin (11331)
ok, first thing is that you can't do this:
class foo
{
foo x; //class recursion or whatever you wanna call this is no-can-do.
}

pointers are OK, so foo*x there in the class does work.
so your lines 10, 11 are messed up.

second, use nullptr instead of NULL in modern c++.
temporal: of or relating to time. Temporary: a disposable object.

if(empty) should be if(empty()). the normal rules of C++ still apply even in templates :)

the ctor for a node is this:
Node(T, Node<T>, Node<T>);
but you say
head = new Node<T>(info, NULL, NULL);
which is
Node(T, a pointer, another pointer?)
Node<T> is not a pointer. it is a node.
Also you need to be using references in case your <T> is a heavy fat class. You are doing a ton of copying T types as parameters because you left all the & off, which is sluggish.


That is as far as I can get it right this moment but just keep mashing compile and fixing these syntax errors as they pop up.
You need to get your head straight on what is a pointer and what is not a pointer. Templates are a bit endgame/advanced -- there are lots of subtle ways to muck them up, and lots of weird as crap error messages that take some experience to unravel. Maybe do a linked list of type integer, and then replace int with templates afterward.
Last edited on
mbozzi (3910)
A template is a computer program whose output is code - they automate your work of programming. For example a class template is a computer program that the compiler executes to produce a class definition.

But, without a solid understanding of what the resulting class definitions should look like, you can't effectively automate the process of writing them. So start with very specific cases. Code a linked list of int first and then, once you're satisfied with it, change it into a class template. It's doubly important to separate these steps because designing a correct template is occasionally a real challenge in its own right.

Some time last year I sketched a linked list for a guy who was trying to re-implement the standard one. It's a toy, but the gist of a production-strength implementation is there:

https://coliru.stacked-crooked.com/a/ab3410bb09af20b5
Last edited on
seeplus (6457)
As a first refactor, consider (note tail isn't used):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
 
#include <iostream>
#include <string>

template <class T>
class Node {
private:
	T data {};
	Node<T>* next {};
	Node<T>* previous {};

public:
	Node(T, Node<T>* = nullptr, Node<T>* = nullptr);

	T getData() const;
	Node<T>* getNext() const;
	Node<T>* getPrevious() const;

	void setData(const T&);
	void setNext(Node<T>*);
	void setPrevious(Node<T>*);
};

template <class T>
Node<T>::Node(T info, Node<T>* nx, Node<T>* prv)
	:data(info), next(nx), previous(prv) {}

template <class T>
T Node<T>::getData() const { return data; }

template <class T>
Node<T>* Node<T>::getNext() const { return next; }

template<class T>
Node<T>* Node<T>::getPrevious() const { return previous; }

template<class T>
void Node<T>::setData(const T& info) { data = info; }

template<class T>
void Node<T>::setNext(Node<T>* nx) { next = nx; }

template<class T>
void Node<T>::setPrevious(Node<T>* prv) { previous = prv; }

template<class T>
class List {
private:
	Node<T>* head {};
	//Node<T>* tail {};
	size_t numberOfElements {};

public:
	List();
	virtual ~List();

	void add(const T&);
	void remove(size_t);
	bool empty() const ;
	size_t getNumberOfElements() const;
	void printList() const;

	List(const List&) = delete;
	List(List&&) = delete;
	List& operator=(List) = delete;
};

template<class T>
List<T>::List() {}

template<class T>
List<T>::~List() {
	while (head) {
		const auto tmp { head };

		head = head->getNext();
		delete tmp;
	}
}

template<class T>
void List<T>::add(const T& info) {
	if (empty())
		head = new Node<T>(info);
	else {
		auto temporal { head };

		for (; temporal->getNext(); temporal = temporal->getNext());

		temporal->setNext(new Node<T>(info, nullptr, temporal));
	}

	++numberOfElements;
}

template<class T>
// Position starts at 0
void List<T>::remove(size_t position) {
	if (numberOfElements > position) {
		auto temporal { head };

		for (size_t i {}; i < position; ++i)
			temporal = temporal->getNext();

		if (temporal == head)
			head = temporal->getNext();
		else {
			temporal->getPrevious()->setNext(temporal->getNext());

			if (temporal->getNext())
				temporal->getNext()->setPrevious(temporal->getPrevious());
		}

		delete temporal;
		--numberOfElements;
	}
}

template<class T>
bool List<T>::empty() const { return head == nullptr; }

template<class T>
size_t List<T>::getNumberOfElements() const { return numberOfElements; }

template<class T>
void List<T>::printList() const {
	std::cout << "----------Printing List---------\n";

	for (auto temporal { head }; temporal; temporal = temporal->getNext())
		std::cout << temporal->getData() << '\n';
}

class Person {
private:
	std::string name;
	std::string id;

public:
	Person(const std::string&, const std::string&);
	virtual ~Person();

	friend std::ostream& operator <<(std::ostream& out, const Person& p) {
		return out << "Name: " << p.name << "\tID: " << p.id;
	}
};

Person::Person(const std::string& n, const std::string& i) : name(n), id(i) {}
Person::~Person() {}

int main() {
	List<int> list1;
	List<Person> list2;

	for (int i = 0; i < 10; i++)
		list1.add(i * 3);

	Person per1("A", "1");
	Person per2("B", "2");
	Person per3("C", "3");
	Person per4("D", "4");
	Person per5("E", "5");

	list2.add(per1);
	list2.add(per2);
	list2.add(per3);
	list2.add(per4);
	list2.add(per5);

	list1.printList();
	list2.printList();

	list2.remove(4);
	list2.remove(0);
	list2.printList();
}



----------Printing List---------
0
3
6
9
12
15
18
21
24
27
----------Printing List---------
Name: A ID: 1
Name: B ID: 2
Name: C ID: 3
Name: D ID: 4
Name: E ID: 5
----------Printing List---------
Name: B ID: 2
Name: C ID: 3
Name: D ID: 4

Last edited on
sarvcr (16)
Thanks you all. I corrected the wrong syntax that I had and the used seeplus' code as a huge reference. It's working perfectly on the single file.

For some reason, when I finally understood everything and copied it into separate file (node and list .h and node and list.cpp), when I create the list in the same way as I did before, it throws an error:

1>------ Build started: Project: Proyecto 2 V1, Configuration: Debug x64 ------
1>main.cpp
1>main.obj : error LNK2019: unresolved external symbol "public: __cdecl List<class TrajeAbst>::List<class TrajeAbst>(void)" (??0?$List@VTrajeAbst@@@@QEAA@XZ) referenced in function main
1>main.obj : error LNK2019: unresolved external symbol "public: virtual __cdecl List<class TrajeAbst>::~List<class TrajeAbst>(void)" (??1?$List@VTrajeAbst@@@@UEAA@XZ) referenced in function main
1>main.obj : error LNK2019: unresolved external symbol "public: void __cdecl List<class TrajeAbst>::add(class TrajeAbst *)" (?add@?$List@VTrajeAbst@@@@QEAAXPEAVTrajeAbst@@@Z) referenced in function main
1>main.obj : error LNK2019: unresolved external symbol "public: void __cdecl List<class TrajeAbst>::printList(void)const " (?printList@?$List@VTrajeAbst@@@@QEBAXXZ) referenced in function main
1>E:\I CICLO 2022\Progra II\Proyectos\Proyecto2\Proyecto 2 V1.a\Proyecto 2V1\x64\Debug\Proyecto 2 V1.exe : fatal error LNK1120: 4 unresolved externals
1>Done building project "Proyecto 2 V1.vcxproj" -- FAILED.
========== Build: 0 succeeded, 1 failed, 0 up-to-date, 0 skipped ==========

I made sure that the files are correctly included and that I didn't make any mistake while copying it. If anyone knows how to solve this or why this happens, I'll be really glad if you could help me. I'll be doing some reasearch on my own to try to solve it.
Last edited on
seeplus (6457)
As Node and List are templated, the definitions and the function bodies have to go in the same header file. You can't split Node into node.h and node.cpp or List into List.h and List.cpp
George P (5598)
The most separation that can be done with templated code is to slap all the code into a header file. In the case with the code that seeplus provided you can have Node.h and List.h.
sarvcr (16)
It's working perfectly now. I really appreciate all the help you've given to me, you guys literally saved me. Thank you so much!
Topic archived. No new replies allowed.