⚡ Embedded Modern C++ Section 12 • #12.02
Portal Home / Section 12 / Project 12.02: ArrayListApp
Project 12.02 Section 12 ⚡ Embedded Relevance: High ArrayList Dynamic Array Amortized O(1) Memory Relocation

12.02 Implementing Custom Dynamic Arrays, Resize Policies, and Bounded Alternatives

Executive Summary: Building a custom dynamic array list implementing an abstract List interface. We analyze growth factors, amortized complexity, and contiguous memory access benefits.

💻 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 ARRAY_LIST_H 
#define ARRAY_LIST_H

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

class ArrayList : public List {
	public:
		ArrayList(int s = 16) : MAX_SIZE(s) {
			mArray = new int[MAX_SIZE];
			mNumElements = 0;
		}//end ctor

		void add(int newEntry) override {
			if (mNumElements >= MAX_SIZE) {
				cout << "Cannot add any more elements.  List is full." << endl;
				return;
			}

			mArray[mNumElements++] = newEntry;
		}//end add

		void add(int newEntry, int position) override {
			if (mNumElements >= MAX_SIZE) {
				cout << "List is full.  Cannot add element." << endl;
				return;
			}

			if (position < 0 || position > mNumElements) {
				cout << "Position out of range." << endl;
				return;
			}

			for (int i = mNumElements; i > position; i--) {
				mArray[i] = mArray[i - 1];
			}

			mArray[position] = newEntry;
			mNumElements++;
		}//end add

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

			mArray[position] = newEntry;
		}//end set 

		bool contains(int entry) const override {
			for (int i = 0; i < mNumElements; i++) {
				if (mArray[i] == entry) {
					return true;
				}
			}//end for 
			return false;
		}//end contains

		int find(int entry) const override {
			for (int i = 0; i < mNumElements; i++) {
				if (mArray[i] == entry) {
					return i;
				}
			}//end for
			return -1;
		}//end find

		int remove(int position) override {
			if (position < 0 || position >= mNumElements) {
				cout << "Position out of range." << endl;
				return -1;
			}

			int value = mArray[position];
			for (int i = position; i < mNumElements - 1; i++) {
				mArray[i] = mArray[i + 1];
			}//end for

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

		void makeEmpty() override {
			mNumElements = 0;
		}//end makeEmpty

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

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

		void printList() const override {
			for (int i = 0; i < mNumElements; i++) {
				cout << mArray[i] << endl;
			}
		}


	private:
		int* mArray;
		const int MAX_SIZE;
		int mNumElements;
};

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

int main() {
	ArrayList myList;

	for (int i = 0; i < 15; i++) {
		myList.add(i * 10);
	}

	myList.printList();

	cout << endl << "Size is " << myList.size() << endl;

	myList.add(555, 15);

	myList.printList();
	cout << "Size is now " << myList.size() << endl;

	myList.set(987, 3);  

	myList.printList();

	myList.add(1000);  //should trigger an error.

	return 0;
}

📐 2. Architecture & UML Class Model

📐 ArrayList Contiguous Sequential List Architecture
+ Public - Private # Protected
<<interface>> List<T> List Interface 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]
+~List()[virtual]
<<template class>> ArrayList<T> Contiguous List
Attributes / Data Members
-items[CAPACITY] : T
-itemCount : size_t = 0
-maxItems : size_t = CAPACITY
Operations / Methods
+ArrayList()
+insert(newPosition: int, newEntry: const T&) : bool[override, O(N) Shift]
+remove(position: int) : bool[override, O(N) Shift]
+getEntry(position: int) : T const[override, O(1)]
+replace(position: int, newEntry: const T&) : T[O(1)]
+clear() : void[O(1)]
+isEmpty() : bool const[override]
+getLength() : size_t const[override]
🔗 Architectural Relationships & Hierarchy
ArrayList<T> - - ▷ implements interface - - ▷ List<T>

📚 3. Core C++ Concepts Deep-Dive

Dynamic Array Fundamentals

Implements indexable random access ($O(1)$) with dynamic growth when capacity is reached.

⚡ 4. Embedded Systems & Hardware Reality

Heap Relocation Hazards

Resizing an ArrayList requires allocating a new memory block and copying all data, causing latency spikes in real-time loops.

💡 5. Production-Ready Embedded Refactoring

💡 Production-Ready Refactor 
// Bounded ArrayList with zero dynamic allocation
template <typename T, size_t MaxSize>
class BoundedList {
    std::array<T, MaxSize> data_; size_t size_ = 0;
};

📝 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. What is the random access lookup complexity of an ArrayList?
A O(1) constant time
B O(N)
C O(log N)
D O(N^2)
Detailed Explanation: Contiguous array storage enables direct address computation in $O(1)$ time.