C++ Data Structures with Templates

The Code

A C Linked List

// LinkedList.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <stdint.h>
#include <stdlib.h>
#include <iostream>
using namespace std;
typedef struct lNode {
	struct lNode *next;
	int data;
};
struct {
	lNode *lStart = NULL;
	lNode *lEnd = NULL;
}lList;
bool appendToList(int);
lNode* createNode(int);
void deleteList();
bool insertInList(int);
bool push_front(int);
lNode* getNext(int*, lNode*);
int* readNode(bool = false);
int main()
{
	push_front(99);
	for (int i = 0; i < 14; i++) {
		bool added = insertInList((int)rand() % 23);
	}
	lNode* i = lList.lStart;
	while (i != NULL) {
		cout << i->data << '\n';
		i = i->next;
	}
	int d;
	lNode* nxt = getNext(&d, lList.lStart);
	cout << d << '\n';
	while (nxt) {
		nxt = getNext(&d, nxt);
		cout << d << '\n';
	}
	int* ip = readNode(true);
	while (ip) {
		cout << *ip << '\n';
		ip = readNode();
	}
	ip = readNode(true);
	while (ip) {
		cout << *ip << '\n';
		ip = readNode();
	}
	deleteList();
	cin.get();
  return 0;
}
bool appendToList(int data) {
	lNode* nNode = createNode(data);
	if (nNode == NULL) {
		return false;
	}
	if (lList.lStart == NULL) {
		lList.lStart = nNode;
		lList.lEnd = nNode;
	}
	else {
		lList.lEnd = lList.lEnd->next = nNode;
	}
	return true;
}
lNode* createNode(int data) {
	lNode* rNode = (lNode*)malloc(sizeof(lNode));
	if (rNode != NULL) {
		rNode->data = data;
		rNode->next = NULL;
	}
	return rNode;
}
void deleteList() {
	lNode* rNode = lList.lStart;
	while (rNode != NULL) {
		lList.lStart = rNode->next;
		free(rNode);
		rNode = lList.lStart;
	}
	lList.lEnd = lList.lStart = NULL;
}
bool push_front(int data) {
	lNode* nNode = createNode(data);
	if (nNode == NULL) {
		return false;
	}
	nNode->next = lList.lStart;
	lList.lStart = nNode;
	if (lList.lEnd == NULL) {
		lList.lEnd = nNode;
	}
	return true;
}
bool insertInList(int data) {
	lNode* nNode = createNode(data);
	if (nNode == NULL) {
		return false;
	}
	if (lList.lStart == NULL) {
		// first item so just add it.
		lList.lStart = nNode;
		lList.lEnd = nNode;
	}
	else {
		// we need to look for the correct slot
		if (data <= lList.lStart->data) {
			// new value is <= first value in list)
			nNode->next = lList.lStart;
			lList.lStart = nNode;
		}
		else {
			lNode* rNode = lList.lStart;
			while (rNode) {
				if (data <= rNode->next->data) {
					// found the insertion point
					nNode->next = rNode->next;
					rNode->next = nNode;
					break;
				}
				rNode = rNode->next;
				if (!rNode) {
					// new value joins the end of the list
					lList.lEnd = lList.lEnd->next = nNode;
				}
			}
		}
	}
	return true;
}
lNode* getNext(int* i, lNode* n) {
	if (n) {
		*i = n->data;
		return n->next;
	}
	return NULL;
}
int* readNode(bool start) {
	static lNode* last;
	if (start) {
		last = lList.lStart;
	}
	else {
		if (last) {
			last = last->next;
		}
	}
	if (last) {
		return &(last->data);
	}
	return NULL;
}

Arduino Version Setup

int* readNode(bool = false);
void setup() {
  Serial.begin(115200);
  // now add some values to the list
  push_front(99);
  for (int i = 0; i < 14; i++) {
    bool added = insertInList((int)random(1, 23));
  }
  // read the values back
  lNode* rNode = lList.lStart;
  while(rNode != NULL) {
    Serial.println(rNode->data);
    rNode = rNode->next;
  }
  int* ip = readNode(true);
  while (ip) {
    Serial.println(*ip );
    ip = readNode();
  }
  deleteList();
}

