Linked Lists – Part III

I spent some time enhancing and testing the SingleLinkList class. I will stop at this point. On the next post related linked lists will design and implement the DoubleLinkList class using the same methods that have been implemented on the SingleLinkList class. Of course, while testing one class or the other some new method may be added or an existing method may be modified. This is typical in software development.

Following is a screen capture of a console generated by Visual Studio 2013 when running the test code for the SingleLinkList class:

main <<< enqueue widget:  this: 0xe4896fead8 id: 3 name ==>widget_3<==

main <<< head:  this: 0xe4896fef60 id: 1 name ==>widget_1<==
main <<< tail:  this: 0xe4896fefc0 id: 3 name ==>widget_3<==

main <<< j: 0 p:  this: 0x2c5c0d81160 next: 0x2c5c0d81220 prev: 0x0
main <<< insertAfter widget:  this: 0xe4896ff0c8 id: 4 name ==>widget_4<==
main <<< j: 3 p:  this: 0x2c5c0d81720 next: 0x2c5c0d80690 prev: 0x0
main <<< insertAfter widget:  this: 0xe4896ff0c8 id: 5 name ==>widget_5<==
main <<< j: 0 p:  this: 0x2c5c0d81160 next: 0x2c5c0d81a60 prev: 0x0
main <<< insertAfter widget:  this: 0xe4896ff0c8 id: 6 name ==>widget_6<==
main <<< j: 3 p:  this: 0x2c5c0d81220 next: 0x2c5c0d81720 prev: 0x0
main <<< insertAfter widget:  this: 0xe4896ff0c8 id: 7 name ==>widget_7<==
main <<< j: 0 p:  this: 0x2c5c0d81160 next: 0x2c5c0d81d60 prev: 0x0
main <<< insertAfter widget:  this: 0xe4896ff0c8 id: 8 name ==>widget_8<==
main <<< j: 1 p:  this: 0x2c5c0d81fe0 next: 0x2c5c0d81d60 prev: 0x0
main <<< insertAfter widget:  this: 0xe4896ff0c8 id: 9 name ==>widget_9<==
main <<< j: 6 p:  this: 0x2c5c0d81ea0 next: 0x2c5c0d81720 prev: 0x0
main <<< insertAfter widget:  this: 0xe4896ff0c8 id: 10 name ==>widget_10<==
main <<< slq->isFull i: 7
main <<< slq->isFull i: 8
main <<< slq->isFull i: 9

main <<< pop widget:  this: 0xe4896fead8 id: 5 name ==>widget_5<==
main <<< pop widget:  this: 0xe4896fead8 id: 3 name ==>widget_3<==
main <<< pop widget:  this: 0xe4896fead8 id: 10 name ==>widget_10<==
main <<< pop widget:  this: 0xe4896fead8 id: 7 name ==>widget_7<==
main <<< pop widget:  this: 0xe4896fead8 id: 2 name ==>widget_2<==
main <<< pop widget:  this: 0xe4896fead8 id: 4 name ==>widget_4<==
main <<< pop widget:  this: 0xe4896fead8 id: 6 name ==>widget_6<==
main <<< pop widget:  this: 0xe4896fead8 id: 9 name ==>widget_9<==
main <<< pop widget:  this: 0xe4896fead8 id: 8 name ==>widget_8<==
main <<< pop widget:  this: 0xe4896fead8 id: 1 name ==>widget_1<==

