Volunteer to test code - Linked List ADT

closed account (zwA4jE8b)
Hey guys,
I have made a Linked List ADT for both ordered and unordered lists. I would appreciate if someone can try it out and test for errors. The three code segments below are the header files LinkedList.h OrderedLinkedList.h UnorderedLinkedList.h

the lists can be created using either "OrderedLinkedList<dType> listname;" or "UnorderedLinkedList<dType> listname;" where dType is a datatype that will be used for the id field. The id field is the unique identifier for the list.

The fourth code segment is just a quick sample program I wrote to test the classes. It is pretty unorganized but it demonstrates how to use the classes.

If you find this useful feel free to use it and customize it. But give credit where due.

And I know it is not as feature rich as it could be, as it is still a work in progress.

Thanks you for your time...
-Mike-
closed account (zwA4jE8b)
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
 
//Michael Ervin - Linked list Class
//
//insertfirst & insertlast perform the same operation
//in an ordered linked list.

#ifndef H_LinkedList
#define H_LinkedList

#include <iostream>

//place all needed fields in here and modify code accordingly
//id is used as unique identifier throughout - do not change
template <class dType>
struct nodeType
{
	dType id;
	nodeType<dType> *link;
};

template <class dType>
class LinkedList
{
public:
	LinkedList();
	bool isEmpty() const;
	int length() const;
	void print() const;
	void printnode(nodeType<dType> *print, int pos) const;
	virtual void insertfirst(nodeType<dType> *newnode) = 0;
	virtual void insertlast(nodeType<dType> *newnode) = 0;
	virtual void deleteNode(dType todel) = 0;
	virtual void seqsearch(dType id) const = 0;
	void destroyList();
	~LinkedList();
	void copyList(const LinkedList<dType>& otherlist);
protected:
	nodeType<dType> *head;
	nodeType<dType> *tail;
	int count;
};

//Change ID field to match min and max dType
template <class dType>
LinkedList<dType>::LinkedList()
{
	head = new nodeType<dType>;
	tail = new nodeType<dType>;

	tail->id = 9999.0;
	tail->link = NULL;

	head->id = -1.0;
	head->link = tail;

	count = 0;
}

template <class dType>
bool LinkedList<dType>::isEmpty() const
{
	return (head->link == tail);
}

template <class dType>
int LinkedList<dType>::length() const
{
	return count;
}


//If fields have been added to nodeType, they must also be added here
template <class dType>
void LinkedList<dType>::print() const
{
	nodeType<dType> *current;
	current = head->link;
	if (!isEmpty())
	{
		while (current != tail)
		{
			cout << current->id << " " << endl;
			current = current->link;
		}
	}
	else
		cout << "The list is empty...";
	cout << endl;
}


//If fields have been added to nodeType, they must also be added here
template <class dType>
void LinkedList<dType>::printnode(nodeType<dType> *print, int pos) const
{
	cout << "Found node at position " << pos << endl;
	cout << "ID = " << print->id << endl;
	cout << endl;
}

template <class dType>
void LinkedList<dType>::destroyList()
{
	nodeType<dType> *temp;
	while (head->link != tail)
	{
		temp = head->link;
		head->link = temp->link;
		delete temp;
	}
	count = 0;
}

template <class dType>
LinkedList<dType>::~LinkedList()
{
	destroyList();
}

//If fields have been added to nodeType, they must also be added here in order to copy correctly.
template <class dType>
void LinkedList<dType>::copyList(const LinkedList<dType>& otherlist)
{
	nodeType<dType> *current, *newnode;

	current = otherlist.head->link;

	while (current != otherlist.tail)
	{
		newnode = new nodeType<dType>;
		newnode->id = current->id;
		newnode->link = NULL;
		insertlast(newnode);
		current = current->link;
	}
}
#endif 


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
 
//Michael Ervin - Ordered Linked list Class

#ifndef H_OrderedLinkedList
#define H_OrderedLinkedList

