I continue to design and implement the DoubleLinkList class using C++. If interested, please take a look at the previous post on this series: Linked List – Part IV
Following is a screen capture of the Windows console with output from the test program generated by Visual Studio 2013:
main <<< testing widgets ... main <<< widget: this: 0x11b85ceea8 id: 1234 name ==>widget_1234<== main <<< testing nodes ... main <<< node: this: 0x11b85cef60 next: 0x0 prev: 0x0 main <<< widget: this: 0x11b85cef68 id: 1234 name ==>widget_1234<== main <<< n this: 0x191de5706b0 next: 0x0 prev: 0x0 data: 1 main <<< crudeList this: 0x191de5706b0 next: 0x191de5706b0 prev: 0x191de5706b0 data: 1 main <<< n this: 0x191de571280 next: 0x0 prev: 0x0 data: 2 main <<< crudeList this: 0x191de5706b0 next: 0x191de571280 prev: 0x191de571280 data: 1 main <<< n this: 0x191de571180 next: 0x0 prev: 0x0 data: 3 main <<< crudeList this: 0x191de5706b0 next: 0x191de571280 prev: 0x191de571180 data: 1 main <<< n this: 0x191de5713a0 next: 0x0 prev: 0x0 data: 4 main <<< crudeList this: 0x191de5706b0 next: 0x191de571280 prev: 0x191de5713a0 data: 1 main <<< n this: 0x191de5714c0 next: 0x0 prev: 0x0 data: 5 main <<< crudeList this: 0x191de5706b0 next: 0x191de571280 prev: 0x191de5714c0 data: 1 main <<< p this: 0x191de5706b0 next: 0x191de571280 prev: 0x191de5714c0 data: 1 main <<< p this: 0x191de571280 next: 0x191de571180 prev: 0x191de5706b0 data: 2 main <<< p this: 0x191de571180 next: 0x191de5713a0 prev: 0x191de571280 data: 3 main <<< p this: 0x191de5713a0 next: 0x191de5714c0 prev: 0x191de571180 data: 4 main <<< p this: 0x191de5714c0 next: 0x191de5706b0 prev: 0x191de5713a0 data: 5 main <<< testing link list ... main <<< list: this: 0x191de571540 count: 0 maxCount: 13 head: 0x191de571540 tail: 0x191de571540 main <<< enqueue widget: this: 0x11b85cf1b8 id: 1 name ==>widget_1<== main <<< enqueue widget: this: 0x11b85cf1b8 id: 2 name ==>widget_2<== main <<< enqueue widget: this: 0x11b85cf1b8 id: 3 name ==>widget_3<== main <<< enqueue widget: this: 0x11b85cf1b8 id: 4 name ==>widget_4<== main <<< enqueue widget: this: 0x11b85cf1b8 id: 5 name ==>widget_5<== main <<< list: this: 0x191de571540 count: 5 maxCount: 13 head: 0x191de571930 tail: 0x191de571eb0 p: 0x191de571930 data: this: 0x191de571938 id: 1 name ==>widget_1<== next: 0x191de571af0 p: 0x191de571af0 data: this: 0x191de571af8 id: 2 name ==>widget_2<== next: 0x191de571c30 p: 0x191de571c30 data: this: 0x191de571c38 id: 3 name ==>widget_3<== next: 0x191de571d70 p: 0x191de571d70 data: this: 0x191de571d78 id: 4 name ==>widget_4<== next: 0x191de571eb0 p: 0x191de571eb0 data: this: 0x191de571eb8 id: 5 name ==>widget_5<== next: 0x191de571540 main <<< dequeue widget: this: 0x11b85cf2a0 id: 1 name ==>widget_1<== main <<< dequeue widget: this: 0x11b85cf2a0 id: 2 name ==>widget_2<== main <<< dequeue widget: this: 0x11b85cf2a0 id: 3 name ==>widget_3<== main <<< dequeue widget: this: 0x11b85cf2a0 id: 4 name ==>widget_4<== main <<< dequeue widget: this: 0x11b85cf2a0 id: 5 name ==>widget_5<== main <<< enqueue widget: this: 0x11b85ceea8 id: 1 name ==>widget_1<== main <<< enqueue widget: this: 0x11b85ceea8 id: 2 name ==>widget_2<== main <<< enqueue widget: this: 0x11b85ceea8 id: 3 name ==>widget_3<== main <<< head: this: 0x11b85cf3d0 id: 1 name ==>widget_1<== main <<< tail: this: 0x11b85cf430 id: 3 name ==>widget_3<== main <<< count: 3 j: 1 p: this: 0x191de571a70 next: 0x191de571bb0 prev: 0x191de5718b0 main <<< insertAfter widget: this: 0x11b85cf548 id: 4 name ==>widget_4<== main <<< count: 4 j: 2 p: this: 0x191de571cf0 next: 0x191de571bb0 prev: 0x191de571a70 main <<< insertAfter widget: this: 0x11b85cf548 id: 5 name ==>widget_5<== main <<< count: 5 j: 4 p: this: 0x191de571bb0 next: 0x191de571540 prev: 0x191de571eb0 main <<< insertAfter widget: this: 0x11b85cf548 id: 6 name ==>widget_6<== main <<< count: 6 j: 1 p: this: 0x191de571a70 next: 0x191de571cf0 prev: 0x191de5718b0 main <<< insertAfter widget: this: 0x11b85cf548 id: 7 name ==>widget_7<== main <<< count: 7 j: 1 p: this: 0x191de571a70 next: 0x191de572130 prev: 0x191de5718b0 main <<< insertAfter widget: this: 0x11b85cf548 id: 8 name ==>widget_8<== main <<< count: 8 j: 4 p: this: 0x191de571cf0 next: 0x191de571eb0 prev: 0x191de572130 main <<< insertAfter widget: this: 0x11b85cf548 id: 9 name ==>widget_9<== main <<< count: 9 j: 0 p: this: 0x191de5718b0 next: 0x191de571a70 prev: 0x0 main <<< insertAfter widget: this: 0x11b85cf548 id: 10 name ==>widget_10<== main <<< count: 10 j: 8 p: this: 0x191de571bb0 next: 0x191de571ff0 prev: 0x191de571eb0 main <<< insertAfter widget: this: 0x11b85cf548 id: 11 name ==>widget_11<== main <<< count: 11 j: 6 p: this: 0x191de5723b0 next: 0x191de571eb0 prev: 0x191de571cf0 main <<< insertAfter widget: this: 0x11b85cf548 id: 12 name ==>widget_12<== main <<< count: 12 j: 10 p: this: 0x191de572630 next: 0x191de571ff0 prev: 0x191de571bb0 main <<< insertAfter widget: this: 0x11b85cf548 id: 13 name ==>widget_13<== main <<< list: this: 0x191de571540 count: 13 maxCount: 13 head: 0x191de5718b0 tail: 0x191de571ff0 p: 0x191de5718b0 data: this: 0x191de5718b8 id: 1 name ==>widget_1<== next: 0x191de5724f0 p: 0x191de5724f0 data: this: 0x191de5724f8 id: 10 name ==>widget_10<== next: 0x191de571a70 p: 0x191de571a70 data: this: 0x191de571a78 id: 2 name ==>widget_2<== next: 0x191de572270 p: 0x191de572270 data: this: 0x191de572278 id: 8 name ==>widget_8<== next: 0x191de572130 p: 0x191de572130 data: this: 0x191de572138 id: 7 name ==>widget_7<== next: 0x191de571cf0 p: 0x191de571cf0 data: this: 0x191de571cf8 id: 4 name ==>widget_4<== next: 0x191de5723b0 p: 0x191de5723b0 data: this: 0x191de5723b8 id: 9 name ==>widget_9<== next: 0x191de572770 p: 0x191de572770 data: this: 0x191de572778 id: 12 name ==>widget_12<== next: 0x191de571eb0 p: 0x191de571eb0 data: this: 0x191de571eb8 id: 5 name ==>widget_5<== next: 0x191de571bb0 p: 0x191de571bb0 data: this: 0x191de571bb8 id: 3 name ==>widget_3<== next: 0x191de572630 p: 0x191de572630 data: this: 0x191de572638 id: 11 name ==>widget_11<== next: 0x191de5728b0 p: 0x191de5728b0 data: this: 0x191de5728b8 id: 13 name ==>widget_13<== next: 0x191de571ff0 p: 0x191de571ff0 data: this: 0x191de571ff8 id: 6 name ==>widget_6<== next: 0x191de571540 main <<< pop widget: this: 0x11b85ceea8 id: 6 name ==>widget_6<== main <<< pop widget: this: 0x11b85ceea8 id: 13 name ==>widget_13<== main <<< pop widget: this: 0x11b85ceea8 id: 11 name ==>widget_11<== main <<< pop widget: this: 0x11b85ceea8 id: 3 name ==>widget_3<== main <<< pop widget: this: 0x11b85ceea8 id: 5 name ==>widget_5<== main <<< pop widget: this: 0x11b85ceea8 id: 12 name ==>widget_12<== main <<< pop widget: this: 0x11b85ceea8 id: 9 name ==>widget_9<== main <<< pop widget: this: 0x11b85ceea8 id: 4 name ==>widget_4<== main <<< pop widget: this: 0x11b85ceea8 id: 7 name ==>widget_7<== main <<< pop widget: this: 0x11b85ceea8 id: 8 name ==>widget_8<== main <<< pop widget: this: 0x11b85ceea8 id: 2 name ==>widget_2<== main <<< pop widget: this: 0x11b85ceea8 id: 10 name ==>widget_10<== main <<< pop widget: this: 0x11b85ceea8 id: 1 name ==>widget_1<==
Following is my test code:
// **** ****
#include <iostream>
#include <time.h>
// **** ****
using namespace std;
// **** header files (templates contain actual implementations) ****
#include "Widget.h"
#include "Node.h"
#include "SingleLinkList.h"
#include "DoubleLinkList.h"
#include "Solution.h"
// **** constructor ****
Solution::Solution()
{}
// **** destructor ****
Solution::~Solution()
{}
/*
* TEST code.
*/
int main()
{
// **** constant(s) ****
const int MAX_ELEMENTS = 13;
// **** ****
char buffer[BUFSIZ];
errno_t error = 0;
// ***** 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);
}
// ***** activity message ****
cout << "main <<< testing link list ..." << endl;
// **** allocate a linked list ****
//SingleLinkList<Widget> *list = new SingleLinkList<Widget>(MAX_ELEMENTS);
DoubleLinkList<Widget> *list = new DoubleLinkList<Widget>(MAX_ELEMENTS);
cout << "main <<< list: " << list->toString() << endl;
// **** loop inserting elements into the queue ****
for (int i = 1; i <= 5; i++) { // **** check if queue is full **** if (list->isFull()) {
cout << "main <<< list->isFull() i: " << i << endl;
continue;
}
// **** set the widget to be inserted into the queue ****
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 **** try { list->enqueue(widget);
} catch (const int ex) {
cerr << "main <<< EXCEPTION - list->enqueue(widget) ex: " << ex << endl;
exit(ex);
}
}
cout << "main <<< list: " << list->toString() << endl << 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++) { // **** check if queue is full **** if (list->isFull())
{
cout << "main <<< list->isFull() i: " << i << endl;
continue;
}
// **** 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;
// **** seed the pseudo random number generator ****
srand((unsigned int)time(nullptr));
// **** insert after ****
int j = 0;
Node<Widget> *p = nullptr;
for (int i = 0; i < 10; i++) { // **** check if queue is full **** if (list->isFull()) {
cerr << "main <<< list->isFull i: " << i << endl; continue; } // **** generate a random location in the queue **** j = rand() % list->getCount();
// **** pointer to specified element in the queue ****
p = list->elementAt(j);
cout << "main <<< count: " << list->getCount() << " j: " << j << " p: " << p->toString() << endl; // **** set 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;
// **** display the list ****
cout << "main <<< list: " << list->toString() << endl << endl; // **** POP from the tail of the queue (all widgets) **** while (!list->isEmpty()) {
widget = list->pop();
cout << "main <<< pop widget: " << widget.toString() << endl;
}
cout << endl; #ifdef CAKE // **** 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;
}
Note that the name of the list has been changed so we are now able to invoke the same tests with a single or a double link list.
The sections of code following the #define CAKE in the source code signals code that has not been implemented yet.
The current C++ source code for the DoubleLinkList class follows:
#pragma once
// **** ****
#include <string>
// **** ****
#include "Node.h"
// **** vvvv class definition vvvv
template <typename T>
class DoubleLinkList
{
// **** 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:
DoubleLinkList();
// **** constructor ****
public:
DoubleLinkList(int maxElements);
// **** destructor ****
public:
~DoubleLinkList();
// **** list of getters ****
public:
Node<T> *DoubleLinkList<T>::getHead();
public:
int DoubleLinkList<T>::getCount();
public:
Node<T> *DoubleLinkList<T>::getTail();
// **** list of setters ****
// **** generate string for the specified queue object ****
public:
std::string DoubleLinkList<T>::toString();
// **** enqueue element at tail of queue ****
public:
void DoubleLinkList<T>::enqueue(T myData);
// **** check if queue is full ****
public:
bool DoubleLinkList<T>::isFull();
// **** check if queue is empty ****
public:
bool DoubleLinkList<T>::isEmpty();
// **** dequeue element at head of queue ****
public:
T DoubleLinkList<T>::dequeue();
// ***** peek at the head element of the queue ****
public:
T DoubleLinkList<T>::peekHead();
// **** peek at the tail of the queue ****
public:
T DoubleLinkList<T>::peekTail();
// **** return a pointer to the element in the queue at the specified location ****
public:
Node<T> *DoubleLinkList<T>::elementAt(int loc);
// **** insert element AFTER specified element ****
public:
void DoubleLinkList<T>::insertAfter(Node<T> *p, T myData);
// **** check if pointer points to element in this queue ****
public:
bool DoubleLinkList<T>::isValidPointer(Node<T> *p);
// **** pop element from head of queue (FIFO - stack) ****
public:
T DoubleLinkList<T>::pop();
};
// **** vvvv class implementation vvvv
/*
Base constructor.
*/
template <typename T>
DoubleLinkList<T>::DoubleLinkList()
{
count = 0;
maxCount = 0;
head = (Node<T> *)this;
tail = (Node<T> *)this;
}
/*
Constructor indicating max count of element is the queue.
*/
template <typename T>
DoubleLinkList<T>::DoubleLinkList(int maxElements)
{
// **** check if the max number of elements is invalid ****
if (maxElements < 0)
{
throw QueueInvalidMaxCount;
}
// **** ****
count = 0;
maxCount = maxElements;
head = (Node<T> *)this;
tail = (Node<T> *)this;
}
/*
Base destructor.
*/
template <typename T>
DoubleLinkList<T>::~DoubleLinkList()
{}
/*
Build a string representation of the queue and it's elements.
*/
template <typename T>
std::string DoubleLinkList<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);
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 DoubleLinkList<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 (DoubleLinkList<T>::count == 0)
{
DoubleLinkList<T>::head = node;
DoubleLinkList<T>::tail = node;
}
// **** insert new element at the tail of the queue ****
else
{
DoubleLinkList<T>::tail->next = node;
node->prev = DoubleLinkList<T>::tail;
}
// **** ****
node->next = (Node<T> *)this;
DoubleLinkList<T>::tail = node;
DoubleLinkList<T>::count++;
}
/*
Determine if the queue is FULL.
Same but less elegant approach could be achieved with getCount() and a test.
*/
template <typename T>
bool DoubleLinkList<T>::isFull()
{
return (count >= maxCount);
}
/*
Determine if the queue is EMPTY.
Same but less elegant approach could be achieved with getCount() and a test.
*/
template <typename T>
bool DoubleLinkList<T>::isEmpty()
{
return (count <= 0);
}
/*
Dequeue element at head of queue.
The queue maintains a FIFO order (enqueue & dequeue).
*/
template <typename T>
T DoubleLinkList<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;
// **** first remaining node points to the queue ****
node->next->prev = (Node<T> *)this;
// **** free (head) node ****
delete(node);
// **** decrement queue count ****
count--;
// **** update tail (queue is empty) ****
if (count == 0)
{
head = (Node<T> *)this;
tail = (Node<T> *)this;
}
// **** return data ****
return data;
}
/*
Return the element at the HEAD of the queue.
Throws exception if queue is empty.
*/
template <typename T>
T DoubleLinkList<T>::peekHead()
{
if (count <= 0) { throw QueueIsEmpty; } else { return this->head->data;
}
}
/*
Return the element at the TAIL of the queue.
Throws exception if queue is empty.
*/
template <typename T>
T DoubleLinkList<T>::peekTail()
{
if (count <= 0) { throw QueueIsEmpty; } else { return this->tail->data;
}
}
/*
Get the element at the HEAD of the queue.
Element is not removed from the queue.
*/
template <typename T>
Node<T> *DoubleLinkList<T>::getHead()
{
return head;
}
/*
Get the count of elements in the queue.
*/
template <typename T>
int DoubleLinkList<T>::getCount()
{
return count;
}
/*
Get the TAIL from the queue.
Element is not removed from the queue.
*/
template <typename T>
Node<T> *DoubleLinkList<T>::getTail()
{
return tail;
}
/*
Return a pointer to the element in the queue at the specified location.
The first element is at location 0.
*/
template <typename T>
Node<T> *DoubleLinkList<T>::elementAt(int loc)
{
// **** check if location is out of range ****
if ((loc < 0) || (loc > count))
{
throw QueueInvalidLocation;
}
// **** traverse the queue until the specified location is reached ****
Node<T> *p = head;
for (int i = 0; i < loc; i++) { p = p->next;
}
// **** ****
return p;
}
/*
Insert the specified element AFTER the specified one.
*/
template <typename T>
void DoubleLinkList<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;
node->prev = p;
p->next->prev = node;
p->next = node;
// **** update the queue ****
if (p == tail)
{
tail = node;
}
count++;
}
/*
Check if the specified pointer a valid pointer in this queue.
*/
template<typename T>
bool DoubleLinkList<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;
}
/*
Pop the element at tail of the 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 DoubleLinkList<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 at this time ****
if (count == 1)
{
head = (Node<T> *)this;
tail = (Node<T> *)this;
}
// **** queue has more than one element at this time ****
else
{
tail = tail->prev;
tail->next = (Node<T> *)this;
}
// **** free (previous tail) node ****
delete(node);
// **** decrement queue count ****
count--;
// **** return value ****
return data;
}
Please note that this is still work in progress. Should have it completed in the next related post.
If you have comments or questions regarding this or any other post in this blog, please do not hesitate 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