A C++ Template Double Linked List

LinkedList.h

template<typename T>
class LinkedList {
public:
	using Comparator = int(*)(T*, T*);
	class iterator;
	LinkedList();
	~LinkedList();
	bool push_front(T*);
	bool push_back(T*);
	void clear();
	bool empty();
	iterator begin();
	iterator end();
	iterator rbegin();
	iterator rend();
	T* front();
	T* back();
	void pop_front();
	void pop_back();
	iterator insert(iterator, T*);
	void sort();
	void sort(Comparator);
	void reverse();
	size_t size();
private:
	size_t tSize, nSize, lSize;
	struct lNode {
		lNode* next;
		lNode* back;
		T* data;
	};
	struct {
		lNode *lStart = NULL;
		lNode *lEnd = NULL;
	}lList;
	lNode* createNode(const T*);
	void deleteList();
};
template<typename T>
class LinkedList<T>::iterator {
public:
	iterator(typename LinkedList<T>::lNode* pos, bool forward) {
		this->pos = pos;
		this->forward = forward; // iterator type
	}
	T operator*() const { return *(pos->data); }
	iterator &operator++() {
		if(forward) {
			pos = pos->next;
		}
		else {
			pos = pos->back;
		}
		return *this;
	}
	iterator &operator++(int) {
		if (forward) {
			pos = pos->next;
		}
		else {
			pos = pos->back;
		}
		return *this;
	}
	iterator &operator--() {
		if (forward) {
			pos = pos->back;
		}
		else {
			pos = pos->next;
		}
		return *this;
	}
	iterator &operator--(int) {
		if (forward) {
			pos = pos->back;
		}
		else {
			pos = pos->next;
		}
		return *this;
	}
	bool operator!=(const iterator a) {
		return (this->pos != (a.pos));
	};
	typename LinkedList<T>::lNode* pos;
	bool forward;
};
template<typename T>
LinkedList<T>::LinkedList() {
	tSize = sizeof(T);
	nSize = sizeof(lNode);
	lSize = 0;
}
template<typename T>
LinkedList<T>::~LinkedList() {
	deleteList();
}
// public methods
template<typename T>
bool LinkedList<T>::push_front(T* data) {
	lNode* nNode = createNode(data);
	if (nNode == NULL) {
		return false;
	}
	if (lList.lStart) {
		lList.lStart->back = nNode;
	}
	nNode->next = lList.lStart;
	lList.lStart = nNode;
	if (lList.lEnd == NULL) {
		lList.lEnd = nNode;
	}
	lSize++;
	return true;
}
template<typename T>
bool LinkedList<T>::push_back(T* data) {
	lNode* nNode = createNode(data);
	if (nNode == NULL) {
		return false;
	}
	if (lList.lStart == NULL) {
		lList.lStart = lList.lEnd = nNode;
	}
	else {
		nNode->back = lList.lEnd;
		lList.lEnd = lList.lEnd->next = nNode;
	}
	lSize++;
	return true;
}
template<typename T>
typename LinkedList<T>::iterator LinkedList<T>::insert(iterator it, T* data) {
	if (it.pos && it.pos != lList.lStart) {
		// we know there is a previous and next node
		lNode* nNode = createNode(data);
		if (nNode != NULL) {
			nNode->back = it.pos->back;
			nNode->next = it.pos;
			nNode->back->next = it.pos->back = nNode;
			iterator newIt(nNode, it.forward);
			lSize++;
			return newIt;
		}
	}
	else {
		// empty list or iterator at end or iterator at start
		if (!it.forward || it.pos == lList.lStart) {
			if (push_front(data)) {
				iterator newIt(lList.lStart, it.forward);
				return newIt;
			}
		}
		else {
			if (push_back(data)) {
				iterator newIt(lList.lEnd, it.forward);
				return newIt;
			}
		}
	}
	// signal that something went wrong
	// probably allocating memory
	return it.forward ? end() : rend();
}
template<typename T>
void LinkedList<T>::clear() {
	deleteList();
}
template<typename T>
bool LinkedList<T>::empty() {
	return (lList.lStart == NULL);
}
template<typename T>
size_t LinkedList<T>::size() {
	return lSize;
}
template<typename T>
typename LinkedList<T>::iterator LinkedList<T>::begin() {
	iterator it(lList.lStart, true);
	return it;
}
template<typename T>
typename LinkedList<T>::iterator LinkedList<T>::end() {
	iterator it(NULL, true); // equiv to lList.lEnd->next
	return it;
}
template<typename T>
typename LinkedList<T>::iterator LinkedList<T>::rbegin() {
	iterator it(lList.lEnd, false);
	return it;
}
template<typename T>
typename LinkedList<T>::iterator LinkedList<T>::rend() {
	iterator it(NULL, false);
	return it;
}
template<typename T>
T* LinkedList<T>::front() {
	if (lList.lStart) {
		return lList.lStart->data;
	}
	return NULL;
}
template<typename T>
T* LinkedList<T>::back() {
	if (lList.lEnd) {
		return lList.lEnd->data;
	}
	return NULL;
}
template<typename T>
void LinkedList<T>::pop_front() {
	if (lList.lStart) {
		lNode* d = lList.lStart;
		lList.lStart = d->next;
		if (d->next) {
			d->next->back = NULL;
		}
		free(d->data);
		free(d);
		lSize--;
	}
}
template<typename T>
void LinkedList<T>::pop_back() {
	if (lList.lEnd) {
		lNode* d = lList.lEnd;
		lList.lEnd = d->back;
		if (d->back) {
			d->back->next = NULL;
		}
		free(d->data);
		free(d);
		lSize--;
	}
}
template<typename T>
void LinkedList<T>::reverse() {
	iterator fw = begin();
	iterator bw = rbegin();
	T* temp;
	for (; fw.pos != bw.pos && fw.pos->back != bw.pos; fw++, bw++) {
		temp = bw.pos->data;
		bw.pos->data = fw.pos->data;
		fw.pos->data = temp;
	}
}
template<typename T>
void LinkedList<T>::sort(Comparator cmpFunc) {
	lNode *nLoop, *nTest;
	T* temp;
	bool swp;
	if (lList.lStart == lList.lEnd) {
		// empty or just one item so done
		return;
	}
	nTest = lList.lStart->next; // starts at second item in list
	while (nTest) {
		if (cmpFunc(nTest->data, nTest->back->data) < 0) {
			// this item is out of order so insert it earlier in list
			swp = true;
			nLoop = lList.lStart;
			while (swp) {
				swp = false;
				for (; nLoop != nTest; nLoop = nLoop->next) {
					//loop through the previous items in the list
					if (cmpFunc(nTest->data, nLoop->data) < 0) {
						// if a prior item is smaller then swap
						temp = nLoop->data;
						nLoop->data = nTest->data;
						nTest->data = temp;
						swp = true;
						break;
					}
				}
			}
		}
		nTest = nTest->next;
	}
}
template<typename T>
void LinkedList<T>::sort() {
	lNode *nLoop, *nTest;
	T* temp;
	bool swp;
	if (lList.lStart == lList.lEnd) {
		// empty or just one item so done
		return;
	}
	nTest = lList.lStart->next; // starts at second item in list
	while (nTest) {
		if(*nTest->data < *nTest->back->data) {
			// this item is out of order so insert it earlier in list
			swp = true;
			nLoop = lList.lStart;
			while (swp) {
				swp = false;
				for (; nLoop != nTest; nLoop = nLoop->next) {
					//loop through the previous items in the list
					if (*nTest->data < *nLoop->data) {
						// if a prior item is smaller then swap
						temp = nLoop->data;
						nLoop->data = nTest->data;
						nTest->data = temp;
						swp = true;
						break;
					}
				}
			}
		}
		nTest = nTest->next;
	}
}
template<typename T>
typename LinkedList<T>::lNode* LinkedList<T>::createNode(const T* t) {
	lNode* nNode = (lNode*)malloc(nSize);
	if (nNode != NULL) {
		nNode->data = (T*)malloc(tSize);
		if (nNode->data == NULL) {
			return NULL;
		}
		memcpy(nNode->data, t, tSize);
		nNode->next = NULL;
		nNode->back = NULL;
	}
	return nNode;
}
template<typename T>
void LinkedList<T>::deleteList() {
	lNode* dNode = lList.lStart;
	while (dNode != NULL) {
		lList.lStart = dNode->next;
		free(dNode->data);
		free(dNode);
		dNode = lList.lStart;
	}
	lList.lEnd = lList.lStart = NULL;
	lSize = 0;
}

