CFORBEGINNERS.COM

Create a Linked List

First let us imagine a student. Students have attributes such as a name, age, GPA, and ID number. Of course, a next pointer is required to link each node to another. Here is a visual representation of this particular student node.            
Here is the class representation

class Node
{
private:
	string name;
	int age,ID;
	double GPA;
	Node *next;

public:
	Node(string&,int&,int&,double&);
};

Notice how the constructor takes in a string, two integers, and a double. This is because whenever a variable of Node type is created it will require a string (name), two integers (age,ID), and a double (GPA). The constructor will immediately assign each objects members, in this example each object is a student.

When creating a link list it's common to introduce another class, if the objects of the Node class hold students records then you can think of this next class as the folder that holds students records. Think of it like a heirarchy, if we have ten individual sheets of paper each one containing a students records. We don't want to leave these pieces of paper lying around it would be more organized if we took these ten papers and put it into a single folder. Now in the future we can go directly to the single folder see that it's labeled Student Records on the front of the cover and then go about looking for a specific student. For clarity this class will be named Folder, here's how it looks.

class Folder
{
private:
	Node *root;

public:
	Folder();
	void addNode (string&,int&,int&,double&);
	void traverseList();
};

Notice the pointer 'root'. The variable root is necessary because we need a single variable that will hold all of the nodes together a source if you will. As the name implies, we only need one root, the reason why we wouldn't put root in the Node class is because by design there will be more than one nodes created, if root was a part of the node class then we would create a new root every time a new node is created resulting in multiple roots which really defeats the purpose of root itself. Since only one root is needed and because we only need one Folder to put student records in which means only one Folder class will be created thus only root it makes sense for root to be put inside the Folder class. The addNode function takes in the associated data that a node will hold; name, age, ID, and GPA to then be given to the Node constructor. The traverseList function is simply used to iterate through a link list.

In this particular example there is gonna be five files, two .h files and three .cpp files. Of course, if one wanted to they could easily put all of the code into the main.cpp file but splitting the files up calls for better organization. First create a Node.h file, we have essentially already seen this code. The new lines of code are bolded.

//Node.h
#pragma once

#include <string>
#include <iostream>
using namespace std;


class Node
{
friend class Folder;

private:
	string name;
	int age,ID;
	double GPA;
	Node *next;

public:
	Node();
	Node(string&,int&,int&,double&);
};

The #pragma once is a header guard and essentially works the same way as #ifndef,#define,#endif, by keeping the compiler from including the header file more than once, it should be used with every .h file. Also, we need to include the string library as we are using string data types. Lastly, the class Folder (which will be made shortly) is given friend benifits by being allowed access to class Nodes private members, you will see why we need to do this in a moment.

//Folder.h
#pragma once
#include <string>
using namespace std;

class Node;
class Folder
{
private:
	Node *root;

public:
	Folder();
	~Folder();//Destructor
	void addNode (string&,int&,int&,double&);
	void traverseList();
};

First take notice to the class Node statement. This is sometimes referred to as pre-defining a class. Here it's required to pre-define class Node since we are declaring a pointer called root that points to Node values. By pre-defining the class Node we are essentially telling the compiler that there is a class called Node so let us declare variables that hold Nodes. A destructior is declared here because we will need to free memory that the Folder class will allocate once it goes out of scope. Now that we have the .h files, sometimes called the interface we must implement the functions that we have declared inside the classes, this is what's done in the .cpp files.

//Node.cpp
#include "Node.h"

Node::Node()//used for when root is allocated memort in the Folder class constructor
{

}

Node::Node(string& n,int& a,int& i,double& g)
{
	name = n;
	age = a;
	ID = i;
	GPA = g;
	next = NULL;
}

The only function member of class Node is the constructor, the constructor takes in four parameters, a string, two integers, and a double and uses these parameters to initialize an object of class Node, lastly, the pointer next is initialzed to NULL. Referring back to the picture of a linked list, the last node always points to NULL, this is how the program will be able to tell when it's at the last node. As the program runs and the user creates more and more nodes, a nodes next will be reinitialzed to point to another node, however, the last node will not be reinitialzed, thus remain pointing at NULL.

//Folder.cpp
#include "Folder.h"
#include "Node.h"



Folder::Folder()
{
//allocate memory for root
	root = new Node();
	root = NULL;
}