main <<< enqueue widget:  this: 0xe4896fead8 id: 1 name ==>widget_1<==
main <<< j: 0 p:  this: 0x2c5c0d810e0 next: 0x2c5c0d80690 prev: 0x0
main <<< insertBefore widget:  this: 0xe4896ff318 id: 2 name ==>widget_2<==
main <<< j: 1 p:  this: 0x2c5c0d810e0 next: 0x2c5c0d80690 prev: 0x0
main <<< insertBefore widget:  this: 0xe4896ff318 id: 3 name ==>widget_3<==
main <<< j: 0 p:  this: 0x2c5c0d81620 next: 0x2c5c0d817e0 prev: 0x0
main <<< insertBefore widget:  this: 0xe4896ff318 id: 4 name ==>widget_4<==
main <<< j: 0 p:  this: 0x2c5c0d81ae0 next: 0x2c5c0d81620 prev: 0x0
main <<< insertBefore widget:  this: 0xe4896ff318 id: 5 name ==>widget_5<==
main <<< j: 0 p:  this: 0x2c5c0d81c20 next: 0x2c5c0d81ae0 prev: 0x0
main <<< insertBefore widget:  this: 0xe4896ff318 id: 6 name ==>widget_6<==
main <<< j: 2 p:  this: 0x2c5c0d81ae0 next: 0x2c5c0d81620 prev: 0x0
main <<< insertBefore widget:  this: 0xe4896ff318 id: 7 name ==>widget_7<==

main <<< push widget:  this: 0xe4896fead8 id: 1 name ==>widget_1<==
main <<< push widget:  this: 0xe4896fead8 id: 2 name ==>widget_2<==
main <<< push widget:  this: 0xe4896fead8 id: 3 name ==>widget_3<==
main <<< push widget:  this: 0xe4896fead8 id: 4 name ==>widget_4<==
main <<< push widget:  this: 0xe4896fead8 id: 5 name ==>widget_5<==
main <<< push widget:  this: 0xe4896fead8 id: 6 name ==>widget_6<==
main <<< push widget:  this: 0xe4896fead8 id: 7 name ==>widget_7<==
main <<< push widget:  this: 0xe4896fead8 id: 8 name ==>widget_8<==
main <<<  pop widget:  this: 0xe4896ff4e0 id: 8 name ==>widget_8<==
main <<<  pop widget:  this: 0xe4896ff4e0 id: 7 name ==>widget_7<==
main <<<  pop widget:  this: 0xe4896ff4e0 id: 6 name ==>widget_6<==
main <<<  pop widget:  this: 0xe4896ff4e0 id: 5 name ==>widget_5<==
main <<<  pop widget:  this: 0xe4896ff4e0 id: 4 name ==>widget_4<==
main <<<  pop widget:  this: 0xe4896ff4e0 id: 3 name ==>widget_3<==
main <<<  pop widget:  this: 0xe4896ff4e0 id: 2 name ==>widget_2<==
main <<<  pop widget:  this: 0xe4896ff4e0 id: 1 name ==>widget_1<==

Following is the test code written in C++:

// **** ****

#include <iostream>
#include <time.h>

// **** ****

using namespace std;

// **** header files (templates contain actual implementations) ****

#include "Widget.h"
#include "Node.h"
#include "SingleLinkList.h"
#include "Solution.h"

// **** constructor ****

Solution::Solution()
{}

// **** destructor ****

Solution::~Solution()
{}

