Linked List Template and Binary Search Tree

jason9 (6)
I am posting this because after all my research I could not find a good example of both a templatized linked list and binary search tree. These are what I was able to come up with hope this helps anyone looking for something like this. The template linked list is very useful.

ListNode.h
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
 
#ifndef LIST_NODE_H
#define LIST_NODE_H

template <typename T> 
class List;

template <typename T>
class ListNode //nodes to be contained with a list
{
	friend class List<T>;

public:
	ListNode(T);
	T getData();

private:
	T data; //templatized data stored in node
	ListNode* nextPtr; //pointer to the next node in list
};

template <typename T>
ListNode<T>::ListNode(T dataIn)
{
	data = dataIn; //stores data in node
	nextPtr = 0; //initializes point to next node to null
}

template <typename T>
T ListNode<T>::getData() //returns data stored in node
{
	return data;
}

#endif


List.h
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
 
#ifndef LIST_H
#define LIST_H

#include <iostream>
using namespace std;

#include "ListNode.h"

template <typename T>
class List //linked list of ListNode objects
{
public:
	List();
	~List();
	void insertNewNode(T); //fucntion used to insert new node in order in the list
	void print(); //prints the contents of the linked list
	ListNode<T>* search(T); //searches for a value in the linked list and returns the point to object that contains that value

private:
	ListNode<T> *startPtr; //stores the pointer of first object in the linked list
	ListNode<T> *endPtr; //stored the pointer of the last object in the linked list
	bool isEmpty(); //utility functions used to see if the list contains no elements
	void insertBegin(T); //inserts new node before the first node in the list
	void insertEnd(T); //inserts new node after the last node in the list
};



template <typename T>
List<T>::List() //creates list with start and end as NULL
{
	startPtr = NULL;
	endPtr = NULL;
}

template <typename T>
List<T>::~List()
{
	if ( !isEmpty() ) // List is not empty
   {    
      ListNode<T> *currentPtr = startPtr;
      ListNode<T> *tempPtr;

      while ( currentPtr != 0 ) // delete remaining nodes
      {  
         tempPtr = currentPtr;
         currentPtr = currentPtr->nextPtr;
         delete tempPtr;
      }
   }
}

template <typename T>
bool List<T>::isEmpty()
{
	if(startPtr == NULL && endPtr == NULL) //if the start pointer and end pointer are NULL then the list is empty
		return 1;
	else
		return 0;
}

template <typename T>
void List<T>::insertBegin(T dataIn)
{
	if(isEmpty()) //if the list is empty create first element of the list
	{
		ListNode<T> * newPtr = new ListNode<T>(dataIn); //creates new node
		startPtr = newPtr; //start and end pointer are same becuase there is only one object in list
		endPtr = newPtr;
	}else //if node(s) exist in list insert additional object before the first
	{
		ListNode<T> * newPtr = new ListNode<T>(dataIn);
		newPtr->nextPtr = startPtr; //the next pointer of the new node points to the node that was previously first
		startPtr = newPtr; //the pointer for the new node is now the starting node
	}
}

template <typename T>
void List<T>::insertEnd(T dataIn)
{
	if(isEmpty()) //if the list is empty create first element of the list (same as first case in insert at begin)
	{
		ListNode<T> * newPtr = new ListNode<T>(dataIn);
		startPtr = newPtr;
		endPtr = newPtr;
	}else //if node(s) exist in the list then insert new node at the end of the list
	{
		ListNode<T> * newPtr = new ListNode<T>(dataIn);
		endPtr->nextPtr = newPtr; //the current last node's next pointer points to the new node
		endPtr = newPtr; //the new node is now the last node in the list
	}
}

template <typename T>
void List<T>::insertNewNode(T dataIn) //general funtionn to insert new node the proper order in the list
{
	if(isEmpty()) //if there is no nodes in the list simply insert at beginning
	{
		insertBegin(dataIn);
	}else //otherwise
	{
		if(dataIn < startPtr->data) //if the data of the new object is less than than the data of first node in list insert at beginning
		{
			insertBegin(dataIn);
		}
		else if(dataIn >= endPtr->data) //if the data of the new object is greater than than the data of last node in list insert at end
		{
			insertEnd(dataIn);
		}
		else //the new node is being inserted in order but not at the beginning or end
		{
			ListNode<T> * currentPtr = startPtr;
			ListNode<T> * newPtr = new ListNode<T>(dataIn); //creates new node
			while(currentPtr != endPtr) //runs until the end of the list is reached
			{
				if((newPtr->data < currentPtr->nextPtr->data) && (newPtr->data >= currentPtr->data)) //if the data of the new node is less the data in the next node and greater than the data in the current node, insert after current node 
				{
					ListNode<T> * next = currentPtr->nextPtr; 
					currentPtr->nextPtr = newPtr; //current nodes next pointer now points to the new node
					newPtr->nextPtr = next; //the new nodes next pointer now points the node previously after the current node
					break;
				}
				currentPtr = currentPtr->nextPtr; //moves to the next node in the list
			}
		}
	}
}

