I built this because I was bored. No real use case, no production target — just a C++17 exercise to shake off the rust and explore techniques I knew existed but had never actually used. What I didn't expect was how much the implementation taught me about things I thought I already understood.
The Problem With Homogeneous Lists
Every linked list tutorial shows you the same thing: a list of integers, or a list of strings. The node holds one type, the list holds nodes of that type, done.
That works — until you want a single list to hold an integer, a float, a string, and a custom struct at the same time. Then the standard approach falls apart immediately, because the type is baked into the node at compile time.
The question becomes: how do you build a node that doesn't care what it holds?
The Polymorphic Base — The "Wow" Moment
The answer is a polymorphic base class. Instead of a templated node that holds T directly, you separate the concerns:
// Base class — type-erased, polymorphic
class Object {
public:
virtual ~Object() = default;
virtual void print(std::ostream& os) const = 0;
virtual bool equals(const Object* other) const = 0;
Object* next = nullptr;
Object* prev = nullptr;
};
// Derived class — holds the actual value
template <typename T>
class Node : public Object {
public:
T data;
explicit Node(T value) : data(value) {}
void print(std::ostream& os) const override {
os << data;
}
bool equals(const Object* other) const override {
const Node<T>* otherNode = dynamic_cast<const Node<T>*>(other);
return otherNode && data == otherNode->data;
}
};
Object knows nothing about the type it holds — it only defines the interface. Node<T> knows the type, stores the value, and implements the interface.
The list holds Object* pointers. From the list's perspective, every node is an Object. The actual type is invisible at that level — which is exactly what allows the list to be heterogeneous.
When I saw this working for the first time — a single list printing an integer, then a float, then a string, then a struct, all through the same listPrint() call — it was genuinely surprising. Not because it's magic, but because the abstraction is so clean.
dynamic_cast — Type-Safe Downcasting at Runtime
This is the part that was completely new to me, and worth documenting carefully.
Once you have a list of Object* pointers, you lose type information at the list level. That's fine for printing — print() is virtual, it dispatches correctly. But what about searching? If I want to find the integer 42 in a mixed list, I need to:
- Skip nodes that aren't integers
- Compare only against nodes that actually hold
int
This is exactly what dynamic_cast does:
template <typename T>
Object* dlList::searchNodeInList(T value) {
Object* current = head;
while (current != nullptr) {
Node<T>* typedNode = dynamic_cast<Node<T>*>(current);
if (typedNode && typedNode->data == value) {
return current;
}
current = current->next;
}
return nullptr;
}
dynamic_cast<Node<T>*>(current) attempts to cast the Object* pointer to a Node<T>*. If the actual runtime type of the object is Node<T> — it succeeds and returns a valid pointer. If the actual type is something else — Node<float>, Node<std::string> — it returns nullptr.
That nullptr check is the type filter. No exceptions, no undefined behavior — just a null pointer when the types don't match.
This is the critical distinction from static_cast: static_cast trusts you at compile time. dynamic_cast verifies at runtime. In a heterogeneous container where you genuinely don't know the runtime type of a node, dynamic_cast is the correct tool — static_cast would be undefined behavior waiting to happen.
One requirement: the base class must have at least one virtual function. Without it, the compiler doesn't generate the runtime type information (RTTI) needed for dynamic_cast to work. The virtual destructor in Object satisfies this.
Operator Overloading for Custom Types — Still Somewhat Esoteric
For built-in types like int, float, and std::string, everything works out of the box — operator<< and operator== are already defined. But for a custom struct, you have to teach the compiler how to handle it.
typedef struct {
int x;
float y;
char z;
} myStruct;
// Teach std::ostream how to print myStruct
std::ostream& operator<<(std::ostream& os, const myStruct& s) {
os << s.x << " " << s.y << " " << s.z;
return os;
}
// Teach the compiler how to compare two myStructs
bool operator==(const myStruct& a, const myStruct& b) {
return a.x == b.x && a.y == b.y && a.z == b.z;
}
The operator<< overload is what allows Node<myStruct>::print() to call os << data without knowing anything about myStruct at compile time — as long as that overload exists, the template resolves correctly.
The stream-based syntax (os << s.x << " " << s.y) still feels somewhat counter-intuitive — you're chaining calls on an object that represents an output stream, returning a reference to itself at each step so the chain can continue. It works, it's idiomatic C++, but it takes some time before it stops feeling like incantation.
The operator== overload is what allows dynamic_cast plus value comparison to work in searchNodeInList. Without it, typedNode->data == value wouldn't compile for custom types.
The requirement is clear: any type you want to store in dllist must implement both. This is enforced at compile time — if you try to store a type that doesn't have them, the compiler tells you exactly which operator is missing.
Memory Management — Clearer Than Its Reputation
Manual memory management in C++ has a reputation for being treacherous. In practice, for a data structure with a clear ownership model, it's straightforward — as long as you follow one rule: whoever allocates, deallocates.
Insertion:
template <typename T>
void dlList::listAppend(T value) {
Node<T>* newNode = new Node<T>(value); // heap allocation
if (head == nullptr) {
head = tail = newNode;
} else {
newNode->prev = tail;
tail->next = newNode;
tail = newNode;
}
}
Deletion of a single node:
void dlList::deleteNode(Object* node) {
if (node->prev) node->prev->next = node->next;
else head = node->next;
if (node->next) node->next->prev = node->prev;
else tail = node->prev;
delete node; // heap deallocation
}
Destructor — cleans up everything:
dlList::~dlList() {
Object* current = head;
while (current != nullptr) {
Object* next = current->next;
delete current;
current = next;
}
}
The key detail in the destructor: save current->next before deleting current. After delete current, that memory is gone — accessing current->next afterward is undefined behavior. One line of discipline prevents the entire class of use-after-free errors.
delete on an Object* that points to a Node<T> calls the correct destructor because ~Object() is virtual. Without the virtual destructor, delete on a base pointer would only call the base destructor — leaking whatever the derived class allocated. This is another reason the virtual destructor in Object is not optional.
What This Exercise Actually Taught Me
Building something redundant — std::list and std::variant already cover this problem more efficiently — turned out to be more instructive than using the standard library version would have been.
The standard library hides the machinery. Building it yourself forces you to confront exactly why each piece exists:
- The polymorphic base exists because templates alone can't provide runtime type erasure
-
dynamic_castexists because downcasting without runtime verification is unsafe by definition - The virtual destructor exists because
deleteon a base pointer without it is undefined behavior - Operator overloading exists because templates need the compiler to resolve operations on
T— and for custom types, you have to tell it how
None of this is new knowledge in the sense that it's in every C++ book. But there's a difference between reading about it and building something where removing any one of these pieces breaks the entire structure in a specific and instructive way.
The Code
- GitHub: https://github.com/AlexRosito67/heterogeneous-double-linked-list
- Pure C++17, no dependencies, CMake build
- Intended as a learning reference, not a production library
If this was useful, there's a Buy Me a Coffee link on the GitHub page.
Alex Rosito — self-taught electronics engineer and C++ developer. ATtiny85 · ESP32 · KiCad · C++
Top comments (0)