/*
* TEST code.
*/
int main()
{

	// **** constant(s) ****

	const int MAX_ELEMENTS	= 10;

	char buffer[BUFSIZ];

	// ***** activity message ****

	cout << "main <<< testing widgets ..." << endl;

	// **** create a new Widget ****

	Widget widget = Widget();

	// **** populate widget ****

	try {
		widget.setId(1234);
	} catch (int ex) {
		if (ex == widget.WidgetInvalidId) {
			cerr << "main <<< EXCEPTION widget.setId() - WidgetInvalidId" << endl;
			exit(ex);
		}
	}
	
	try {
		widget.setName("widget_1234");
	} catch (int ex) {
		if (ex == widget.WidgetInvalidName) {
			cerr << "main <<< EXCEPTION widget.setName() - WidgetInvalidName" << endl;
			exit(ex);
		}
	}

	// **** display the widget ****

	cout << "main <<< widget: " << widget.toString() << endl;

	// ***** activity message ****

	cout << endl;
	cout << "main <<< testing nodes ..." << endl;

	// **** instantiate a node ****

	Node<Widget> node = Node<Widget>(widget);

	// **** display the node ****

	cout << "main <<< node: " << node.toString() << endl;

	// **** display the widget ****

	cout << "main <<< widget: " << node.data.toString() << endl;

	// **** build a crude list of nodes ****

	Node<int> *list = nullptr;
	for (int i = 1; i <= 5; i++) {

		// **** allocate a node ****

		Node<int> *n = new Node<int>(i);

		// **** insert node at tail of list ****

		if (list == nullptr) {
			list = n;
		} else {
			Node<int> *p = list;
			for ( ; p->next != nullptr; p = p->next) {}
			p->next = n;
		}
	}

	// **** traverse the crude list of nodes ****

	for (Node<int> *p = list; p != nullptr; p = p->next) {
		cout << "main <<< p data: " << p->data << " next: " << p->next << endl;
	}

	// **** delete all elements from the crude list of nodes ****

	for (Node<int> *p = list; p != nullptr; ) {
		Node<int> *n = p;
		p = p->next;
		cout << "main <<< deleting: " << n->data << endl;
		delete(n);
	}

	// ***** activity message ****

	cout << endl;
	cout << "main <<< testing single link list ..." << endl;

	// **** allocate single link queue ****

	SingleLinkList<Widget> *slq = new SingleLinkList<Widget>(MAX_ELEMENTS);
	cout << "main <<< slq: " << slq->toString() << endl;

	// **** loop inserting elements into the queue ****

	for (int i = 1; i <= 5; i++) {

		// **** allocate a widget ****

		int status			= _itoa_s(i, buffer, sizeof(buffer), 10);
		string widgetName	= "widget_" + string(buffer);
		Widget widget		= Widget(i, widgetName);
		cout << "main <<< enqueue widget: " << widget.toString() << endl; // ***** enqueue widget **** slq->enqueue(widget);
	}
	cout << "main <<< slq: " << slq->toString() << endl;
	cout << endl; // **** loop removing elements from the queue **** while (!slq->isEmpty()) {
		cout << "main <<< dequeue widget: " << slq->dequeue().toString() << endl;
	} 
	cout << endl;

	// **** insert some widgets into the queue ****

	for (int i = 1; i <= 3; i++) {
	
		// **** create a widget ****

		int status			= _itoa_s(i, buffer, sizeof(buffer), 10);
		string widgetName	= "widget_" + string(buffer);
		widget				= Widget(i, widgetName);
		cout << "main <<< enqueue widget: " << widget.toString() << endl; // **** enqueue the widget into the queue **** slq->enqueue(widget);
	}
	cout << endl;

	// **** peek at the head of queue ****

	cout << "main <<< head: " << slq->peekHead().toString() << endl;

	// **** peek at the tail of the queue ****

	cout << "main <<< tail: " << slq->peekTail().toString() << endl << endl;

	// **** initialize the pseudo random number generator ****

	srand((unsigned int)time(nullptr));

	// **** insert after ****

	int j	= 0;
	for (int i = 0; i < 10; i++) { // **** check if queue is full **** if (slq->isFull()) {
			cout << "main <<< slq->isFull i: " << i << endl;
			continue;
		}

		// **** location to insert after in queue ****
	
		Node<Widget> *p;
		switch (i) {
			case 0:						// head of queue
				j = 0;
				p = slq->getHead();
			break;

			case 1:						// tail of queue
				j = slq->getCount() - 1;
				p = slq->getTail();
			break;

			default:					// random location in queue

				// **** generate random location in queue ****

				j = rand() % slq->getCount();

				// **** pointer to specified element in the queue ****

				p = slq->elementAt(j);
			break;
		}
		cout << "main <<< j: " << j << " p: " << p->toString() << endl; // **** create a widget **** int widgetId = slq->getCount() + 1;
		int status			= _itoa_s(widgetId, buffer, sizeof(buffer), 10);
		string widgetName	= "widget_" + string(buffer);
		Widget widget		= Widget(widgetId, widgetName);
		cout << "main <<< insertAfter widget: " << widget.toString() << endl; // **** insert widget into the queue AFTER the specified element **** try { slq->insertAfter(p, widget);
		} catch (int ex) {
			cerr << "main <<< EXCEPTION slq->insertAfter ex: " << ex << endl; 
			exit(ex);
		}
	}
	cout << endl; // **** POP from the tail of the queue (all widgets) **** while (!slq->isEmpty()) {

		// **** pop next element from the queue ****

		widget = slq->pop();
		cout << "main <<< pop widget: " << widget.toString() << endl;
	}
	cout << endl; // **** create a widget **** widget = Widget(1, "widget_1"); // **** enqueue widget **** slq->enqueue(widget);
	cout << "main <<< enqueue widget: " << widget.toString() << endl;

	// **** insert BEFORE ****

	for (int i = 2; (i <= 7) && !slq->isEmpty(); i++)
	{

		// **** check if queue is full ****

		if (slq->isFull())
		{
			cout << "main <<< slq->isFull" << endl;
			continue;
		}

		// **** location to insert before in queue ****

		Node<Widget> *p;

		// **** generate random location in queue ****

		j = rand() % slq->getCount();

		// **** point to an element in the queue ****

		try {
			p = slq->elementAt(j);
		} catch (int ex) {
			cout << "main <<< EXCEPTION slq->elementAt j: " << j << " ex: " << ex << endl;
			exit(ex);
		}
		cout << "main <<< j: " << j << " p: " << p->toString() << endl; // **** create a widget **** int widgetId = slq->getCount() + 1;
		int status			= _itoa_s(widgetId, buffer, sizeof(buffer), 10);
		string widgetName	= "widget_" + string(buffer);
		Widget widget		= Widget(widgetId, widgetName);
		cout << "main <<< insertBefore widget: " << widget.toString() << endl; // **** insert widget into the queue BEFORE the specified element **** try { slq->insertBefore(p, widget);
		}
		catch (int ex)
		{
			cerr << "main <<< EXCEPTION slq->insertBefore ex: " << ex << endl;
			exit(ex);
		}
	}
	cout << endl; // **** clear the queue **** while (!slq->isEmpty()) {
		slq->dequeue();
	}

	// **** push elements on the stack (queue) ****

	for (int i = 0; i <= 7; i++) { // **** check if the stack is full **** if (slq->isFull()) {
			cout << "main <<< slq->isFull i: " << i << endl; continue; } // **** create a widget **** int widgetId = slq->getCount() + 1;
		int status			= _itoa_s(widgetId, buffer, sizeof(buffer), 10);
		string widgetName	= "widget_" + string(buffer);
		widget				= Widget(widgetId, widgetName);
		cout << "main <<< push widget: " << widget.toString() << endl; // **** push the widget on to the stack (queue) **** slq->push(widget);
	}

	// **** pop elements from the stack (queue) ****

	while (!slq->isEmpty()) {
		cout << "main <<<  pop widget: " << slq->pop().toString() << endl;
	}

	// **** all done ****

	return 0;
}