template <typename T>
void List<T>::print()
{
	if(isEmpty())
	{
		cout << "The list is empty" << endl;
	
	}else
	{
		ListNode<T> * currentPtr = startPtr;

		cout << "The contents of the list is: ";
		while(currentPtr != NULL) //prints until the end of the list is reached
		{
			cout << currentPtr->data << ' ';
			currentPtr = currentPtr->nextPtr; //moves to next node in list
		}
		cout << endl;
	}
}

template <typename T>
ListNode<T>* List<T>::search(T key) //search functions that searches for node that contains data equal to the key
{
	ListNode<T>* nodePtr;
	bool found = false;

	nodePtr = startPtr;

	while((!found) && (nodePtr != NULL)) //runs through list until data is found within a node or end of list is reached
	{
		if(nodePtr->data == key) //if the node's data equals the key then the node has been found
			found = true;
		else
			nodePtr = nodePtr->nextPtr; //moves to next node in list
	}
	return nodePtr; //returns pointer to the node that contains data equal to key (NULL if not found)
}
#endif

jason9 (6)
TreeNode.h
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
 
#ifndef TREE_NODE_H
#define TREE_NODE_H

template <typename T> 
class Tree;

template <typename T>
class TreeNode
{
	friend class Tree<T>;

public:
	TreeNode(T); 
	T getData(); //returns data stored in node

private:
	T data;
	TreeNode* leftPtr; //pointer to left child node of node
	TreeNode* rightPtr; //pointer to right child node of node
};

template <typename T>
TreeNode<T>::TreeNode(T dataIn)
{
	data = dataIn;
	leftPtr = 0; //pointer to left and right child nodes are initilized to NULL
	rightPtr = 0;
}

template <typename T>
T TreeNode<T>::getData()
{
	return data;
}

#endif


Tree.h
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
 
#ifndef TREE_H
#define TREE_H

#include <iostream>
using namespace std;

#include "TreeNode.h"

template <typename T>
class Tree
{
public:
	Tree();
	void insertNewNode(T); //inserts new node in the tree
	void preOrderPrint(); //prints out tree in the order in which it was entered
	void inOrderPrint(); //prints out tree in accending order
	void postOrderPrint(); //prints out the tree after the order
	TreeNode<T>* search(T); //search for node thats data equals the search key and returns the pointer to that node

private:
	TreeNode<T> *rootPtr;
	bool isEmpty();

	//utility functions to make the insert, print, and search functions more understandable
	void insertNewNodeUtility(TreeNode<T>**,T);
	void preOrderPrintUtility(TreeNode<T>*);
	void inOrderPrintUtility(TreeNode<T>*);
	void postOrderPrintUtility(TreeNode<T>*);
	TreeNode<T>* searchUtility(TreeNode<T>*,T);
};

template <typename T>
Tree<T>::Tree()
{
	rootPtr = 0;
}

template <typename T>
void Tree<T>::insertNewNode(T dataIn)
{
	insertNewNodeUtility(&rootPtr, dataIn); //calls insert new node function passing refernce of the root node and the data to be inserted in the new node
}

template <typename T>
void Tree<T>::insertNewNodeUtility(TreeNode<T>** temp, T dataIn)
{
	if(*temp == 0) //if node is null create a new node with input data
		*temp = new TreeNode<T>(dataIn);
	else
	{
		if(dataIn < (*temp)->data) //if input data is less than data in current node
			insertNewNodeUtility(&((*temp)->leftPtr),dataIn); //recursive function call with current node's left child as input leaf
		else 
		{
			if(dataIn > (*temp)->data) //if input data is greater than data in current node
				insertNewNodeUtility(&((*temp)->rightPtr),dataIn); //recursive function call with current node's right child as input leaf
			else //if input data is equal to data in current node
				cout << dataIn << " is a duplicate value " << endl; //duplicate values ignored
		}
	}
}

template <typename T>
void Tree<T>::preOrderPrint()
{
	preOrderPrintUtility(rootPtr); 
}

