#include <iostream>
#include <random>
/*
* A minimal doubly‑linked list node.
* This is similar to your C version, but now it is a base class.
* User-defined data types will inherit from DNode.
*/
struct DNode {
DNode* prev = nullptr;
DNode* next = nullptr;
};
/*
* A generic doubly‑linked list using sentinel head/tail nodes.
* This class manages memory for the sentinel nodes only.
* User nodes are owned by the caller (like std::list does).
*/
class DList {
public:
DList() {
// Initialize sentinel links
head.next = &tail;
tail.prev = &head;
}
bool empty() const {
return head.next == &tail;
}
// Return first real node or nullptr
DNode* front() {
return empty() ? nullptr : head.next;
}
// Return last real node or nullptr
DNode* back() {
return empty() ? nullptr : tail.prev;
}
// Insert node at front
void push_front(DNode* n) {
insert_after(&head, n);
}
// Insert node at back
void push_back(DNode* n) {
insert_before(&tail, n);
}
// Remove and return first node
DNode* pop_front() {
if (empty()) return nullptr;
return remove_node(head.next);
}
// Remove and return last node
DNode* pop_back() {
if (empty()) return nullptr;
return remove_node(tail.prev);
}
// Insert n after node r
void insert_after(DNode* r, DNode* n) {
DNode* s = r->next;
n->prev = r;
n->next = s;
r->next = n;
s->prev = n;
}
// Insert n before node r
void insert_before(DNode* r, DNode* n) {
insert_after(r->prev, n);
}
// Remove node n from list
DNode* remove_node(DNode* n) {
DNode* p = n->prev;
DNode* s = n->next;
p->next = s;
s->prev = p;
return n;
}
private:
DNode head; // sentinel head
DNode tail; // sentinel tail
};
/*
* A user-defined node that stores actual data.
* It inherits from DNode so it can be inserted into DList.
*/
struct IntNode : public DNode {
int value;
};
/*
* Print list forward
*/
void print_forward(DList& list) {
std::cout << "Forward: ";
for (DNode* n = list.front(); n != nullptr && n->next != nullptr; n = n->next) {
if (n->next == nullptr) break; // safety
IntNode* m = static_cast<IntNode*>(n);
std::cout << m->value << " ";
if (n->next->next == nullptr) break; // reached tail sentinel
}
std::cout << "\n";
}
/*
* Print list backward
*/
void print_backward(DList& list) {
std::cout << "Backward: ";
for (DNode* n = list.back(); n != nullptr && n->prev != nullptr; n = n->prev) {
IntNode* m = static_cast<IntNode*>(n);
std::cout << m->value << " ";
if (n->prev->prev == nullptr) break; // reached head sentinel
}
std::cout << "\n";
}
int main() {
// C++ random generator
std::mt19937 rng(std::random_device{}());
std::uniform_int_distribution<int> dist(0, 99);
DList list;
// Add 5 random nodes at tail
for (int i = 0; i < 5; i++) {
auto* n = new IntNode;
n->value = dist(rng); // idiomatic random
list.push_back(n);
}
std::cout << "Added 5 nodes\n";
print_forward(list);
print_backward(list);
// Insert at head
auto* h = new IntNode;
h->value = 999;
list.push_front(h);
std::cout << "Inserted 999 at head\n";
print_forward(list);
// Remove head
auto* removed = static_cast<IntNode*>(list.pop_front());
std::cout << "Removed head: " << removed->value << "\n";
delete removed;
print_forward(list);
// Remove all nodes from tail
while (!list.empty()) {
auto* n = static_cast<IntNode*>(list.pop_back());
std::cout << "Removed tail: " << n->value << "\n";
delete n;
}
}
/*
run:
Added 5 nodes
Forward: 63 30 84 88 47
Backward: 47 88 84 30 63
Inserted 999 at head
Forward: 999 63 30 84 88 47
Removed head: 999
Forward: 63 30 84 88 47
Removed tail: 47
Removed tail: 88
Removed tail: 84
Removed tail: 30
Removed tail: 63
*/
