Out4Mind Your multi-thematic blog
In this article I’m going to show you an example with an implementation of a doubly linked list using class templates in C++.
For a better understanding of this article, the reader should already have some notions of lists in C++ and class templates.
– For an introduction to lists in C++ and singly linked lists, please read the article “Singly linked lists in C++“.
– For an introduction to doubly linked lists, please read the article “Doubly linked lists in C++“.
– If you need to review any question about class templates in C++, you can also read this introductory article: “Class template in C++“.
Classes to manage lists and similar structures already exist in the STL (Standard Template Library) of C++. However, for students or beginners, it is important to understand how these classes work. Therefore, to know how to implement such classes is a good starting point for a better understanding of this subject.
We are going to see a simple implementation that, although it won’t be the same as the STL’s implementations, would allows you to understand how these lists work with class templates and, you can even use these classes in your own projects. It is also important to notice that, because we are using class templates, we can have any data type in the nodes. So, we can’t make an implementation that will handle data in such a direct way as we saw in previous examples. There will be some extra code when we using these classes.
So, for this example, we will have 3 classes:
- Class “DNode” – This class will define a node for a doubly linked list
- Class “DList” – This class will manage a doubly linked list
- Class “Iterator” – This class will allow us to iterate the list in both ways
Once again, I’m going to ignore “includes” and other instructions. In the end, you’ll find a link to download the complete code with comments.
Let’s then start with the code for the class “DNode” that, because it’s a class template, it will be fully implemented in a header file (“.h“):
template <class T>
class DNode {
public:
DNode(const T &e = T(), DNode *n = NULL, DNode *p = NULL) : element(e), next(n), previous(p) {}
~DNode() {}
T element;
DNode *next;
DNode *previous;
};
In line 4, we declare a constructor that, by default, will create a “double” node with an element of type “T” (generic), a pointer for the next node set to NULL and a pointer for the previous node, also set to NULL. We can pass, in the constructor, one existing element and the respective pointers “next” and “previous”. In line 6, we declare an element of type T for the node and, in lines 7 and 8 we will have the pointers for the next and previous nodes, respectively.
Before we go to the list, let’s see the iterator first:
template <class T>
class Iterator {
private:
DNode<T> *actualNode;
public:
Iterator(DNode<T> *node = NULL) : actualNode(node) {}
~Iterator() {
if (actualNode==NULL) {
actualNode = NULL;
}
}
DNode<T> *nextNode() {
if (actualNode==NULL) {
return NULL;
}
actualNode = actualNode->next;
return actualNode;
}
DNode<T> *previousNode() {
if (actualNode==NULL) {
return NULL;
}
actualNode = actualNode->previous;
return actualNode;
}
};
In line 4, we have a private member that will be a pointer for the actual node of the iterator. In line 6, we have a constructor that shall receive one of the nodes of the list. By default, the actual node will be set to NULL but that will render the iterator useless. In line 12, we declare a method called “nextNode” that will return NULL if we already iterated the last node. Otherwise, with will advance to the next node and returns that node. In a similar way, in line 19, we have the method “previousNode” that will return NULL if we already iterated the first node (in backwards). Otherwise, it will recede for the previous node and returns it.
Now, for the code of the class “DList“, in file “DList.h”, due to its size, I’m going to split it showing you the methods that will be available.
So, let’s start with the private members for the head and tail.
template <class T>
class DList {
private:
DNode<T> *head;
DNode<T> *tail;
Notice that, both head and tail will be of type “DNode” for a generic type T.
Regarding the constructor and destructor:
public:
DList() {
head = new DNode<T>();
tail = new DNode<T>();
}
~DList() {
clear();
delete head;
delete tail;
}
We can see that, in the constructor (line 2) we are declaring both the head and the tail as nodes! This means that we will have the first element of the list being pointed by “head->next” and the last element of the list by “tail->previous“. Notice that we are using an empty constructor of “DNode”, so we will have these pointers set to NULL (the list will be empty).
In the destructor, in line 6, we need to clear the list to release any existing nodes from memory and we also need to release the head and the tail.
Let’s now see the other methods one by one:
– isEmpty()
bool isEmpty() { return (head->next == NULL); }
This method will return “true” if the list is empty. It simply returns the result of the comparison “head->next == NULL” that, to be true, tells the list is empty.
– insertFirst(T)
void insertFirst(T &e) {
if (isEmpty()) {
DNode<T> *newNode = new DNode<T>(e);
head->next = newNode;
tail->previous = newNode;
}
else {
DNode<T> *actualFirst = head->next;
DNode<T> *newNode = new DNode<T>(e, actualFirst);
actualFirst->previous = newNode;
head->next = newNode;
}
}
This method inserts an element, passed as a parameter, at the head of the list. Notice that we shall test if the list is empty (line 2) and, if it’s the case, we need to create a new node with just the element to insert (line 3), because we know that, by default, the pointers “next” and “previous” will be set to NULL. And that’s what we want to define a first element for the list. Next, in line 4, we change the pointer “next” of the head to point to the new node, that will become the first of the list and, in line 5, we also change the pointer “previous” of the tail to point to the new node, because this will also be the last one.
If the list is not empty, in the “else” block in line 7, we will get a pointer for the actual first node of the list (line 8) and a pointer for the new node with the new element and the pointer of the actual first node, that will become the second one (line 9). Notice that, in the constructor for the new node, we are not passing the pointer for the “previous” node because it will be set to NULL by default. And that’s what we need because we are inserting a new first node (insert at the head). Next, we shall change the pointer “previous” of the actual first node to point to the new first node (line 10). Finally, in line 11, the pointer “next” of the head will now point to the new node, making it the new first node in the list.
– insertLast(T)
void insertLast(T &e) {
if (isEmpty()) {
DNode<T> *newNode = new DNode<T>(e);
head->next = newNode;
tail->previous = newNode;
}
else {
DNode<T> *actualLast = tail->previous;
DNode<T> *newNode = new DNode<T>(e, NULL, actualLast);
actualLast->next = newNode;
tail->previous = newNode;
}
}
Similar to the previous method, this one will insert an element, passed as a parameter, at the tail of the list. Notice once more that in line 2 we test if the list is empty and, if it is the case, we apply the same code we saw in the method “insertFirst”, because we are inserting a first element in the list.
Otherwise, on the “else” block in line 7, we will now get a pointer for the actual last node of the list (line 8) and we declare a pointer for the new node (line 9). This time, in the constructor, we send the new element, NULL for the pointer “next” of this new node (since it will become the new last node – insert at tail) and for its pointer “previous” the pointer of the actual last node, that will become the penultimate node. This time, in line 10, we change the pointer “next” of the actual last node to point to the new node. Finally, in line 11, the pointer “previous” of the tail will now point for this new last node.
– insertBefore(DNode<T> *, T)
bool insertBefore(DNode<T> *ref, T &e) {
if (isEmpty()) {
return false;
}
DNode<T> *searchRef = head->next;
while (searchRef!=NULL) {
if (searchRef==ref) {
break;
}
searchRef = searchRef->next;
}
if (searchRef==NULL) {
return false;
}
else {
DNode<T> *beforeRef = searchRef->previous;
DNode<T> *newNode = new DNode<T>(e, searchRef, beforeRef);
if (beforeRef==NULL) {
head->next = newNode;
}
else {
beforeRef->next = newNode;
}
searchRef->previous = newNode;
return true;
}
}
In this method, we want to insert a new element before a given node “ref”, that will be a pointer to a node “reference” node that we will be searched in the list. This method will return “true” if the element was successfully inserted, or “false” if that “reference” node does not exist in the list or if the list is empty. But, supposedly, if we have a node from the list, the list shouldn’t be empty. But because we can also define any other node, we shall test if the list is empty (line 2) and search if that node exists.
So, in line 5, we declare a pointer to search that “reference” node and, in line 6, we perform a loop to search for it. If we find that node, we exit the loop with the break statement in line 8. However, the loop can reach the end without having found that reference node. Se we need to test, in line 12, if the pointer used in the search is NULL. In case it is, it means that the reference node was not found and the method returns “false”.
Otherwise, we have the “else” block in line 15. Notice that, at this moment, we have the pointer “searchRef” with the same address of the pointer for the “reference” and this one is the node that is after the position where we want to insert de new node. So, we now need to declare a pointer for the node that is prior to the reference node (line 16), that will be before the new node we want to insert.
Now, in line 17, and because we are doing a possible insertion at the middle of the list, we declare a pointer for the new node with the new element, the pointer for the reference node (that will be after the new node) and the pointer of “beforeRef” (that will be the node that will be prior to the new node). An important note! If the “reference” node is the first node, we will have an insertion at the head of the list and the pointer “beforeRef” will be NULL! In this case, when we declare the new node, its pointer “previous” will automatically be set to NULL! But we also have to test this case, in line 18, and perform an insertion at the head, changing its pointer “next” for the new node (line 19). Otherwise, the pointer “beforeRef” is really pointing to a node will be prior to the new node e we shall change its pointer “next” to the new node. Finally, in line 24, we change the pointer “previous” of the reference node to point to the new node and we will return “true”, since the node was inserted and we have the list’s integrity guaranteed.
– insertAfter(DNode<T> *, T)
bool insertAfter(DNode<T> *ref, T &e) {
if (isEmpty()) {
return false;
}
DNode<T> *searchRef = head->next;
while (searchRef!=NULL) {
if (searchRef==ref) {
break;
}
searchRef = searchRef->next;
}
if (searchRef==NULL) {
return false;
}
else {
DNode<T> *afterRef = searchRef->next;
DNode<T> *newNode = new DNode<T>(e, afterRef, searchRef);
if (afterRef==NULL) {
tail->previous = newNode;
}
else {
afterRef->previous = newNode;
}
searchRef->next = newNode;
return true;
}
}
In this method, the main difference is that we now want to insert a new node after the “reference” node. I’m not going to detail this case because is almost equal to the previous case. The difference is in the pointers, that in this case, the “reference” node will be the one that will be prior the new node and we will declare a pointer “afterRef” (line 16) that will point to the node that will be after the new node. Because we may be at the end of the list, in line 18, we also need to test if this “afterRef” is NULL and perform an insertion at the tail if it is.
For more informations, read the comments in the complete source code. You’ll find the download link at the end of this article.
– remove(DNode<T> *)
bool remove(DNode<T> *r) {
if (isEmpty()) {
return false;;
}
DNode<T> *removeNode = tail->previous;
while (removeNode!=NULL) {
if (removeNode==r) {
break;
}
removeNode = removeNode->previous;
}
if (removeNode==NULL) {
return false;
}
else {
DNode<T> *afterRemove = removeNode->next;
DNode<T> *beforeRemove = removeNode->previous;
if (afterRemove==NULL) {
tail->previous = beforeRemove;
}
else {
afterRemove->previous = beforeRemove;
}
if (beforeRemove==NULL) {
head->next = afterRemove;
}
else {
beforeRemove->next = afterRemove;
}
delete removeNode;
return true;
}
}
This method is used to remove a specified node passed as a parameter. The node’s removal can be performed at the head, at the tail or at the middle of the list. It will return “true” if the node was successfully removed or “false” if the list is empty or the given node was not found. Now, we should test if the list is empty (line 2) and search the node in the “while” loop (line 6). For that, in line 5, we declare the pointer “removeNode” to search for the node from the head of the list. When the node is found, the break statement in line 8 will interrupt and exit the loop.
Once again, it is supposed that the node exists, but since we can declare any other node, we check if the pointer “removeNode” is NULL in line 12. If it is, it means that the node was not found and we will return “false”. Otherwise, we enter the else block in line 15.
Now, we will declare 2 pointers! In line 16, we declare a pointer for the node that is after the node we want to remove (“afterRemove”) and, in line 17, another pointer for the node that is before the node we want to remove (“beforeRemove”).
However, we don’t know where the node to remove is and we can be removing at the end or at the tail of the list. So, in line 18 we check if the pointer “afterRemove” is NULL. If it is, that means we are removing the last node from the list and we are performing a removal at the tail! In this case, we need to change the tail‘s pointer “previous” to point to the node prior to the one we want to remove. If it is not the last node, we will change the pointer “previous” of “afterRemove” to the node prior to the one we want to remove. Now, in line 24, we also need to test if we are at the first node of the list by checking if the pointer “beforeRemove” is NULL. If it is, we are performing a removal at the head and we need to change the head’s pointer “next” to point to the node “afterRemove”. If it is not the first node, then we change the pointer “next” of “beforeRemove” to point to “afterRemove”.
Notice that, if both pointers – “afterRemove” and “beforeRemove” – are set to NULL, we are removing the only existing element from the list! In this case, we will get both pointers “next” (on the head) and “previous” (on the tail) set to NULL which means the list will become empty!
Finally, we have all set to release the node we want to remove from memory with the delete statement in line 30 and we will return “true”.
– clear()
void clear() {
int counter = 0;
while (tail->previous!=NULL) {
DNode<T> *remove = tail->previous;
tail->previous = remove->previous;
delete remove;
counter++;
}
std::cout << "Released " << counter << " nodes from memory" << std::endl;
}
This is a very simple method to remove all nodes from the list. This method is called from the destructor but it can also be called by the code, in case we want to clear the entire list. In the previous examples we saw this process from the head, so in this one I will remove the nodes from the tail (line 3). In this loop, we declare a pointer “remove” to point to the last node of the list (line 4) and we move the tail to point to the its prior node (line 5). Then we delete it in line 6. This loop ends after deleting the last element, when the tail’s pointer “previous” becomes NULL.
Normally, classes don’t write anything in the output but, to make easier to the reader to understand the nodes that were released, a counter was implemented and its value will be displayed at the end of this method, telling how many nodes were released from memory.
– getIteratorAtHead()
Iterator<T> *getIteratorAtHead() {
Iterator<T> *i = new Iterator<T>(head);
return i;
}
This method will just return a pointer to an iterator initiated at the head of the list.
– getIteratorAtTail()
Iterator<T> *getIteratorAtTail() {
Iterator<T> *i = new Iterator<T>(tail);
return i;
}
This method will just return a pointer to an iterator initiated at the tail of the list.
And that’s all for the classes that will handle our doubly linked list with class templates.
In the second part of this article, we will see some examples on how to use these classes.
– Doubly linked list with class templates (Part II)
Source code (UTF-8; OS X / UNIX):