#include <iostream>
#include "LinkedList.h"

template <class dType>
class OrderedLinkedList:public LinkedList<dType>
{
public:
	void insert(nodeType<dType> *newnode);
	void insertfirst(nodeType<dType> *newnode);
	void insertlast(nodeType<dType> *newnode);
	void deleteNode(dType todel);
	void seqsearch(dType id) const;
};

template <class dType>
void OrderedLinkedList<dType>::insertfirst(nodeType<dType> *newnode)
{
	insert(newnode);
}

template <class dType>
void OrderedLinkedList<dType>::insertlast(nodeType<dType> *newnode)
{
	insert(newnode);
}

template <class dType>
void OrderedLinkedList<dType>::insert(nodeType<dType> *newnode)
{
	nodeType<dType> *current, *trail;
		trail = head;
		current = head->link;
		while (current != tail && current->id < newnode->id)
		{
			trail = current;
			current = current->link;
		}
		newnode->link = current;
		trail->link = newnode;
		count++;
}

template <class dType>
void OrderedLinkedList<dType>::deleteNode(dType todel)
{
	nodeType<dType> *current, *trail;
	bool stop = false;

	if(!isEmpty())
	{
		trail = head;
		current = head->link;
		while (current != tail && !stop)
		{
			if (current->id == todel)
				stop = true;
			else
			{
				trail = current;
				current = current->link;
			}
		}
		if (!stop)
			cout << "The node to delete is not in the list!" << endl;
		else
		{
			trail->link = current->link;
			delete current;
			count--;
		}
	}
	else
	{
		cout << "The list is empty!" << endl;
	}
}

template <class dType>
void OrderedLinkedList<dType>::seqsearch(dType id) const
{
	nodeType<dType> *current;
	bool found = false;
	int pos = 1;

	current = head->link;
	while (current != tail && !found)
	{
		if (current->id == id)
			found = true;
		else
		{
			current = current->link;
			pos++;
		}
	}
	if (found)
		printnode(current, pos);
	else
		cout << "Node not in list..." << endl;
}
#endif 


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
 
//Michael Ervin - Unordered Linked list Class

#ifndef H_UnorderedLinkedList
#define H_UnorderedLinkedList

#include <iostream>
#include "LinkedList.h"

template <class dType>
class UnorderedLinkedList:public LinkedList<dType>
{
public:
	void insertfirst(nodeType<dType> *newnode);
	void insertlast(nodeType<dType> *newnode);
	void deleteNode(dType todel);
	void seqsearch(dType id) const;
};

template <class dType>
void UnorderedLinkedList<dType>::insertlast(nodeType<dType> *newnode)
{
	nodeType<dType> *current;
	current = head;
	while (current->link != tail)
		current = current->link;
	newnode->link = tail;
	current->link = newnode;
}

template <class dType>
void UnorderedLinkedList<dType>::insertfirst(nodeType<dType> *newnode)
{
	newnode->link = head->link;
	head->link = newnode;
}

template <class dType>
void UnorderedLinkedList<dType>::deleteNode(dType todel)
{
	nodeType<dType> *current, *trail;
	bool stop = false;

	if(!isEmpty())
	{
		trail = head;
		current = head->link;
		while (current != tail && !stop)
		{
			if (current->id == todel)
				stop = true;
			else
			{
				trail = current;
				current = current->link;
			}
		}
		if (!stop)
			cout << "The node to delete is not in the list!" << endl;
		else
		{
			trail->link = current->link;
			delete current;
			count--;
		}
	}
	else
	{
		cout << "The list is empty!" << endl;
	}
}

template <class dType>
void UnorderedLinkedList<dType>::seqsearch(dType id) const
{
	nodeType<dType> *current;
	bool found = false;
	int pos = 1;

	current = head->link;
	while (current != tail && !found)
	{
		if (current->id == id)
			found = true;
		else
		{
			current = current->link;
			pos++;
		}
	}
	if (found)
		printnode(current, pos);
	else
		cout << "Node not in list..." << endl;
}
#endif
closed account (zwA4jE8b)
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
 