LinkedList.cpp

#include "stdafx.h"
#include <stdint.h>
#include <stdlib.h>
#include <iostream>
#include "LinkedList.h"
using namespace std;
struct MyData {
	int valueC;
	int valueD;
};
int compMyData(MyData*, MyData*);
int compMyDataRev(MyData*, MyData*);
int compMyDataD(MyData*, MyData*);
void test2();
void test1();
void test3(); 
void test4();
int main()
{
	//test1();
	//test2();
	//test3();
	test4();
	/*int vals[] = { 2, 76, 65, 3, 99, 1, 56, 34, 22, 11, 101, 6 };
	LinkedList<int> newList;
	for (int i = 0; i < 12; i++) {
		newList.push_back(&vals[i]);
	}
	for (LinkedList<int>::iterator it = newList.begin(); it != newList.end(); it++) {
		cout << *it << '\n';
	}
	newList.sort();
	cout << "After sort\n";
	for (LinkedList<int>::iterator it = newList.begin(); it != newList.end(); it++) {
		cout << *it << '\n';
	}
	newList.clear();*/
	cin.get();
	return 0;
}
void test1() {
	int vals[] = { 2, 76, 65, 3, 99, 1, 56, 34, 22, 11, 101, 6 };
	LinkedList<int> newList;
	for (int i = 0; i < 12; i++) {
	newList.push_back(&vals[i]);
	}
	for (LinkedList<int>::iterator it = newList.begin(); it != newList.end(); it++) {
	cout << *it << '\n';
	}
	newList.sort();
	cout << "After sort\n";
	for (LinkedList<int>::iterator it = newList.begin(); it != newList.end(); it++) {
		cout << *it << '\n';
	}
}
void test2() {
	LinkedList<MyData> newList;
	MyData myData;
	for (int i = 0; i < 20; i++) {
		myData.valueC = rand() % 49;
		myData.valueD = rand() % 11;
		newList.push_back(&myData);
	}
	newList.sort(compMyData);
	for (LinkedList<MyData>::iterator it = newList.begin(); it != newList.end(); it++) {
		cout << "Value C: " << (*it).valueC << " Value D: " << (*it).valueD << '\n';
	}
}
void test3() {
	LinkedList<MyData> newList;
	MyData myData;
	for (int i = 0; i < 20; i++) {
		myData.valueC = rand() % 49;
		myData.valueD = rand() % 11;
		newList.push_back(&myData);
	}
	newList.sort(compMyDataRev);
	for (LinkedList<MyData>::iterator it = newList.begin(); it != newList.end(); it++) {
		cout << "Value C: " << (*it).valueC << " Value D: " << (*it).valueD << '\n';
	}
}
void test4() {
	LinkedList<MyData> newList;
	MyData myData;
	for (int i = 0; i < 20; i++) {
		myData.valueC = rand() % 49;
		myData.valueD = rand() % 11;
		newList.push_back(&myData);
	}
	newList.sort(compMyDataD);
	for (LinkedList<MyData>::iterator it = newList.begin(); it != newList.end(); it++) {
		cout << "Value C: " << (*it).valueC << " Value D: " << (*it).valueD << '\n';
	}
}
int compMyData(MyData* a, MyData* b) {
	if (a->valueC < b->valueC) { return -1; }
	if (b->valueC < a->valueC) { return 1; }
	if (a->valueD < b->valueD) { return -1; }
	if (b->valueD < a->valueD) { return 1; }
	return 0;
}
int compMyDataRev(MyData* a, MyData* b) {
	if (a->valueC < b->valueC) { return 1; }
	if (b->valueC < a->valueC) { return -1; }
	if (a->valueD < b->valueD) { return 1; }
	if (b->valueD < a->valueD) { return -1; }
	return 0;
}
int compMyDataD(MyData* a, MyData* b) {
	if (a->valueD < b->valueD) { return -1; }
	if (b->valueD < a->valueD) { return 1; }
	if (a->valueC < b->valueC) { return -1; }
	if (b->valueC < a->valueC) { return 1; }
	return 0;
}

