generic link list using templates

[HUPextreme]

hi there, i'm quite the beginner at c++, just got to my last project for my course to do.

The project asks me to create a family tree using linked list. It says the tree and its components should be templated so it can have a family tree of any object- humans, animals, commercial enterprises etc.

Well i've created a family tree for humans which is able to add nodes, delete nodes etc. But i'm confused about making it generic for other objects. What i currently can only think of is a repeat of all my functions for a different object.

here is my class for a list

#ifndef LINKEDLIST_H
#define LINKEDLIST_H
#include <iostream>
#include <vector>
using namespace std;

template <class T, class T2>
class LinkedList
{
private:
	// Declare a structure for the list
	struct ListNode
	{
		T age, children, generation;
		T2 name, partner, sex, childname, birth, death, parenta, parentb;
		vector<string> child;
		struct ListNode *next;
	};
	
	ListNode *head; // List head pointer
	

public:
	LinkedList(void) // Constructor
	{ head = NULL; }
	~LinkedList(void); // Destructor
	void appendNode(void);
	int readfile(void);
	void insertNode(void);
	int deleteNode(void);
	void displayList(void);
	void options(void);
};

// Destructor
// This function deletes every node in the list.
template <class T, class T2>
LinkedList<T, T2>::~LinkedList(void)
{
	ListNode *nodePtr, *nextNode;
	nodePtr = head;
	while (nodePtr != NULL)
	{
		nextNode = nodePtr->next;
		delete nodePtr;
		nodePtr = nextNode;
	}
}
#endif

and here is part of the 'human' family tree cpp, which contains the functions

#include <iostream>
#include <string>
#include <fstream>
#include "nodes.h"

using namespace std;

void main(void)
{
	cout << "\t\t::|| Welcome to the Family Tree Generator ||::" << endl;
	cout << "\nWhat would you like to do?" << endl;
	cout << endl;
	cout << "[1] Start to enter details for family tree" << endl;
	cout << "\t-You will need to enter the first member of the family and work your way down the family chain." << endl;
	cout << endl;
	cout << "[2] Input a family tree from a file" << endl;
	cout << "\t-If you have already created a family tree select this option." << endl;
	cout << endl;

	LinkedList<int, string> list;

	int keystroke;
	cout << endl;
	cout << endl;
	cout << "Please select from the options above: ";
	

	do {
		fflush(stdin); // flush standard input
		scanf_s("%d",&keystroke);

		
		switch( keystroke ) 
		{
			case 1:
				cout << endl;
				// Build the list
				list.appendNode();
				break;

			case 2:
				cout << endl;
				// Build the list from a file
				list.readfile();
				break;

			default:
				
				cout <<"Please enter a number between 1 and 2: ";			
		}
	}

	while (!(1<=keystroke && keystroke<=2));
	


	cout << "Here are the initial values:\n";
	list.displayList();
	cout << endl;
	
	//cout << "Now inserting the value 5.\n";
	//list.insertNode(18480109, "David", "male");
	
	//list.displayList();
	cout << endl;

	//cout << "Now deleting a member.\n";
	//list.deleteNode();
	//cout << "Here are the nodes left.\n";
	//list.displayList();
	cout << endl;

}