The SingleLinkList class uses a template; which allow us to use the queue with different types of objects. I tested it with integers and Widgets. The Widget class was solely created to test the operations of the queue. The Widgets class may have additional fields by the time the entire queue implementation is done.

The first set of items in the test code checks the operations of creating, populating and displaying Widgets.

The second set of operations in the test code checks creating, populating, displaying and creating a crude linked list with elements from the Node class. A list is created, nodes are inserted and deleted.

The third part of the test starts by checking out the enqueue method. The isEmpty method was created to eliminate the need to count the number of elements remaining in the queue. Before implementing the method I started by looping the same number of times as elements were inserted. The second pas used the getCount getter to determine if we should remove additional nodes. The current test implementation makes use of the isEmpty method. This is also typical of Agile and TDD approaches. You only implement what is needed and always generate test cases that do not compile before the actual code in the associated classes.

After testing the dequeue method a few widgets are inserted into the queue and we test the methods to get what is at the head and the tail of the queue.

We then test the insertAfter and insertBefore methods. These are used to insert elements at random positions in the queue. I believe we will be using them in a future implementation of a LFU Cache.

We then loop invoking the pop method. A queue can be used to implement FILO (queue) or FIFO (stack) objects. It is simpler and cleaner when using a double linked Node, but as you can verify, such operations also work with single linked lists.

