Linked Lists – Part IV

Hope you had a nice weekend. Over the weekend and for preparation to start the design and implementation of the DoubleLinkList class I started updating the test code for the LinkedLists test class. The current code builds a crude list taking into account the pre and next members of the Node class.

Following is a screen capture of the console for Visual Studio 2013 when executing a partially commented out test:

main <<< testing widgets ...
main <<< widget: this: 0x14294ffa48 id: 1234 name ==>widget_1234<==

main <<< testing nodes ...
main <<< node:  this: 0x14294ffb00 next: 0x0 prev: 0x0
main <<< widget: this: 0x14294ffb08 id: 1234 name ==>widget_1234<==

main <<<         n  this: 0x1bc8bc406d0 next: 0x0 prev: 0x0 data: 1
main <<< crudeList  this: 0x1bc8bc406d0 next: 0x1bc8bc406d0 prev: 0x1bc8bc406d0 data: 1
main <<<         n  this: 0x1bc8bc412a0 next: 0x0 prev: 0x0 data: 2
main <<< crudeList  this: 0x1bc8bc406d0 next: 0x1bc8bc412a0 prev: 0x1bc8bc412a0 data: 1
main <<<         n  this: 0x1bc8bc411a0 next: 0x0 prev: 0x0 data: 3
main <<< crudeList  this: 0x1bc8bc406d0 next: 0x1bc8bc412a0 prev: 0x1bc8bc411a0 data: 1
main <<<         n  this: 0x1bc8bc413c0 next: 0x0 prev: 0x0 data: 4
main <<< crudeList  this: 0x1bc8bc406d0 next: 0x1bc8bc412a0 prev: 0x1bc8bc413c0 data: 1
main <<<         n  this: 0x1bc8bc414e0 next: 0x0 prev: 0x0 data: 5
main <<< crudeList  this: 0x1bc8bc406d0 next: 0x1bc8bc412a0 prev: 0x1bc8bc414e0 data: 1

main <<< p  this: 0x1bc8bc406d0 next: 0x1bc8bc412a0 prev: 0x1bc8bc414e0 data: 1
main <<< p  this: 0x1bc8bc412a0 next: 0x1bc8bc411a0 prev: 0x1bc8bc406d0 data: 2
main <<< p  this: 0x1bc8bc411a0 next: 0x1bc8bc413c0 prev: 0x1bc8bc412a0 data: 3
main <<< p  this: 0x1bc8bc413c0 next: 0x1bc8bc414e0 prev: 0x1bc8bc411a0 data: 4
main <<< p  this: 0x1bc8bc414e0 next: 0x1bc8bc406d0 prev: 0x1bc8bc413c0 data: 5

In addition I am displaying the data value in the node.

As I commented before, I am using the first node as the head of the queue. This is poor practice. Think about passing the queue around some threads and having one deleting the first node.

The C++ code for the test class follows:

// **** ****

#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;
	cout << endl;

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

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

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

		Node<int> *n = new Node<int>(i);
		cout << "main <<<         n " << n->toString() << " data: " << n->data << endl; // **** if list is emply then this node becomes the list (poor practice) **** if (crudeList == nullptr) { crudeList = n; n->next		= crudeList;
			n->prev		= crudeList;
		} 
		
		// **** else insert the node at the tail of the list ****

		else {
			Node<int> *p = crudeList;
			for ( ; p->next != crudeList; p = p->next) {}
			p->next = n;
			n->next = crudeList;
			n->prev = p;
			crudeList->prev = n;
		}

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

		cout << "main <<< crudeList " << crudeList->toString() << " data: " << crudeList->data << endl;
	}
	cout << endl;

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

	for (Node<int> *p = crudeList; true; p = p->next)
	{
		cout << "main <<< p " << p->toString() << " data: " << p->data << endl; if (p->next == crudeList) {
			break;
		}
	}
	cout << endl;

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

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


#ifdef CAKE
	// ***** activity message ****

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

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

	SingleLinkList<Widget> *list = new SingleLinkList<Widget>(MAX_ELEMENTS);
	cout << "main <<< list: " << list->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 **** list->enqueue(widget);
	}
	cout << "main <<< list: " << list->toString() << endl;
	cout << endl; // **** loop removing elements from the queue **** while (!list->isEmpty()) {
		cout << "main <<< dequeue widget: " << list->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 **** list->enqueue(widget);
	}
	cout << endl;

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

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

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

	cout << "main <<< tail: " << list->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 (list->isFull()) {
			cout << "main <<< list->isFull i: " << i << endl;
			continue;
		}

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

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

			default:					// random location in queue

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

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

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

				p = list->elementAt(j);
			break;
		}
		cout << "main <<< j: " << j << " p: " << p->toString() << endl; // **** create a widget **** int widgetId = list->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 { list->insertAfter(p, widget);
		} catch (int ex) {
			cerr << "main <<< EXCEPTION list->insertAfter ex: " << ex << endl; 
			exit(ex);
		}
	}
	cout << endl; // **** POP from the tail of the queue (all widgets) **** while (!list->isEmpty()) {

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

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

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

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

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

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

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

		Node<Widget> *p;

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

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

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

		try {
			p = list->elementAt(j);
		} catch (int ex) {
			cout << "main <<< EXCEPTION list->elementAt j: " << j << " ex: " << ex << endl;
			exit(ex);
		}
		cout << "main <<< j: " << j << " p: " << p->toString() << endl; // **** create a widget **** int widgetId = list->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 { list->insertBefore(p, widget);
		}
		catch (int ex)
		{
			cerr << "main <<< EXCEPTION list->insertBefore ex: " << ex << endl;
			exit(ex);
		}
	}
	cout << endl; // **** clear the queue **** while (!list->isEmpty()) {
		list->dequeue();
	}

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

	for (int i = 0; i <= 7; i++) { // **** check if the stack is full **** if (list->isFull()) {
			cout << "main <<< list->isFull i: " << i << endl; continue; } // **** create a widget **** int widgetId = list->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) **** list->push(widget);
	}
	cout << endl; // **** pop elements from the stack (queue) **** while (!list->isEmpty()) {
		cout << "main <<<  pop widget: " << list->pop().toString() << endl;
	}
#endif


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

	return 0;
}

Please note that the code inside the #ifdef CAKE directive is not currently being used. The only thing I did was to change the name of the list from slq to list.

If you have comments or questions regarding this or any other entry in this post, please send me a message. Will reply ASAP and will not use your name unless you explicitly allow me to do so.

John
john.canessa@gmail.com
Follow me on Twitter: @john_canessa

Leave a Reply

Your email address will not be published. Required fields are marked *