Programming lesson
Building a Doubly Linked List in C++: From Queue to Stack with Iterators
Learn how to implement a templated doubly linked list in C++ that can function as both a queue and a stack. This tutorial covers node structure, enqueue, dequeue, pop, remove, and a custom iterator class with practical examples.
Understanding the Doubly Linked List
A doubly linked list is a fundamental data structure where each node contains data and two pointers: one pointing to the next node and one to the previous node. This bidirectional linking allows efficient traversal in both directions and enables the list to behave as a queue (FIFO) or a stack (LIFO) depending on where you add or remove elements.
Think of it like a playlist of songs on a music streaming app: you can go forward to the next track or backward to the previous one. In C++, implementing a templated linked list gives you the flexibility to store any data type, just like how a playlist can hold songs, podcasts, or audiobooks.
Node Structure and List Class
Each node in our list will store a data element and pointers to the next and previous nodes. We'll use a template so the list can work with any type, such as int, string, or a custom Location struct with coordinates.
template <typename T>
struct Node {
T data;
Node* next;
Node* prev;
Node(const T& val) : data(val), next(nullptr), prev(nullptr) {}
};The LinkedList class itself maintains pointers to the front (first node) and back (last node), plus a count of elements for convenience.
template <typename T>
class LinkedList {
private:
Node<T>* head;
Node<T>* tail;
int size;
public:
LinkedList() : head(nullptr), tail(nullptr), size(0) {}
// ... methods
};Queue Operations: enqueue and dequeue
To use the list as a queue, we add elements at the back (enqueue) and remove from the front (dequeue). This follows the first-in, first-out principle, like customers waiting in line at a coffee shop.
void enqueue(T element) {
Node<T>* newNode = new Node<T>(element);
if (isEmpty()) {
head = tail = newNode;
} else {
tail->next = newNode;
newNode->prev = tail;
tail = newNode;
}
size++;
}
void dequeue() {
if (isEmpty()) return;
Node<T>* temp = head;
head = head->next;
if (head) head->prev = nullptr;
else tail = nullptr;
delete temp;
size--;
}Stack Operations: push and pop
For stack behavior (last-in, first-out), we add and remove from the same end. Here we implement pop to remove from the back, but you could also push to the back. Think of it like the undo history in a text editor: the most recent action is undone first.
void pop() {
if (isEmpty()) return;
Node<T>* temp = tail;
tail = tail->prev;
if (tail) tail->next = nullptr;
else head = nullptr;
delete temp;
size--;
}Notice that enqueue and pop both operate on the back, but dequeue removes from the front. Mixing these operations changes the list's behavior.
Removing a Specific Element
The remove method deletes the first node whose data equals the given element. You must handle four cases: removing the only node, the first node, a middle node, or the last node. This is like removing a specific item from a to-do list app.
void remove(T element) {
Node<T>* current = head;
while (current) {
if (current->data == element) {
if (current == head && current == tail) {
// only node
head = tail = nullptr;
} else if (current == head) {
// first node
head = head->next;
head->prev = nullptr;
} else if (current == tail) {
// last node
tail = tail->prev;
tail->next = nullptr;
} else {
// middle node
current->prev->next = current->next;
current->next->prev = current->prev;
}
delete current;
size--;
return;
}
current = current->next;
}
}Building the Iterator Class
An iterator allows you to traverse the list without exposing its internal structure. Our nested Iterator class will support dereferencing, pre-increment, pre-decrement, and equality checks. This is similar to how you scroll through a social media feed: you can move forward (next post) or backward (previous post).
class Iterator {
private:
Node<T>* node;
public:
Iterator(Node<T>* n) : node(n) {}
T operator*() const {
return node->data;
}
Iterator& operator++() {
if (node) node = node->next;
return *this;
}
Iterator& operator--() {
if (node) node = node->prev;
return *this;
}
bool operator==(const Iterator& rhs) const {
return node == rhs.node;
}
bool operator!=(const Iterator& rhs) const {
return node != rhs.node;
}
};Note: The pre-increment and pre-decrement should handle the case where the iterator has moved past the end or before the beginning. In our implementation, end() returns an iterator with node = nullptr. So if you increment past the last node, node becomes nullptr, matching end(). Similarly, decrementing before the first node yields nullptr.
Using the Iterator
Provide begin(), tail(), and end() methods to return iterators at the start, last node, and past-the-end respectively.
Iterator begin() const {
return Iterator(head);
}
Iterator tail() const {
return Iterator(tail);
}
Iterator end() const {
return Iterator(nullptr);
}You can then iterate from front to back or back to front:
LinkedList<int> list;
list.enqueue(10);
list.enqueue(20);
list.enqueue(30);
for (auto it = list.begin(); it != list.end(); ++it) {
std::cout << *it << " ";
}
// Output: 10 20 30
for (auto it = list.tail(); it != list.end(); --it) {
std::cout << *it << " ";
}
// Output: 30 20 10Real-World Analogy: Gaming Leaderboard
Imagine a real-time gaming leaderboard for the latest battle royale tournament. Players are ranked from first to last. The leaderboard updates as new scores come in. If you think of each player as a node, you can easily insert a new high score at the front (like a stack push) or add a new player at the bottom (like a queue enqueue). Removing a player who cheated is similar to our remove method. Iterators let you scan the leaderboard forward or backward to display rankings.
Testing Your Implementation
When testing, ensure you cover edge cases:
- Empty list operations (dequeue, pop, remove, clear)
- Single element list
- Removing first, middle, last, and only node
- Iterator increment and decrement at boundaries
Use the provided test driver to verify output matches exactly. Pay attention to memory management: delete nodes in clear() and destructor to avoid leaks.
Pro tip: In C++, always remember to implement a destructor, copy constructor, and copy assignment operator (the Rule of Three) for classes that manage dynamic memory. For simplicity, this tutorial focuses on core logic, but your full solution should include them.
Conclusion
You now have a solid understanding of building a doubly linked list in C++ with queue and stack capabilities, plus a custom iterator. This project mirrors real-world scenarios in app development, gaming, and data processing. Practice by extending the list with additional methods like insert or reverse. Happy coding!