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
 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150`` ``````#include #include using namespace std; template class List; template class Node { private: T data; Node next; Node previous; public: Node(T, Node, Node); virtual ~Node(); T getData(); Node* getNext(); Node* getPrevious(); void setData(T); void setNext(Node*); void setPrevious(Node*); }; template Node::Node(T info, Node nx, Node prv) :data(info), next(nx), previous(prv) {} template Node::~Node() {} template T Node::getData() { return data; } template Node* Node::getNext() { return next; } template Node* Node::getPrevious() { return previous; } template void Node::setData(T info) { data = info; } template void Node::setNext(Node* nx) { next = nx; } template void Node::setPrevious(Node* prv) { previous = prv; } template class List{ private: Node* head; Node* temporal; Node* tail; int numberOfElements; public: List(); virtual ~List(); void add(const T&); void remove(int); bool empty(); int getNumberOfElements(); void printList(); }; template List::List():head(NULL),temporal(NULL),tail(NULL),numberOfElements(0) {} template List::~List(){} template void List::add(const T& info){ if (empty) { head = new Node(info, NULL, NULL); numberOfElements++; } else { temporal = head; while (temporal->getNext() != NULL) { temporal = temporal->getNext(); } Node* newNode = new Node(info, NULL, temporal); temporal->setNext(newNode); numberOfElements++; } } template void List::remove(int position){ temporal = head; for (int i=0;igetNext(); } temporal->getPrevious()->setNext(temporal->getNext()); temporal->getNext()->setPrevious(temporal->getPrevious()); delete temporal; numberOfElements--; } template bool List::empty() { return head == NULL; } template int List::getNumberOfElements() { return numberOfElements; } template void List::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 list1; List 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
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
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.
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
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
As a first refactor, consider (note tail isn't used):

 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174`` ``````#include #include template class Node { private: T data {}; Node* next {}; Node* previous {}; public: Node(T, Node* = nullptr, Node* = nullptr); T getData() const; Node* getNext() const; Node* getPrevious() const; void setData(const T&); void setNext(Node*); void setPrevious(Node*); }; template Node::Node(T info, Node* nx, Node* prv) :data(info), next(nx), previous(prv) {} template T Node::getData() const { return data; } template Node* Node::getNext() const { return next; } template Node* Node::getPrevious() const { return previous; } template void Node::setData(const T& info) { data = info; } template void Node::setNext(Node* nx) { next = nx; } template void Node::setPrevious(Node* prv) { previous = prv; } template class List { private: Node* head {}; //Node* 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 List::List() {} template List::~List() { while (head) { const auto tmp { head }; head = head->getNext(); delete tmp; } } template void List::add(const T& info) { if (empty()) head = new Node(info); else { auto temporal { head }; for (; temporal->getNext(); temporal = temporal->getNext()); temporal->setNext(new Node(info, nullptr, temporal)); } ++numberOfElements; } template // Position starts at 0 void List::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 bool List::empty() const { return head == nullptr; } template size_t List::getNumberOfElements() const { return numberOfElements; } template void List::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 list1; List 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
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
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
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.
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.