template <typename T>
void Tree<T>::preOrderPrintUtility(TreeNode<T>* temp)
{
	if(temp != 0)
	{
		cout << temp->data << ' '; //process node
		preOrderPrintUtility(temp->leftPtr); //recursive traversal of left subtree
		preOrderPrintUtility(temp->rightPtr); //recursive traversal of right subtree
	}
}


template <typename T>
void Tree<T>::inOrderPrint()
{
	inOrderPrintUtility(rootPtr);
}

template <typename T>
void Tree<T>::inOrderPrintUtility(TreeNode<T>* temp)
{
	if(temp != 0)
	{
		inOrderPrintUtility(temp->leftPtr); //recursive traversal of left subtree
		cout << temp->data << ' '; //process node
		inOrderPrintUtility(temp->rightPtr); //recursive traversal of right subtree
	}
}


template <typename T>
void Tree<T>::postOrderPrint()
{
	postOrderPrintUtility(rootPtr);
}

template <typename T>
void Tree<T>::postOrderPrintUtility(TreeNode<T>* temp)
{
	if(temp != 0)
	{
		postOrderPrintUtility(temp->leftPtr); //recursive traversal of left subtree
		postOrderPrintUtility(temp->rightPtr); //recursive traversal of right subtree
		cout << temp->data << ' '; //process node
	}
}

template <typename T>
TreeNode<T>* Tree<T>::search(T key)
{
	return searchUtility(rootPtr, key);
}

template <typename T>
TreeNode<T>* Tree<T>::searchUtility(TreeNode<T>* leaf, T key)
{
	if(leaf != NULL)
	{
		if(key == leaf->data)
			return leaf;
		if(key < leaf->data)
			return searchUtility(leaf->leftPtr, key);
		else
			return searchUtility(leaf->rightPtr, key);
	}
	else
		return NULL;
}
#endif
jason9 (6)
main.cpp
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
 
#include <iostream>
#include <ctime>

#include "List.h"
#include "ListNode.h"
#include "Tree.h"
#include "TreeNode.h"

using namespace std;

int main()
{
	int choice = 0;

	//create function array of 10 random numbers between 0 and 100
	const int size = 10;
	int arr[size];
	srand(time(0)); //time is used as the random seed
	for(int i = 0; i <= size-1;  i++)
	{
		arr[i] = rand() % 101; //assigns random number in array
	}

	List<int> intList; //creates order linked list
	for(int i = 0; i <= size-1;  i++)
	{
		intList.insertNewNode(arr[i]); //inserts value from array to the linked list in the proper positions
	}

	Tree<int> intTree; //create binary tree
	for(int i = 0; i <= size-1;  i++)
	{
		intTree.insertNewNode(arr[i]); //inserts value from array to the binry tree in the same order entered
	}

	while (choice != 7)
	{
		//displays initial array of values
		cout << "Initial Array of Values" << endl;
		cout << "-----------------------" << endl;
		for(int i = 0; i <= size-1;  i++)
		{
			cout << arr[i] << ' ';
		}
		cout << endl << endl;

		//menu of options to perform 
		cout << "Linked Lists and Trees" << endl;
		cout << "-----------------------" << endl;
		cout << "1. Print Linked List" << endl;
		cout << "2. Search For Entry In Linked List" << endl;
		cout << "3. Print Pre-Ordered Traverseal of Tree" << endl;
		cout << "4. Print In-Order Traversal of Tree" << endl;
		cout << "5. Print Post-Order Traversal of Tree" << endl;
		cout << "6. Search For Entry In Tree" << endl;
		cout << "7. EXIT" << endl;
		cout << "Enter Choice: ";
		cin >> choice;
		system("cls");

		int key; //search key used for both the search of linked list and binary tree
		
		ListNode<int>* posList; //node pointer used to store a pointer to node returned from the linked list search function

		TreeNode<int>* posTree; //node pointer used to store a pointer to node returned from the binary tree search function

		switch(choice)
		{
		case 1:
			cout << "Output of a Sorted Linked List" << endl;
			cout << "------------------------------" << endl;
			intList.print(); //prints contents of linked list
			system("pause");
			system("cls");
			break;
		case 2:
			cout << "Searching In a Linked List" << endl;
			cout << "--------------------------" << endl;
			//prompt for search key
			cout << "Enter a a search key: ";
			cin >> key;
			posList = intList.search(key); //stores pointer to list node object
			cout << "The value of pointer is " << posList << endl;
			if(posList != NULL) //if not null then the value was found
				cout << "The value stored at this posistion is " << posList->getData() << endl;
			else
				cout << "The pointer to this position is NULL so there can be no value stored" << endl;
			system("pause");
			system("cls");
			break;
		case 3:
			cout << "Pre-Ordered Traverseal of Tree" << endl;
			cout << "------------------------------" << endl;
			intTree.preOrderPrint(); //print pre ordered traversal of binary tree
			cout << endl;
			system("pause");
			system("cls");
			break;
		case 4:
			cout << "In-Ordered Traverseal of Tree" << endl;
			cout << "------------------------------" << endl;
			intTree.inOrderPrint(); //print in ordered traversal of binary tree
			cout << endl;
			system("pause");
			system("cls");
			break;
		case 5:
			cout << "Post-Ordered Traverseal of Tree" << endl;
			cout << "------------------------------" << endl;
			intTree.postOrderPrint(); //print post ordered traversal of binary tree
			cout << endl;
			system("pause");
			system("cls");
			break;
		case 6:
			cout << "Searching In a Tree" << endl;
			cout << "-------------------" << endl;
			//prompt for search key
			cout << "Enter a a search key: ";
			cin >> key;
			posTree = intTree.search(key); //stores pointer to tree node object
			cout << "The value of pointer is " << posTree << endl;
			if(posTree != NULL) //if not null then the value was found
				cout << "The value stored at this posistion is " << posTree->getData() << endl;
			else
				cout << "The pointer to this position is NULL so there can be no value stored" << endl;
			system("pause");
			system("cls");
			break;
		case 7:
			cout << "Thanks for using my test program for Linked Lists and Trees" << endl;
			system("pause");
			system("cls");

		}
	}
}
Abramus (285)
I don’t want to criticize you, but there is very little reason not to use std::list/std::map/std::set instead of your own implementations of a list and binary search tree. Especially if these implementations are worse.

