⚡ Embedded Modern C++ Section 12 • #12.10
Portal Home / Section 12 / Project 12.10: _for-proj12-2-files
Project 12.10 Section 12 ⚡ Embedded Relevance: Core Reference Architecture Data Structures Comparative Analysis

12.10 Comparative Data Structure Evaluation for Real-Time Firmware

Executive Summary: Comparative architectural review of custom data structure implementations across performance, footprint, and deterministic timing metrics.

💻 1. Annotated Source Code 

#ifndef LIST_H
#define LIST_H

class List {
public:
	virtual void add(int newEntry) = 0;
	virtual void add(int newEntry, int position) = 0;
	virtual void set(int newEntry, int position) = 0;

	virtual bool contains(int entry) const = 0;
	virtual int find(int entry) const = 0;
	virtual int remove(int position) = 0;
	virtual void makeEmpty() = 0;

	virtual int size() const = 0;
	virtual bool isEmpty() const = 0;
	virtual void printList() const = 0;

};

#endif
#ifndef LINKED_LIST_H
#define LINKED_LIST_H

#include <iostream>
#include "List.h"
using namespace std;

// ---------------- Node -------------------- //
class Node {
	public:
		Node(int data, Node* next) {
			this->data = data;
			this->next = next;
		}//end ctor

		int getData() const {
			return data;
		}

		void setData(int data) {
			this->data = data;
		}

		Node* getNext() const {
			return next;
		}

		void setNext(Node* next) {
			this->next = next;
		}

	private:
		int data;
		Node* next;
};

// --------------- Linked List ---------------------//
class LinkedList : public List {
	public:
		LinkedList() {
			mHead = nullptr;
			mNumElements = 0;
		}//end ctor

		virtual ~LinkedList() {
			makeEmpty();  //clean up the nodes
		}//end dtor

		void add(int newEntry) override {
			Node* newNode = new Node(newEntry, nullptr);

			if (mHead == nullptr) {
				mHead = newNode;
			}
			else {
				Node* walker = mHead;                        
				while (walker->getNext() != nullptr) {
					walker = walker->getNext();
				}//end while

				walker->setNext(newNode);
			}
			mNumElements++;
		}//end add


		void add(int newEntry, int position) override {
			if (position < 0 || position > mNumElements) {
				cout << "Error: Cannot add at specified position." << endl;
				return;
			}

			Node* newNode = new Node(newEntry, nullptr);

			if (position == 0) {
				newNode->setNext(mHead);
				mHead = newNode;
			}
			else {
				Node* nodeBefore = mHead;

				for (int i = 0; i < position - 1; i++) {
					nodeBefore = nodeBefore->getNext();
				}//end for 
				                                                         
				newNode->setNext(nodeBefore->getNext());     
				nodeBefore->setNext(newNode);
			}

			mNumElements++;
		}//end add

		void set(int newEntry, int position) override {
			if (position < 0 || position > mNumElements) {
				cout << "Error:  Invalid position." << endl;
				return;
			}

			Node* walker = mHead;

			for (int i = 0; i < position; i++) {
				walker = walker->getNext();
			}//end for 

			walker->setData(newEntry);
		}//end set

		bool contains(int entry) const override {
			return find(entry) != -1;
		}//end contains

		int find(int entry) const override {
			Node* walker = mHead;
			int index = 0;

			while (walker != nullptr) {
				if (walker->getData() == entry) {
					return index;
				}
				walker = walker->getNext();
				index++;
			}//end while

			return -1;

		}//end find

		int remove(int position) override {
			if (position < 0 || position >= mNumElements) {
				cout << "Error:  Cannot remove at specified position." << endl;
				return 0;
			}

			int dataToReturn = 0;

			if (position == 0) {
				Node* temp = mHead;
				dataToReturn = temp->getData();
				mHead = mHead->getNext();
				delete temp;
			}
			else {
				Node* nodeBefore = mHead;
				for (int i = 0; i < position - 1; i++) {
					nodeBefore = nodeBefore->getNext();
				}//end for

				Node* nodeToRemove = nodeBefore->getNext();
				Node* nodeAfter = nodeToRemove->getNext();
				dataToReturn = nodeToRemove->getData();

				nodeBefore->setNext(nodeAfter);
				delete nodeToRemove;
			}

			mNumElements--;
			return dataToReturn;
		}//end remove 