Finally a few widgets are pushed and popped from a stack (implemented with the same queue).

The C++ code for the Widget class follows:

#include <string>

#include "Widget.h"

/*
	Constructor.
*/
Widget::Widget()
{
id		= 0;
name	= "";
}

/*
*/
Widget::Widget(int newId, std::string newName) {
	id		= newId;
	name	= newName;
}

/*
	Destructor.
*/
Widget::~Widget()
{}

// **** getters ****

int Widget::getId() {
	return id;
}

std::string Widget::getName() {
	return name;
}

// **** setters ****

void Widget::setId(int newId) {
	if (newId <= 0) { throw WidgetInvalidId; } id = newId; } void Widget::setName(std::string newName) { if (newName == "") { throw WidgetInvalidName; } name = newName; } /* Return a string representation of the Widget object */ std::string Widget::toString() { std::string str = ""; char buffer[BUFSIZ]; errno_t status; status = _i64toa_s((long long)this, buffer, sizeof(buffer), 16); str += " this: 0x" + std::string(buffer); status = _itoa_s(id, buffer, sizeof(buffer), 10); str += " id: " + std::string(buffer); str += " name ==>" + name + "<==";
	return str;
}

// **** overload = operator ****

void Widget::operator=(const Widget&obj) {
	(*this).id		= obj.id;
	(*this).name	= obj.name;
}

The C++ code for the Node class follows:

#pragma once

// **** ****

#include <string>
#include <sstream>


// **** vvvv class definition vvvv

template <typename T>
class Node
{

	// **** constants ****

public:
	const int NodeInvalidData = -1;

	// **** members ****

public: 
	T		data;
	Node<T>	*next;
	Node<T>	*prev;

	// **** constructor ****

public:
	Node();

	// **** constructor ****

public:
	Node(T myData);

	// **** destructor ****

public:
	~Node();

	// **** setters ***

public:
	void setData(T myData);

	// **** getters ****

public:
	T getData();

	// **** return a string with the contents of the node ****

public:
	std::string toString();

	// **** override the << operator ****

public:
	friend std::ostream& operator <<(std::ostream &outputStream, const Node<T> &node);
};

// **** vvvv class implementation vvvv

/*
	Constructor.
*/
template <typename T>
Node<T>::Node()
{
	next = (Node<T> *)nullptr;
	prev = (Node<T> *)nullptr;
}

// **** constructor ****

template <typename T>
Node<T>::Node(T myData)
{
	data = myData;
	next = (Node<T> *)nullptr;
	prev = (Node<T> *)nullptr;
}

// **** destructor ****

template <typename T>
Node<T>::~Node()
{}

// **** setters ****

template <typename T>
void Node<T>::setData(T myData)
{
	data = myData;
}

// **** getters ****

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

// **** override << operator ****

template <typename T>
std::ostream& operator <<(std::ostream& outputStream, const Node<T>& node) {
	string str = (T)(node.data).toString();
	outputStream << "data=" << str;
	return outputStream;
}

/*
	Generate a string with the contents of the node.
*/
template <typename T>
std::string Node<T>::toString()
{
	std::string str = "";
	char buffer[BUFSIZ];
	errno_t status;

	status = _i64toa_s((long long)this, buffer, sizeof(buffer), 16);
	str += " this: 0x" + std::string(buffer);

	status = _i64toa_s((long long)next, buffer, sizeof(buffer), 16);
	str += " next: 0x" + std::string(buffer);

	status = _i64toa_s((long long)prev, buffer, sizeof(buffer), 16);
	str += " prev: 0x" + std::string(buffer);

	return str;
}

// **** override the << operator ****

Note that I was about to override the “<<” operator but decided to leave it for when needed.

The C++ class for the SingleLinkList class follows:

#pragma once

// **** ****

#include <string>

// **** ****

#include "Node.h"


// **** vvvv class definition vvvv

