For learning and reviewing purposes, I decided to build a linked list from scratch. The goal is to achieve a relatively featured implementation of a doubly linked list. At this point I have implemented a Node and a Widget to test with. Both classes and a Solution are all I have at this point in time. In the next day or two I hope to complete this task.
Given that I use among other IDEs Visual Studio, decided to use it. For programming language I selected C++. Expect to be using C++ for work about 50% of my development time.
I frequently mention that I develop software following a TDD approach. For
this reason I will generate three blogs related to the linked lists using C++. You should be able to see how the approach works.
Following is a screen capture of a Windows console with the output of my current test code:
main <<< testing widgets …
main <<< widget: id: 1234 name ==>widget_1234<==
main <<< testing nodes …
main <<< node: data: 5678 next: 0x0 prev: 0x0
main <<< p: data: 1 next: 0x2483c630660 prev: 0x0
main <<< p: data: 2 next: 0x2483c6310b0 prev: 0x0
main <<< p: data: 3 next: 0x2483c631130 prev: 0x0
main <<< p: data: 4 next: 0x2483c6311b0 prev: 0x0
main <<< p: data: 5 next: 0x2483c631230 prev: 0x0
main <<< p: data: 6 next: 0x2483c6312b0 prev: 0x0
main <<< p: data: 7 next: 0x0 prev: 0x0
main <<< deleting: data: 1 next: 0x2483c630660 prev: 0x0
main <<< deleting: data: 2 next: 0x2483c6310b0 prev: 0x0
main <<< deleting: data: 3 next: 0x2483c631130 prev: 0x0
main <<< deleting: data: 4 next: 0x2483c6311b0 prev: 0x0
main <<< deleting: data: 5 next: 0x2483c631230 prev: 0x0
main <<< deleting: data: 6 next: 0x2483c6312b0 prev: 0x0
main <<< deleting: data: 7 next: 0x0 prev: 0x0
It feels good to be using pointers. Have been working with Java and for some tasks (given that Java does not support pointers) seems like other programming languages (e.g., C / C++) are better suited.
The test code follows:
// **** ****
#include <iostream>
// **** ****
#include “Solution.h”
#include “Widget.h”
#include “Node.h”
// **** ****
using namespace std;
// **** constructor ****
Solution::Solution()
{}
// **** destructor ****
Solution::~Solution()
{}
/*
* TEST code.
*/
int main()
{
// ***** activity message ****
cout << “main <<< testing widgets …” << endl;
// **** instantiate a Widget ****
Widget widget = Widget();
// **** populate widget ****
try {
widget.setId(1234);
} catch (int ex) {
if (ex == widget.WidgetInvalidId) {
cout << “main <<< EXCEPTION widget.setId() – WidgetInvalidId” << endl;
exit(ex);
}
}
try {
widget.setName(“widget_1234”);
} catch (int ex) {
if (ex == widget.WidgetInvalidName) {
cout << “main <<< EXCEPTION widget.setName() – WidgetInvalidName” << endl;
exit(ex);
}
}
// **** display the widget ****
cout << “main <<< widget: ” << widget.toString() << endl;
// ***** activity message ****
cout << “main <<< testing nodes …” << endl;
// **** instantiate a node ****
Node *node = new Node();
// **** set the data in the node ****
node->data = 5678;
// **** display the node ****
cout << “main <<< node: ” << node->toString() << endl;
// **** delete the node ****
delete(node);
node = nullptr;
// **** implement a crude list ****
Node *list = nullptr;
for (int i = 1; i <= 7; i++) {
node = new Node(i);
if (list == nullptr) {
list = node;
} else {
Node *p = nullptr;
for (p = list; p->next != nullptr; p = p->next) {}
p->next = node;
}
}
// **** traverse the crude list ****
for (Node *p = list; p != nullptr; p = p->next) {
cout << “main <<< p: ” << p->toString() << endl;
}
// **** destroy the crude list ****
for (Node *p = list; p != nullptr; ) {
Node *n = p;
p = p->next;
cout << “main <<< deleting: ” + n->toString() << endl;
delete(n);
}
// **** all done ****
return 0;
}
The first part of the test deals with the Widget class. A widget is 
instantiated; the widget is populated and then displayed. I guess that nothing is to exciting about the specified sequence of operations. When all is said and done this class might remain as is or include a couple new members at most.
The current *.cpp and *.h files will only be used to test the queue implementations. The current code for the Widget.cpp follows:
#pragma once
#include <string>
class Node
{
// **** constants ****
public:
const int NodeInvalidData = -1;
// **** members ****
public:
int data;
Node *next;
Node *prev;
// **** constructor ****
public:
Node();
// **** constructor ****
public:
Node(int myData);
// **** destructor ****
public:
~Node();
// **** setters ***
void setData(int myData);
// **** getters ****
int getData();
// **** other methods ****
std::string toString();
};
The code for the Widget.h file follows:
// **** ****
#include <string>
// **** ****
#include “Node.h”
// **** constructor ****
Node::Node()
{
data = 0;
next = (Node *)nullptr;
prev = (Node *)nullptr;
}
// **** constructor ****
Node::Node(int myData) {
data = myData;
next = (Node *)nullptr;
prev = (Node *)nullptr;
}
// **** destructor ****
Node::~Node()
{}
// **** setters ****
void Node::setData(int myData) {
data = myData;
}
// **** getters ****
int Node::getData() {
return data;
}
// **** other methods ****
std::string Node::toString() {
std::string str = “”;
char buffer[64];
int error = _itoa_s(data, buffer, sizeof(buffer), 10);
str = “data: ” + std::string(buffer);
error = _i64toa_s((long long)next, buffer, sizeof(buffer), 16);
str += ” next: 0x” + std::string(buffer);
error = _i64toa_s((long long)prev, buffer, sizeof(buffer), 16);
str += ” prev: 0x” + std::string(buffer);
return str;
}
The Node class will be used as nodes of different types to be managed by the single and double link queues. At this time it only supports integers. The header file (Node.h) follows:
#pragma once
#include <string>
class Node
{
// **** constants ****
public:
const int NodeInvalidData = -1;
// **** members ****
public:
int data;
Node *next;
Node *prev;
// **** constructor ****
public:
Node();
// **** constructor ****
public:
Node(int myData);
// **** destructor ****
public:
~Node();
// **** setters ***
void setData(int myData);
// **** getters ****
int getData();
// **** other methods ****
std::string toString();
};
The source code in the Node.cpp file follows:
// **** ****
#include <string>
// **** ****
#include “Node.h”
// **** constructor ****
Node::Node()
{
data = 0;
next = (Node *)nullptr;
prev = (Node *)nullptr;
}
// **** constructor ****
Node::Node(int myData) {
data = myData;
next = (Node *)nullptr;
prev = (Node *)nullptr;
}
// **** destructor ****
Node::~Node()
{}
// **** setters ****
void Node::setData(int myData) {
data = myData;
}
// **** getters ****
int Node::getData() {
return data;
}
// **** other methods ****
std::string Node::toString() {
std::string str = “”;
char buffer[64];
int error = _itoa_s(data, buffer, sizeof(buffer), 10);
str = “data: ” + std::string(buffer);
error = _i64toa_s((long long)next, buffer, sizeof(buffer), 16);
str += ” next: 0x” + std::string(buffer);
error = _i64toa_s((long long)prev, buffer, sizeof(buffer), 16);
str += ” prev: 0x” + std::string(buffer);
return str;
}
The second part of the test code instantiate a node and directly sets some data. The contents of the node are displayed and then the node is deleted. The last section of this part implements a single link list. A few nodes are created and manually inserted into the simple queue. A final loop is used to delete the elements in the queue.
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 replay as soon as possible 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