Folder::~Folder()
{
//free memory once Folder class has gone out of scope
 	delete root;
}

void Folder::addNode(string& name, int &age, int &ID, double &GPA)
{
	Node *new_student = new Node (name,age,ID,GPA);//create a new node
	
	if (root == NULL)//empty link list
	{
		root = new_student;
		return;
	}

	else
	{
		
	Node *temp_node = root;//declares a Node data type to start at root node
	
	while (temp_node->next != NULL)//traverses to the end of the link list
		{
			temp_node = temp_node->next;
		}

	temp_node->next = new_student;
	}
}

void Folder::traverseList()
{
	Node *temp_node = root;
	
	while (temp_node != NULL)
	{
		cout<<temp_node->name<<endl;
		temp_node = temp_node->next;
	}
}

The addNode function takes in four parameters and immediately creates a new node with those four variables. Remember, because the constructor of the Node class is designed to take in four parameters it's necessary to have four variable to give whenever creating a new node. This is strictly by design, an additional constructor for the Node class made with no parameters therefore giving the us the option to create nodes with no parameters, we used this option only once for the root pointer.

if (root == NULL)//empty link list
	{
		root = new_student;
		return;
	}

The if statement is used to check for an empty linked list, remember that constructor of the Folder class intialized root to NULL therefore if root equals NULL the linked list is empty. If this is true, root is assigned to new_student and the functions returns control to main since there is nothing left to do.

else
	{
		
	Node *temp_node = root;//declares a Node data type to start at root node
	
	while (temp_node->next != NULL)//traverses to the end of the link list
		{
			temp_node = temp_node->next;
		}

	temp_node->next = new_student;
	}

If root does not equal NULL and therefore the linked list isn't empty the program will move to the else statement. First we create a temporary pointer that points to Node values and assign it to roots value. This temp_node will act as roots decoy, temp_node has the same value as root and if we so happen to change temp_node we won't directly change root. The while loop traverses all the way down the linked list, if temp_node->next doesn't equal NULL then temp_node moves over to its neighbor node this is done with temp_node = temp_node->next. Finally, when the while loop has successfully traversed all the way down the linked list, temp_node->next (which at this instant equals NULL) is intialized to the new node that was created at the beginning of the addNode function, new_student.

void Folder::traverseList()
{
	Node *temp_node = root;
	
	while (temp_node != NULL)
	{
		cout<<temp_node->name<<endl;
		temp_node = temp_node->next;
	}
}

The traversList function is used just to print out all the nodes (or students) in the linked list. It begins by creating the familiar temp_node pointer, this temporary pointer is again used to traverse through a linked list the same way it did in the addNode funciton with only a few differences. First notice how the while condition is a little different than the one in the addNode function. instead of the conditon being temp_node->next != NULL it's just temp_node != NULL. The former condition will break the while loop out too quickly and the last node (or student) will not be printed out. Finally, notice how only the name of a node is printed out in the cout statement. This is simply because we are not able to just simple print out an object like this.

cout<<temp_node<<endl;

Remember that an object of the Node class in this case temp_node has many member variables name, age, ID, GPA. We can't simply just print out an object because of this, unless of course we overload the operator giving the program specifice instructions on what to do when an event like this arises. However, operator overloading is out of the scope of this lesson, this is why I have just printed out the nodes name since this is allowed without any overloading.

Now all we need to do is set up main to instantiate the classes

//main.cpp
#include <iostream>
//must include header files
#include "Folder.h"
#include "Node.h"

using namespace std;

int main()
{
//declare variables
	Folder rec;
	string name;
	int age,ID;
	double GPA;

	while (true)
	{
//input name, age, ID, and GPA and then send these variables to the addNode function
		cout<<"Enter name (or quit to exit)"<<endl;
		cin>>name;
		if (name == "quit") break;
		cout<<"Enter age"<<endl;
		cin>>age;
		cout<<"Enter ID number"<<endl;
		cin>>ID;
		cout<<"Enter GPA"<<endl;
		cin>>GPA;
		rec.addNode(name,age,ID,GPA);
}
	rec.traverseList();//Print out the linked list members
	
system ("pause");
return 0;
}

At last a linked list has been constructed, in your compiler simple create a Node.h, Folder.h, Node.cpp, Folder.cpp, and main.cpp. Theres always ways to improve the code, and this linked list is no exception, happy coding!