template <typename T>
class SingleLinkList
{

// **** constants ****

public:
	const int QueueIsFull			= -1;
	const int QueueIsEmpty			= -2;
	const int QueueInvalidLocation	= -3;
	const int QueueNullPointer		= -4;
	const int QueueInvalidPointer	= -5;
	const int QueueInvalidMaxCount	= -6;

// **** members ****

private:
	int		count;
	int		maxCount;
	Node<T>	*head;
	Node<T>	*tail;

// **** constructor ****

public:
	SingleLinkList();

// **** constructor ****

public:
	SingleLinkList(int maxElements);

// **** destructor ****

public:
	~SingleLinkList();

// **** getters ****

public:
	int SingleLinkList<T>::getCount();

public:
	Node<T> *SingleLinkList<T>::getHead();

public:
	Node<T> *SingleLinkList<T>::getTail();

// **** setters ****


// **** generate string of queue ****

public:
	std::string SingleLinkList<T>::toString();

// **** enqueue element at tail of queue ****

public:
	void SingleLinkList<T>::enqueue(T myData);

// **** dequeue element at head of queue ****

public:
	T SingleLinkList<T>::dequeue();

// **** check if queue is empty ****

public:
	bool SingleLinkList<T>::isEmpty();

// ***** peek at the head of the queue ****

public:
	T SingleLinkList<T>::peekHead();
	
// **** peek at the tail of the queue ****

public:
	T SingleLinkList<T>::peekTail();

// **** return a pointer to the element in the queue at the specified location ****

public:
	Node<T> *SingleLinkList<T>::elementAt(int loc);

// **** check if pointer is valid in this queue ****

public:
	bool SingleLinkList<T>::isValidPointer(Node<T> *p);

// **** insert AFTER specified element ****

public:
	void SingleLinkList<T>::insertAfter(Node<T> *p, T myData);

// **** check if queue is full ****

public:
	bool SingleLinkList<T>::isFull();

// **** pop element from head of queue (FIFO - stack) ****

public:
	T SingleLinkList<T>::pop();

// **** insert BEFORE specified element ****

public:
	void SingleLinkList<T>::insertBefore(Node<T> *p, T myData);

// **** PUSH an element into a queue (stack) ****

public:
	void SingleLinkList<T>::push(T myData);
};


// **** vvvv class implementation vvvv

/*
	Base constructor.
*/
template <typename T>
SingleLinkList<T>::SingleLinkList()
{
	count		= 0;
	maxCount	= 0;
	head		= (Node<T> *)this;
	tail		= (Node<T> *)this;
}

/*
	Constructor indicating max count of element is the queue.
*/
template <typename T>
SingleLinkList<T>::SingleLinkList(int maxElements) {

	// **** check if the value is invalid ****

	if (maxElements < 0) {
		throw QueueInvalidMaxCount;
	}

	// **** ****

	count		= 0;
	maxCount	= maxElements;
	head		= (Node<T> *)this;
	tail		= (Node<T> *)this;
}

/*
	Base destructor.
*/
template <typename T>
SingleLinkList<T>::~SingleLinkList()
{}

/*
	Build a string representation of the queue.
*/
template <typename T>
std::string SingleLinkList<T>::toString()
{
	std::string str = "";
	char buffer[64];
	int status;

	// **** collect data from the queue ****

	status = _ui64toa_s((long long)this, buffer, sizeof(buffer), 16);
	str += "this: 0x" + std::string(buffer);

	status = _itoa_s(count, buffer, sizeof(buffer), 10);
	str += " count: " + std::string(buffer);

	status = _itoa_s(maxCount, buffer, sizeof(buffer), 10);
	str += " maxCount: " + std::string(buffer);

	status = _ui64toa_s((long long)head, buffer, sizeof(buffer), 16);
	str += " head: 0x" + std::string(buffer);

	status = _ui64toa_s((long long)tail, buffer, sizeof(buffer), 16);
	str += " tail: 0x" + std::string(buffer);

	// **** collect data from the queue elements ****

	for (Node<T> *p = this->head; p != (Node<T> *)this; p = p->next)
	{
		str += "\n";

		status = _ui64toa_s((long long)p, buffer, sizeof(buffer), 16);
		str += "\t\tp: 0x" + std::string(buffer);

		//status = _itoa_s(p->data, buffer, sizeof(buffer), 10);
		//str += " data: " + std::string(buffer);
		str += " data: " + (p->data).toString();

		status = _ui64toa_s((long long)p->next, buffer, sizeof(buffer), 16);
		str += " next: 0x" + std::string(buffer);
	}

	// **** ****

	return str;
}

