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