I would choose doubly linked list for a general list container, as it allows you to insert and remove arbitrary elements in a constant time. Cost of this feature is very low on modern computers, with gigabytes of RAM. Additionally, good list implementations perform insertion and removal of nodes without any conditional statements.

As for the tree, well, it is not a self-balancing tree, what makes it inappropriate for many situations.

As a side note, the only case when I have implemented a list myself in C++ was when I wanted a container that does not possess its elements (i.e. only existing elements can be inserted/removed, without any memory allocation/deallocation operations). This still can be accomplished using std::list, but I thought it is better to reimplement everything.
jason9 (6)
The reason I posted this is that I had an assignment where I had to design a binary search tree and a linked list and couldn't find anything online as to how to design it yourself. Everywhere I looked they used the STL linked list which is not the purpose of the assignment. I wanted to post this so anybody else in my situation has something to refer to and get the basic idea.
Abramus (285)
OK, I understand. But I also think that the readers should be aware of any problems with the code they analyze.
sohguanh (1236)
I believe working world and academic world has some mis-match alignment. Developing BST and such are common assignments in Uni computer science course (I did that in my Uni studies too!). But ask those in the working world developers, out of every 100, how many of them need to do that ? My estimate is 95 of them will be busy using available libraries e.g STL to build business specific apps. The remaining 5 will do the ACTUAL BST etc implementation and most likely in R&D sector :)
firedraco (6243)
But ask those in the working world developers, out of every 100, how many of them need to do that ? My estimate is 95 of them will be busy using available libraries e.g STL to build business specific apps.


No kidding...I had that assignment, and basically it consisted of copying the code from the book. >_>
sohguanh (1236)
This is strange. C++ STL was created to alleviate the need for hand-written code for commonly needed algorithm and data structures. The fact you need to copy the code from the book indicates somehow your employer prefer to re-invent rather than re-use which goes against business nature as most business-es want solution want fast and quick to earn monies FIRST before their competitors.

May I know your employer is in which industry ?
firedraco (6243)
It wasn't an employer, it was a college class. Was still dumb though, I didn't learn anything really.
sohguanh (1236)
This confirm my earlier posting. Working and academic worlds are different, at least in terms of software implementation. Academic world is to teach whereas working world is to deliver the fastest output using available preferably free tools and libraries for you to achieve your objectives.

In R&D, the objectives are slightly different. Some monies are meant to be "burnt" to search for the holy grail solution to some common workplace business problems. In this arena, you really get to implement your linked list, BST etc etc.

But if you take a look at numbers, how many ppl are employed in R&D sector and how many ppl are employed in business sector :P
Topic archived. No new replies allowed.