/*
	Enqueue element at the tail of the queue.
	The queue maintains a FIFO order (enqueue & dequeue).
*/
template <typename T>
void SingleLinkList<T>::enqueue(T myData)
{

	// **** check if queue is full ****

	if ((maxCount != 0) && (count >= maxCount))
	{
		throw QueueIsFull;
	}

	// **** allocate new node ****

	Node<T> *node = new Node<T>(myData);

	// **** insert node in empty queue ****

	if (SingleLinkList<T>::count == 0)
	{
		SingleLinkList<T>::head = node;
	}

	// **** insert new element at the tail of the queue ****

	else
	{
		SingleLinkList<T>::tail->next = node;
	}

	// **** ****

	node->next = (Node<T> *)this;
	SingleLinkList<T>::tail = node;
	SingleLinkList<T>::count++;
}

/*
	Dequeue element at head of queue.
	The queue maintains a FIFO order (enqueue & dequeue).
*/
template <typename T>
T SingleLinkList<T>::dequeue()
{

	// **** check if the queue is empty ****

	if (count <= 0)
	{
		throw QueueIsEmpty;
	}

	// **** for ease of use ****

	Node<T> *node = head;

	// **** get the data from the head node ****

	T data = node->data;

	// **** update the head ****

	head = head->next;

	// **** free (head) node ****

	delete(node);

	// **** decrement queue count ****

	count--;

	// **** update tail (queue is empty) ****

	if (count == 0)
	{
		tail = (Node<T> *)this;
	}

	// **** return value ****

	return data;
}

/*
	Get the count of elements in the queue.
*/
template <typename T>
int SingleLinkList<T>::getCount()
{
	return count;
}

/*
	Get the HEAD from the queue.
*/
template <typename T>
Node<T> *SingleLinkList<T>::getHead()
{
	return head;
}

/*
	Get the TAIL from the queue.
*/
template <typename T>
Node<T> *SingleLinkList<T>::getTail()
{
	return tail;
}

/*
	Determine if the queue is EMPTY.
	Same but less elegant approach could be achieved with getCount() and a test.
*/
template <typename T>
bool SingleLinkList<T>::isEmpty()
{
	return (count <= 0);
}

/*
	Determine if the queue is FULL.
	Same but less elegant approach could be achieved with getCount() and a test.
*/
template <typename T>
bool SingleLinkList<T>::isFull()
{
	return (count >= maxCount);
}

/*
	Return the element at the HEAD of the queue.
	Returns null if queue is empty.
*/
template <typename T>
T SingleLinkList<T>::peekHead() {
	if (count <= 0) { throw QueueIsEmpty; } else { return this->head->data;
	}
}

/*
	Return the element at the TAIL of the queue.
	Returns null if queue is empty.
*/
template <typename T>
T SingleLinkList<T>::peekTail() {
	if (count <= 0) { throw QueueIsEmpty; } else { return this->tail->data;
	}
}

/*
*/
template <typename T>
Node<T> *SingleLinkList<T>::elementAt(int loc) {

	// **** check if location is out of range ****

	if ((loc < 0) || (loc > count)) {
		throw QueueInvalidLocation;
	}

	// **** traverse the list until specified location is found ****

	Node<T> *p = head;
	for (int i = 0; i < loc; i++) { p = p->next;
	}

	// **** ****

	return p;
}