//This is some sample code utilizing the LinkedList Class of LinkedList.h

#include <iostream>
#include "OrderedLinkedList.h"
#include "UnorderedLinkedList.h"

using namespace std;

int main()
{
	OrderedLinkedList<int> l1;				//Create List
	nodeType<int> *trial, *add2;			//Create Nodes to add to list

	cout << "l1 initialized (int)..." << endl;
	l1.print();

	cout << "Hardcode entry of new node into l1 - id 10..." << endl;
	trial = new nodeType<int>;
	trial->id = 10;
	trial->link = NULL;
	l1.insertlast(trial);
	l1.print();
	cout << endl;

	cout << "Inserting nodes into l1 using for loop..." << endl;
	for (int i = 66; i <=90; i++)
	{
		add2 = new nodeType<int>;
		add2->id = i;
		add2->link = NULL;
		l1.insertfirst(add2);
	}
	l1.print();

	cout << endl << "The length of l1 is: " << l1.length() << endl;

	cout << "Searching for id 122...";
	l1.seqsearch(122);
	cout << endl;

	cout << "Deleting node with id 122 from l1..." << endl;
	l1.deleteNode(122);
	l1.print();
	cout << endl;

	cout << "Now creating and printing l2 (int)..." << endl;
	OrderedLinkedList<int> l2;
	l2.copyList(l1);
	l2.print();

	cout << endl << "The length of l2 is: " << l2.length() << endl;

	cout << "Hardcode entry of new node into l2 - id 221..." << endl;
	trial = new nodeType<int>;
	trial->id = 221;
	trial->link = NULL;
	l2.insertlast(trial);
	l2.print();
	cout << endl;

	cout << "Deleting node with id 124 from l2..." << endl;
	l2.deleteNode(124);
	l2.print();
	cout << endl;

	cout << "Printing l1 and l2 respectively..." << endl;
	l1.print();
	l2.print();
	cout << endl;

	cout << "Destroying list 1, printing list 1..." << endl;
	l1.destroyList();
	l1.print();

	cout << "Destroying list 2, printing list 2..." << endl;
	l2.destroyList();
	l2.print();
	cout << endl;

	cout << endl << endl;

	cout << "Creating l3 as double type..." << endl;
	OrderedLinkedList<double> l3;
	nodeType<double> *add1;

	for (int i = 0; i <=100; i++)
	{
		add1 = new nodeType<double>;
		add1->id = (i + (i * 0.521));
		add1->link = NULL;
		l3.insertlast(add1);
	}
	l3.print();

	cout << "Hardcode add of node with id 132.111..." << endl;
	add1 = new nodeType<double>;
	add1->id = (132.111);
	add1->link = NULL;
	l3.insertfirst(add1);
	l3.print();
	cout << endl;

	cout << "Searching l3 for 34.3 and 15.21 respectiveley..." << endl;
	l3.seqsearch(34.3);
	l3.seqsearch(15.21);

	UnorderedLinkedList<int> l4;
	nodeType<int> *unord1;
	unord1 = new nodeType<int>;
	unord1->id = 15;
	unord1->link = NULL;
	l4.insertfirst(unord1);
	l4.print();

	for (int i = 0; i <= 15; i++)
	{
		unord1 = new nodeType<int>;
		unord1->id = i;
		unord1->link = NULL;
		l4.insertlast(unord1);
	}
	l4.print();

	unord1 = new nodeType<int>;
	unord1->id = 3;
	unord1->link = NULL;
	l4.insertlast(unord1);
	l4.print();

	cout << "Press ENTER to exit...";
	cin.get();
	return 0;
}
closed account (zwA4jE8b)
files should be named

LinkedList.h
OrderedLinkedList.h
UnorderedLinkedList.h

respectively, copy and paste
Topic archived. No new replies allowed.