class DoublyLinkedList {
private:
struct Node {
Node *next;
Node *prev;
DATATYPE data;
void insertAfter(Node *prev) {
next = prev->next;
this->prev = prev;
prev->next = this;
next->prev = this;
}
void remove() {
prev->next = next;
next->prev = prev;
next = this;
prev = this;
}
Node() {
next = this;
prev = this;
}
};
Node *head;
public:
DoublyLinkedList() : head() {}
~DoublyLinkedList() {
// need to destroy all nodes on destruction to prevent memory leak
while (!isEmpty()) {
pop();
}
}
// adds data to end of queue
void add(DATATYPE data) {
Node *const node = new Node();
node->data = data;
if (head) {
node->insertAfter(head->prev);
} else {
head = node;
}
}
// returns true if queue is empty
bool isEmpty() {
return !head;
}
// Retrieves and removes the head of the queue (queue mode operation). Only call when isEmpty returns false.
DATATYPE dequeue() {
Node *const node = head;
DATATYPE const data = node->data;
if (node->next != node) {
head = node->next;
node->remove();
} else {
head = 0;
}
delete node;
return data;
}
// Retrieves and removes the end of the queue (stack mode operation). Only call when isEmpty returns false.
DATATYPE pop() {
Node *const node = head->prev;
DATATYPE const data = node->data;
if (node != head) {
node->remove();
} else {
head = 0;
}
delete node;
return data;
}
}