template <class T, class T2>
void LinkedList<T, T2>::appendNode(void)
{
	ListNode *newNode, *nodePtr, *temp, *gen;
	// Allocate a new node & store num
	newNode = new ListNode;
	int countchild;
	cin.ignore();
	cin.clear();

	cout << "Please enter the name of the person: ";
	getline(cin,newNode->name);
	newNode->generation = 1; //Enter a dummy value for generation

	cout << "Please enter the sex of the person [M] or [F]: ";
	getline(cin,newNode->sex);

	cout << "Please enter their date of birth (DD/MM/YYYY): ";
	getline(cin,newNode->birth);

	cout << "Please enter their date of death (DD/MM/YYYY): ";
	getline(cin,newNode->death);

	cout << "Please enter the name of their partner: ";
	getline(cin,newNode->partner);

	cout << "How many children : ";
	cin >> newNode->children;
	countchild = newNode->children;
	
	if (newNode->children != 0){
		cout << "\nPlease enter each child's name, seperating by pressing enter : ";
		cout << endl;
		cin.ignore();

		for (int i = 0; i < newNode->children; ++i) 
		{
			cout << "Child [" << i+1 << "]: ";
			getline(cin,newNode->childname);
			newNode->child.push_back(newNode->childname);
		}
	}
	
	newNode->next = NULL;
	cout << endl;
.
.
.
.

as you can see it takes a void input to the appendnode function, then all the data types are added to the node within this function.

Is there an easier way to make this generic without repeating all the code again, i.e. a different appendnode function etc.

Thanks in advance.

[Stinomus]

Ok what it is asking is for you to create a generic linked list.

Using template <class T> before you declare the class allows you to specify, when you use the class, the type that 'T' is.

For example a node in a linked list might be:

template <class T>
class Node
{
  Node(T _data){ data=_data; }
  Node<T> *next;
  T data;
};

Then you would use it in the form:

Node<std::string> *n = new Node<std::string>("Hello");

So you can see that 'T' is resolved at compile-time so in your binary a data structure for Node will be created and in place of 'T' it will put 'std::string'.
You can therefore declare multiple Nodes of different types.

Your linked list class may still only be of one type though, that is you could not have a linked list that mixed both humansand animals.

Once you have a generic linked list you can give it any type of object (fundamental types or user-defined types), be it a human, animal, integer, string, etc...

[HUPextreme]

thanks for the response, but i'm still confused, i understand that a generic node can be made for a single data type, but my nodes contains multiple data, ints and strings.

So how would i have another node for lets say animals, which contains different collection of data.

something like this??

struct humanNode
	{
		T age, children, generation; //ints
		T2 name, partner, sex, childname, birth, death, parenta, parentb; // strings
		vector<string> child;
		struct humanNode *next;
		
	};

		struct animalNode
	{
		T2 name;
		vector<string> child;
		struct animalNode *next;
	};

	
	ListNode *head; // List head pointer
	animalNode *head;

[Lerner]

Create a node using template syntax as per Stinomus' post above.
Create a list using template declarations for the List class which has all the variables and methods you want to use.
Create whatever user defined classes you need to place in the list.
Declare a separate node type for each class you want to put in the list.
Declare a separate list for each class you want a list created for.

//declare typical classes
class Human
class Animal

//write template classes to use user defined types
template class node
template class list

//declare variables to use in specific program without rewrite entire code for each class used in this program.
Human humanNode
Animal animalNode
list<Human> humanList;
list<Animal> animalList;

//use declared variables however you want
while(1)
{
    //obtain information for specific Human
    humanNode.getData();
    //insert node into list of Humans
    humanList.insert(humanNode);

    //obtain information for specific Animal
    animalNode.getData();
   //insert node into list of Animals
   animalList.insert(animalNode);
   //etc
}

[Stinomus]

thanks for the response, but i'm still confused, i understand that a generic node can be made for a single data type, but my nodes contains multiple data, ints and strings.

As Lerner said, you want to encapsulate the definition of your types (human, animal, etc...) into classes. That way you have a class that has all of your data describing your types (name, age, sex, etc...).
The idea of templates is that they are generic, you don't need to alter the Node and have a humanNode, animalNode, etc...as the Node is simply a container, it can hold any type of class.

[HUPextreme]

appreciating all the help so far, but i'm getting lost again with the structs and classes and templates :confused:

so what i have currently is

class human {
public:
	int children, generation;
	string name, partner, sex, childname, birth, death, parenta, parentb;
	vector<string> child;
};


template <class T>
class LinkedList
{
private:

	// Declare a structure for the list
	struct ListNode
	{
		T _data;		
		struct ListNode *next;
		
	};
	
	ListNode *head; // List head pointer


public:
	LinkedList(void) // Constructor
	{ head = NULL; }
	~LinkedList(void); // Destructor
	void appendNode(void);
	int readfile(void);
	void insertNode(void);
	int deleteNode(void);
	void displayList(void);
	void options(void);
};

then in my cpp i declare a new node

LinkedList<human> list;

but the struct is not able to find any of the human data types, like name etc.

I think i'm not getting the basics still. I thought i would create a list for a single data type then generalise it at the end thinking it was easy, sigh.

[Stinomus]

appreciating all the help so far, but i'm getting lost again with the structs and classes and templates :confused:

so what i have currently is

class human {
public:
	int children, generation;
	string name, partner, sex, childname, birth, death, parenta, parentb;
	vector<string> child;
};


template <class T>
class LinkedList
{
private:

	// Declare a structure for the list
	struct ListNode
	{
		T _data;		
		struct ListNode *next;
		
	};
	
	ListNode *head; // List head pointer


public:
	LinkedList(void) // Constructor
	{ head = NULL; }
	~LinkedList(void); // Destructor
	void appendNode(void);
	int readfile(void);
	void insertNode(void);
	int deleteNode(void);
	void displayList(void);
	void options(void);
};

then in my cpp i declare a new node

LinkedList<human> list;

but the struct is not able to find any of the human data types, like name etc.

I think i'm not getting the basics still. I thought i would create a list for a single data type then generalise it at the end thinking it was easy, sigh.

Ok now you're on the right track. The idea is that template classes should not depend on explicit data types, so you're getting there with that now.

Now that you have a LinkedList of humans (that's the best way to read the <> brackets), you need to add a human to it.
So create a human and populate it:

human h;
h.name = "bill";
etc...

Then you want to call insert on your list to add the human to the list.

And remember a class is collection of data and methods required to describe and operate on a 'thing'...in this case a human. A struct is a class but with implicit public specifiers on everything...structs have their uses but in most cases they can be avoided for OO programming in favour of classes. And templates are essentially for generic programming - most often used for containers - where the actual type of data is irrelevant and has no impact on the functionality of the template class, for example if you have a list, it could be a list of anything and it works the same no matter what you put in it but you don't want to have to write a new list for every single class, struct or fundamental datatype.

[HUPextreme]

Thank you very very much Stinomus and Lerner, i finally got it. All working now.

so like you said i got the required data for human a via a.name, a.birth etc, then at the end of the collection declared the data for the node as

newNode->_data = a;

as _data takes in the humas class as templated before.

appreciate all the explaining, i think i get everything now about how nodes and linked lists work.