/*
	Check if the specified pointer a valid pointer in this queue.
*/
template<typename T>
bool SingleLinkList<T>::isValidPointer(Node<T> *p) {
	
	// **** check for null pointer ****

	if (p == nullptr) {
		throw QueueNullPointer;
	}

	// **** traverse the queue looking for the specified pointer ****

	for (Node<T> *q = head; q != (Node<T> *)this; q = q->next) {
		if (q == p) {

			// **** node found ****

			return true;
		}
	}

	// **** node NOT found ****

	return false;
}

/*
	Insert the specified element AFTER the specified one.
*/
template <typename T>
void SingleLinkList<T>::insertAfter(Node<T> *p, T myData) {

	// **** check if queue is full ****

	if ((maxCount != 0) && (count >= maxCount))
	{
		throw QueueIsFull;
	}

	// **** check for null pointer ****

	if (p == nullptr) {
		throw QueueNullPointer;
	}

	// **** check if specified pointer is NOT in the queue ****

	if (!isValidPointer(p)) {
		throw QueueInvalidPointer;
	}

	// **** allocate new node ****

	Node<T> *node = new Node<T>(myData);

	// **** insert new element after the specified one ****

	node->next	= p->next;
	p->next		= node;

	// **** update the queue ****

	if (p == tail) {
		tail = node;
	}
	count++;
}

/*
	Pop the element at tail of queue.
	A queue maintains a FIFO order (enqueue & dequeue).
	A stack (implemented as a queue) maintains a FILO order (push & pop).
*/
template <typename T>
T SingleLinkList<T>::pop()
{

	// **** check if the queue is empty ****

	if (count <= 0)
	{
		throw QueueIsEmpty;
	}

	// **** for ease of use ****

	Node<T> *node = tail;

	// **** get the data (to be returned) from the tail node ****

	T data = node->data;


	// **** queue has a single element ****

	if (count == 1) {
	
		// **** update the head and tail pointers (queue will be empty) ****

		head = (Node<T> *)this;
		tail = (Node<T> *)this;
	}

	// **** queue has more than one element ****

	else {
	
		// **** get to the node before the tail ****

		Node<T> *p = head;
		for ( ; p->next != tail; p = p->next) {}

		// **** update tail pointer ****

		tail	= p;

		// **** update new tail node ****

		p->next = (Node<T> *)this;
	}

	// **** free (previous tail) node ****

	delete(node);

	// **** decrement queue count ****

	count--;

	// **** return value ****

	return data;
}

/*
	Insert the specified element BEFORE the specified one.
*/
template <typename T>
void SingleLinkList<T>::insertBefore(Node<T> *p, T myData)
{

	// **** check if queue is full ****

	if ((maxCount != 0) && (count >= maxCount))
	{
		throw QueueIsFull;
	}

	// **** check for null pointer ****

	if (p == nullptr)
	{
		throw QueueNullPointer;
	}

	// **** check if specified pointer is NOT in the queue ****

	if (!isValidPointer(p))
	{
		throw QueueInvalidPointer;
	}

	// **** allocate new node ****

	Node<T> *node = new Node<T>(myData);

	// **** node being inserted BEFORE p ****

	node->next = p;

	// **** insert BEFORE head ****

	if (p == head) {
		node->next = head;
		head = node;
	}

	// **** insert somewhere else ****

	else {
	
		// **** get to the node before p ****

		Node<T> *q = head;
		for ( ; q->next != p; q = q->next) {}

		// **** ****

		q->next = node;
	}

	// **** update the queue ****

	count++;
}

/*
	PUSH and element into a stack (implemented as a queue).
*/
template <typename T>
void SingleLinkList<T>::push(T myData)
{
	enqueue(myData);
}

As you can see in the last lines of the SingleLinkList class, the push method is implemented by calling the enqueue method.

Also note that the queue contains the count and maxCount members. The reason is to quickly be able to tell the count without traversing the queue and more important to be able to implement XON / XOFF. More on this in a future post.

If you have comments or questions regarding this or any other post in this blog, please feel free and send me a message. I will not use your name unless you explicitly allow me to do so.

John

john.canessa@gmail.com

Follow me on Twitter:  @john_canessa