If you haven't read the Singly Linked List notes, read those first.
Simple Doubly Linked Lists video (11 minutes) (Spring 2021) (Overview of the idea and implementation of push_back and iterator)
By adding another pointer to the LinkedListNode struct, the Singly-Linked List data type can be enhanced, to a Doubly-Linked List. The new pointer points to the previous Node in a List. Nodes now have access to both the previous, and next, Node in the List.
With the extra pointer, inserting and deleting nodes is a bit more complicated. This uses more space but allows us to go from a node to the next or previous node. In other words, iterators can be both incremented and decremented.
A second pointer is added, pointing to the previous Node in a list. Each node in a Doubly-Linked List now has 2 pointers, or links, hence "Doubly-Linked". The constructor is updated, to initialize both pointers to nullptr.
template <typename T>
struct LinkedListNode {
T value;
LinkedListNode<T> *prev;
LinkedListNode<T> *next;
LinkedListNode(const T& value) : value(value), prev(nullptr), next(nullptr) {}
};
The pop_front() function removes the Node at the head of a List. To account for the extra prev pointer that Nodes in a Doubly-Linked List have, some extra code is necessary.
The head->prev pointer is similar to the tail->next pointer. A doubly-linked list is symmetrical, so just as tail has nothing AFTER it, head has nothing BEFORE it.
To ensure that the new head has an appropriate prev pointer, pointing to nothing, we make the assignment head->next->prev = nullptr.
void pop_front() {
// Let's assume head != nullptr
// TODO: Subclass std::exception and throw an exception with a proper error message.
if (head == nullptr) {
throw std::exception();
}
LinkedListNode<T> *old_head = head;
if (head->next != nullptr) {
head->next->prev = nullptr;
}
head = head->next;
delete old_head;
}
The push_back() function adds a Node to the end of a List, after the current tail. Code for push_back in a Singly-Linked List was already making the assignment tail->next = new_node. Now that new_node has a prev pointer, we need to assign that to the Node in front of our newly inserted node. This assignment is: new_node->prev = tail.
void push_back(const T& value) {
LinkedListNode<T> *new_node = new LinkedListNode<T>(value);
if (empty()) {
head = tail = new_node;
} else {
new_node->prev = tail;
tail->next = new_node;
tail = new_node;
}
}
Now that nodes have a prev pointer, and "know about the node in front of them", iterators can go both forwards (incrementing, e.g. ++it) through the List, and backwards (decrementing, e.g. --it) through the list.
The -- operator, to decrement, is very similar to the ++ operator, to increment. Instead of advancing to a Node's next pointer, cur = cur->next, it advances to a node's previous pointer, cur = cur->prev.
Iterator& operator--() {
cur = cur->prev;
return *this;
}
Forwards iteration through a List starts at the head of a list, with the begin() Iterator, and increments until it is equal to an Iterator location AFTER the tail of the list, or end(). This covers the entire list, forwards, from head to tail.
Iterator begin() {
return Iterator(head);
}
Iterator end() {
return Iterator(nullptr);
}
for (auto it = someList.begin(); it != someList.end(); ++it) {
cout << *it << endl;
}
Backwards iteration is similar but opposite: we need an Iterator at the tail of the list, or tail_iterator(), and also an Iterator location before the head of the list, or before_begin_iterator().
This will enable us to iterate backward, starting at the tail, and ending when our decremented iterator is equal to a location one place before the head, which covers the entire list, backwards, from tail to head.
Iterator tail_iterator() {
return Iterator(tail);
}
Iterator before_begin_iterator() {
return Iterator(nullptr);
}
for (auto it = someList.tail_iterator(); it != someList.before_begin_iterator(); --it) {
cout << *it << endl;
}
Here's the complete code incorporating everything we've just covered:
#include <exception>
template <typename T>
struct LinkedListNode {
T value;
LinkedListNode<T> *prev;
LinkedListNode<T> *next;
LinkedListNode(const T& value) : value(value), prev(nullptr), next(nullptr) {}
};
template <typename T>
class LinkedList {
LinkedListNode<T> *head, *tail;
class Iterator {
LinkedListNode<T> *cur;
public:
Iterator(LinkedListNode<T> * cur) : cur(cur) {}
// Check for equality (inequality)
bool operator==(const Iterator& other) {
return cur == other.cur;
}
bool operator!=(const Iterator& other) {
return !(*this == other);
}
// Increment (e.g. --it)
Iterator& operator--() {
cur = cur->prev;
return *this;
}
// Increment (e.g. ++it)
Iterator& operator++() {
cur = cur->next;
return *this;
}
// Dereference (e.g. *it)
T& operator*() {
return cur->value;
}
friend LinkedList;
};
public:
LinkedList() : head(nullptr), tail(nullptr) {}
~LinkedList() {
for(LinkedListNode<T> *cur = head, *next; cur != nullptr; cur = next) {
next = cur->next;
delete cur;
}
}
void pop_front() {
// Let's assume head != nullptr
// TODO: Subclass std::exception and throw an exception with a proper error message.
if (head == nullptr) {
throw std::exception();
}
LinkedListNode<T> *old_head = head;
if (head->next != nullptr) {
head->next->prev = nullptr;
}
head = head->next;
delete old_head;
}
void push_back(const T& value) {
LinkedListNode<T> *new_node = new LinkedListNode<T>(value);
if (empty()) {
head = tail = new_node;
} else {
new_node->prev = tail;
tail->next = new_node;
tail = new_node;
}
}
Iterator begin() {
return Iterator(head);
}
Iterator end() {
return Iterator(nullptr);
}
Iterator tail_iterator() {
return Iterator(tail);
}
Iterator before_begin_iterator() {
return Iterator(nullptr);
}
};
Thanks to Brian Foster for typing up the rough draft of these notes based on the lecture video.