LinkedList.ino (Arduino)

#include "LinkedList.h"
struct MyData {
  int valueC;
  int valueD;
};
template<class T> inline Print &operator <<(Print &obj, T arg) { obj.print(arg); return obj; }
void setup() {
  Serial.begin(115200);
  test4();
}
void test1() {
  int vals[] = { 2, 76, 65, 3, 99, 1, 56, 34, 22, 11, 101, 6 };
  LinkedList<int> newList;
  for (int i = 0; i < 12; i++) {
  newList.push_back(&vals[i]);
  }
  for (LinkedList<int>::iterator it = newList.begin(); it != newList.end(); it++) {
  Serial << *it << '\n';
  }
  newList.sort();
  Serial << "After sort\n";
  for (LinkedList<int>::iterator it = newList.begin(); it != newList.end(); it++) {
    Serial << *it << '\n';
  }
}
void test2() {
  LinkedList<MyData> newList;
  MyData myData;
  for (int i = 0; i < 20; i++) {
    myData.valueC = rand() % 49;
    myData.valueD = rand() % 11;
    newList.push_back(&myData);
  }
  newList.sort(compMyData);
  for (LinkedList<MyData>::iterator it = newList.begin(); it != newList.end(); it++) {
    Serial << "Value C: " << (*it).valueC << " Value D: " << (*it).valueD << '\n';
  }
}
void test3() {
  LinkedList<MyData> newList;
  MyData myData;
  for (int i = 0; i < 20; i++) {
    myData.valueC = rand() % 49;
    myData.valueD = rand() % 11;
    newList.push_back(&myData);
  }
  newList.sort(compMyDataRev);
  for (LinkedList<MyData>::iterator it = newList.begin(); it != newList.end(); it++) {
    Serial << "Value C: " << (*it).valueC << " Value D: " << (*it).valueD << '\n';
  }
}
void test4() {
  LinkedList<MyData> newList;
  MyData myData;
  for (int i = 0; i < 20; i++) {
    myData.valueC = rand() % 49;
    myData.valueD = rand() % 11;
    newList.push_back(&myData);
  }
  newList.sort(compMyDataD);
  for (LinkedList<MyData>::iterator it = newList.begin(); it != newList.end(); it++) {
    Serial << "Value C: " << (*it).valueC << " Value D: " << (*it).valueD << '\n';
  }
}
int compMyData(MyData* a, MyData* b) {
  if (a->valueC < b->valueC) { return -1; }
  if (b->valueC < a->valueC) { return 1; }
  if (a->valueD < b->valueD) { return -1; }
  if (b->valueD < a->valueD) { return 1; }
  return 0;
}
int compMyDataRev(MyData* a, MyData* b) {
  if (a->valueC < b->valueC) { return 1; }
  if (b->valueC < a->valueC) { return -1; }
  if (a->valueD < b->valueD) { return 1; }
  if (b->valueD < a->valueD) { return -1; }
  return 0;
}
int compMyDataD(MyData* a, MyData* b) {
  if (a->valueD < b->valueD) { return -1; }
  if (b->valueD < a->valueD) { return 1; }
  if (a->valueC < b->valueC) { return -1; }
  if (b->valueC < a->valueC) { return 1; }
  return 0;
}

Read the chapter in my book C++ Data Structures with immediate download from Amazon