Linked List Using Templates in C++
A template is a class-defined datatype created when the datatype to use is in question. Using a template gives the ability to be flexible with datatypes and use only that datatype provided as input during compilation time.
This article discusses how we can form a linked list using a template in C++.
Linked List Using Templates in C++
This article presents a 3-part program containing the main file (.cpp file) that extracts the node and linked list data from its header files (.h). The program provides input through the main file containing the driver method.
First, let’s understand how to create nodes using templates.
Initialize Data Members Inside the Template Class in C++
This is the first header file that the program initiates during compilation. Here two classes are defined: create_list and Init.
// file: init.h
#ifndef _INIT_H
#define _INIT_H
template <typename T>
class create_list;
template <typename T>
class Init {
friend class create_list<T>;
public:
Init(T data = 0, Init<T> *next = 0) : data(data), next(next) { /* empty */
}
private:
T data;
Init<T> *next;
};
#endif
The syntax template<typename T> class create_list; creates a class of type T. This tells the compiler to use T as a user-defined datatype until a primary datatype is given.
Using templates in a C++ program provides an interesting feature to define a variable using a user-defined datatype. Similarly, methods can also be defined as datatype, making it a useful tool for programmers.
Using the syntax friend class create_list<T>; directs the compiler to tag the class create_list as a friend class. A friend class gets its private and public members shared in this header file.
Once the class create_list is defined, the class Init is created with type T.
When the compiler executes the syntax friend class create_list<T>;, it directs the compiler to use the private and public members from the header file create_list.h in this class.
Two main variables are required to create a Linked List using templates in C++, a data variable that stores the input value and a node variable that points to the next pointer.
In this program, these two main variables are defined as data and next. Then the private and public members of constructors are initialized using default values before operations are conducted on them.
Lastly, the member variables of constructor public get initialized with member variables of constructor private.
Create Class Linked List Using Template in C++
This section discusses the second part out of the three parts of this article. The program discussed here imports the init.h header file using the syntax #include "init.h" and uses its data members to create the Linked List using the template in C++.
Inside the template class create_list, there are four public members - a constructor create_list(), a destructor ~create_list(), and two member methods void insert() and void display().
Two private members are defined, pointers *up and *down, with datatype T. This class-defined datatype allows the program to use any datatype in the driver program, thus saving the programmer from going back to the source code to modify things.
Pointer variables head and tail are initialized inside the constructor create_list.
template <typename T>
create_list<T>::create_list() : up(0), down(0)
Inside the destructor ~create_list(), the objects stored inside memory are released.
Here, if the object up has some value stored inside it, it is copied inside pointer *a; pointer *b is given a 0 value.
Pointer variables head and tail are initialized inside the constructor create_list.
template <typename T>
create_list<T>::~create_list() {
if (up) {
Init<T> *a = up;
Init<T> *b = 0;
For the number of times a has values, it gets copied to b, which acts as a placeholder for objects inside the variable a. Then, a is given the value stored inside the next pointer, and in the end, values inside b are released.
while (a) {
b = a;
a = a->next;
delete b;
}
Method to Add Values Inside Linked List
This part of the program creates a method with class type T that takes in info as a parameter. Inside the method, an if-else condition is given.
The down variable is used to point to the next pointer. Here, the if condition checks that if the variable up is non-empty, it creates a new object from parameter info and transfers it to variable down.
Inside the else condition, the variable up is given the value of down, which is the object created from the parameter value.
template <typename T>
void create_list<T>::insert(T value) {
if (up) {
down->next = new Init<T>(value);
down = down->next;
} else {
up = down = new Init<T>(value);
}
}
Method to Print the Values Inside Linked List
This method prints the contents of the linked list. The pointer value inside the variable up is copied to a variable *a.
For the number of times the values are there in the given pointer a, the while loop prints it and then shifts a to the up pointer.
template <typename T>
void create_list<T>::display() {
if (up) {
Init<T> *a = up;
while (a) {
cout << a->data << "->";
a = a->next;
}
The section below shows the code to create a linked list using C++ templates:
// file createlist.h
#ifndef _CREATELIST_H
#define _CREATELIST_H
#include <iostream>
using namespace std;
#include "init.h"
template <typename T>
class create_list {
public:
create_list();
~create_list();
void insert(T);
void display();
private:
Init<T> *up;
Init<T> *down;
};
#endif
template <typename T>
create_list<T>::create_list() : up(0), down(0) { /* empty */
}
template <typename T>
create_list<T>::~create_list() {
if (up) {
Init<T> *a = up;
Init<T> *b = 0;
while (a) {
b = a;
a = a->next;
delete b;
}
cout << endl;
}
}
template <typename T>
void create_list<T>::insert(T value) {
if (up) {
down->next = new Init<T>(value);
down = down->next;
} else {
up = down = new Init<T>(value);
}
}
template <typename T>
void create_list<T>::display() {
if (up) {
Init<T> *a = up;
while (a) {
cout << a->data << "->";
a = a->next;
}
cout << endl;
}
}
Create the Linked List Using Template From .cpp File
This is the final part of the program. It includes the create_list header file, and the main function is created.
The datatype of the linked list template is set inside the main function. Here, char is used to print the ASCII values of the numbers inside the given for loop.
The for loop runs ten times and prints the ASCII values from 65 to 75, letters A to J. The list.insert(i); syntax passes the value of i to the method add, which gets inserted into the linked list, and then another value is passed.
Finally, list.display(); prints the contents of the linked list.
// file run.cpp
#include "create_list.h"
int main(int argc, char *argv[]) {
create_list<char> created_list;
for (char i = 65; i < 75; i++) created_list.insert(i);
created_list.display();
Conclusion
This article provides a detailed explanation of how linked lists are created using templates in C++. After going through the article, the reader will be able to create programs with user-defined data types and use linked lists with multiple data types at once.