		void makeEmpty() override {
			Node* temp;
			while (mHead != nullptr) {
				temp = mHead;
				mHead = mHead->getNext();
				delete temp;
			}
		}//end makeEmpty

		int size() const override {
			return mNumElements;
		}//end size

		bool isEmpty() const override {
			return mNumElements == 0;
		}//end isEmpty

		void printList() const override {
			Node* walker = mHead;
			while (walker != nullptr) {
				cout << walker->getData() << endl;
				walker = walker->getNext();
			}//end while
		}

	private:
		Node* mHead;
		int mNumElements;
};



#endif 
#ifndef STACK_H
#define STACK_H

class Stack {
public:
	virtual void push(int newEntry) = 0;
	virtual int pop() = 0;
	virtual int peek() const = 0;
	virtual bool isEmpty() const = 0;
	virtual void makeEmpty() = 0;
};

#endif 
#include <iostream>
#include "LinkedStack.h"
using namespace std;

void printStack(LinkedStack& stack);

int main() {
	LinkedStack stack;

	stack.push(100);
	stack.push(150);
	stack.push(222);
	stack.push(71);
	stack.push(53);
	stack.push(125);

	printStack(stack);
	cout << "Again to verify it's intact:" << endl;
	printStack(stack);

	//cout << "Top of stack is: " << stack.peek() << endl;

	//while (!stack.isEmpty()) {
	//	cout << stack.pop() << endl;
	//}
	return 0;
}

void printStack(LinkedStack& stack) {
	LinkedStack temp;
	int data;

	while (!stack.isEmpty()) {
		data = stack.pop();
		cout << data << endl;
		temp.push(data);
	}//end while

	while (!temp.isEmpty()) {
		stack.push(temp.pop());
	}

}//end printStack

📐 2. Architecture & UML Class Model

📐 Hierarchical Data Structure Framework (Stack & List Polymorphism)
+ Public - Private # Protected
<<interface>> List<T> List Contract
Attributes / Data Members
(none / stateless)
Operations / Methods
+insert(pos: int, entry: const T&) : bool[pure virtual =0]
+remove(pos: int) : bool[pure virtual =0]
+getEntry(pos: int) : T const[pure virtual =0]
+isEmpty() : bool const[pure virtual =0]
+getLength() : size_t const[pure virtual =0]
<<template class>> LinkedList<T> Linked Implementation
Attributes / Data Members
-headPtr : Node<T>*
-itemCount : size_t
Operations / Methods
+insert(pos: int, entry: const T&) : bool[override]
+remove(pos: int) : bool[override]
+getEntry(pos: int) : T const[override]
<<interface>> Stack<T> Stack Contract
Attributes / Data Members
(none / stateless)
Operations / Methods
+push(entry: const T&) : bool[pure virtual =0]
+pop() : bool[pure virtual =0]
+peek() : T const[pure virtual =0]
+isEmpty() : bool const[pure virtual =0]
🔗 Architectural Relationships & Hierarchy
LinkedList<T> - - ▷ implements interface - - ▷ List<T>

📚 3. Core C++ Concepts Deep-Dive

Architectural Synthesis

Reviewing interface contracts and polymorphism across container implementations.

⚡ 4. Embedded Systems & Hardware Reality

Metric Synthesis

Comparing contiguous array performance vs linked node overhead in microcontroller systems.

💡 5. Production-Ready Embedded Refactoring

💡 Production-Ready Refactor 
// Architectural summary: Prefer contiguous static structures in microcontrollers

📝 Knowledge Verification Quiz

Test your understanding of the C++ concepts and embedded microcontroller trade-offs covered in this guide. Click any option for instant feedback.

Q1. In general, which container category is best suited for real-time microcontrollers?
A Contiguous bounded static containers (std::array, ring buffers, flat maps).
B Dynamic node-based containers (std::list, std::map).
C Deeply nested heap trees.
D Global void* pointers.
Detailed Explanation: Contiguous bounded containers provide deterministic execution, zero heap fragmentation, and maximum CPU cache efficiency.