Home > Technology > Computer Science > Programming > C++ > Doubly linked list with class templates (Part II)

Doubly linked list with class templates (Part II)

In the first part of this article, we saw the class templates that will handle our doubly linked list. Now, let’s see some examples on how to use them!

In the complete source code, that you can download in the link available at the end of this article, we have two list examples. One example with a list of integer numbers and another example with a struct “Contacts” with names, phones and e-mail addresses.

Let me remember you again that, as we are using class templates, there are some operations that can’t be directly implemented in the classes because we just don’t know the data types that will be used in the nodes.

Doubly linked list with integer numbers

In this example, we create a list of integer numbers that will be stored in a descendent order. This time I won’t check for duplicated numbers, so they might exist. Therefore, you should keep in mind that, if we remove a node with a given value, if it exists in duplicate, only the first occurrence of that number will be removed.

Because we are using class templates, we will declare our list as follows:

    DList<int> *listOfInts = new DList<int>();

Let’s now take a look on how we are going to insert a number stored in a variable “v”. In this example, we will search for a value greater than the one we want to insert from the tail, so the code will behave like we were inserting the value in an ascending order.

    if (listOfInts->isEmpty()) {
        listOfInts->insertLast(v);
    }
    else {
        Iterator<int> *i = listOfInts->getIteratorAtTail();
        DNode<int> *search;
        while ((search=i->previousNode())!=NULL) {
            int s = search->element;
            if (s>v) {
                break;
            }
        }
        if (search==NULL) {
            listOfInts->insertFirst(v);
        }
        else {
            listOfInts->insertAfter(search, v);
        }
        delete i;
    }

As usual, we should test if the list is empty (line 1) and, if it is, we use the method “insertLast” to insert our very first number. We could also use the method “insertFirst”, but the goal is to have an example of both methods. If the list is not empty, the code will proceed to the code below the else block (line 4) and we will need to get an iterator initiated at the tail (line 5). Now we declare a pointer for a search node and perform a while loop in line 7, where we are going to retrieve the next node from the iterator until we get a NULL (because we are here searching from the tail, it tells we went behind the start of the list).

Inside the loop, if we find a number greater than the one we want to insert (because we are searching from the tail), we interrupt the loop with the break statement in line 10. After the loop, in line 13, if the “search” pointer is NULL it means that we didn’t find any greater number and, in this case, we will want to insert the number at the head, by using the method “insertFirst” (line 14). If a number, greater than ours, was found we will use the method “insertAfter” using the “search” node to tell the class the position where we want to insert the new number after.

As the iterator was retrieved as a pointer to a new iterator, we have to release it from memory (line 19).

Now, let’s see how to remove a given value, in a variable “v”. This time, we are going to search the value from the head:

    Iterator<int> *i = listOfInts->getIteratorAtHead();
    DNode<int> *search;
    while ((search=i->nextNode())!=NULL) {
        if (search->element==v) {
            break;
        }
    }
    if (search==NULL) {
        cout << "The value was not found or the list is empty" << endl;
    }
    else {
        if (listOfInts->remove(search)) {
            cout << "The value was successfully removed" << endl;
        }
        else {
            cout << "Operation Error" << endl;
        }
    }
    delete i;

For this case, I’m not going to test if the list is empty because, if it is, the iterator will return NULL in the first call. Let me remember you again that the class can’t directly receive a value to search for and delete it because we can have a list with any data type, including “structs” or other classes. So, in line 1, we get an iterator initiated at the head. We then declare a node for the “search” that will be used in the loop in line 3. If we find our number, we interrupt the loop in line 5.

In line 8, we test if the pointer used in the search is NULL. If it is, it means that the value was not found or the list is empty. Otherwise, we will try to remove the value by sending its node‘s pointer (line 12). The node should be removed because we are using a pointer that shall exist in the list. It it was not found here, then we have some bug in our code.

Finally, let’s see the code to display the values from our list:

    cout << endl << "Integers ordered by descending" << endl;
    Iterator<int> *i = listOfInts->getIteratorAtHead();
    DNode<int> *list;
    while ((list=i->nextNode())!=NULL) {
        cout << list->element << endl;
    }
    delete i;

Here we are listing our values from the head (line 2). The code to test if the list is empty is in the complete code you can download down below.



Doubly linked list with a structure (“struct“)

In this other example, we will have a “struct” called “Contact” with names, phones and e-mail addresses.

The struct is declared in the file “contacts.h”:

struct Contact {
    string name;
    string phone;
    string email;
};

In our program, in “contacts.cpp”, we have the list declared as:

    DList<Contact> *listOfContacts = new DList<Contact>();

Assuming that the date were already iserted by the user and a new variable “contact” (of the type “Contact” was declared, we can insert a contact in the list, ordered by name, as follows:

    if (listOfContacts->isEmpty()) {
        listOfContacts->insertFirst(contact);
    }
    else {
        Iterator<Contact> *i = listOfContacts->getIteratorAtHead();
        DNode<Contact> *search;
        while ((search=i->nextNode())!=NULL) {
            Contact c = search->element;
            if (c.name>name) {
                break;
            }
        }
        if (search==NULL) {
            listOfContacts->insertLast(contact);
        }
        else {
            listOfContacts->insertBefore(search, contact);
        }
        delete i;
    }

After testing if the list is empty (line 1), if it is we will now use the method “insertFirst” to insert the first contact in our list. Otherwise, we will have to search the list from the head (line 5) to find where we will insert that new contact, using a pointer named “search” in the while loop in line 7.

Now, notice that in line 8, we are declaring a variable of the type “Contact” with the element returned by the iterator. As we want to insert the contacts, ordered by name, if we find a name “greater” than the name we want to insert, we interrupt the loop in line 10. Similar to what we did in the list of integers, if we don’t find a name “greater” than the one we want to insert, the “search” node will be NULL (line 13) and we will insert at the end of the list with the method “insertLast”. If we find that “greater name”, we will user the method “insertBefore” to insert the new node before the “search” node.

In order to remove a contact, we can do it using the field “name”. This way, having the name we want to delete in a variable “name”, the code will be as follows:

    Contact contact;
    Iterator<Contact> *i = listOfContacts->getIteratorAtHead();
    DNode<Contact> *search;
    while ((search=i->nextNode())!=NULL) {
        contact = search->element;
        if (contact.name==name) {
            break;
        }
    }
    if (search==NULL) {
        cout << "The name was not found in your contacts list" << endl;
    }
    else {
        if (listOfContacts->remove(search)) {
            cout << "The contact was successfully removed" << endl;
        }
        else {
            cout << "Operation error" << endl;
        }
    }
    delete i;

Once again, we get the iterator initiated at the head (line 2) and perform a while loop until we reach the end of the list (line 4). If we find our name, we interrupt the loop (line 7) and, after the loop, in line 10, we check if the pointer used in the search is NULL, meaning that the name was not found in the list. If we find the name we want to remove, in line 14, we will try to remove the node containing that name. Once again, we should be able to remove the node. Otherwise, we might have an error in our code.

To list the elements of our list, we have the following code:

    cout << endl << "List of contacts" << endl;
    Iterator<Contact> *i = listOfContacts->getIteratorAtHead();
    DNode<Contact> *list;
    while ((list=i->nextNode())!=NULL) {
        cout << "Name: " << list->element.name << endl;
        cout << "Phone: " << list->element.phone << endl;
        cout << "E-Mail: " << list->element.email << endl << endl;
    }
    delete i;

So, in line 2, we get the iterator initiated at the head of the list and perform a while loop (line 4) to list all nodes until we reach the end of the list.

We can also list the elements of our list in reverse order:

    cout << endl << "List of contacts in reverse order" << endl;
    Iterator<Contact> *i = listOfContacts->getIteratorAtTail();
    DNode<Contact> *list;
    while ((list=i->previousNode())!=NULL) {
        cout << "Name: " << list->element.name << endl;
        cout << "Phone: " << list->element.phone << endl;
        cout << "E-Mail: " << list->element.email << endl << endl;
    }
    delete i;

This time, in line 2, we get the iterator initiated at the tail of the list and we perform the while loop in reverse order (from back to front – line 4) to get all the nodes until we reach the start of the list.



With this article I close this chapter regarding lists, hoping that it was useful for you. If you have any doubts or if you want more examples regarding lists, do not hesitate on using the comments section below to leave your questions and/or suggestions. Notice that there are implementations with more methods that would facilitate the operations performed in these examples, including methods for searching nodes. However, the goal was to give you an overview regarding this subject and, after you get a better understanding on these lists, the ideal is to use the STL classes from C++.

You can download the full source code in the link below. The code was written with XCode and the characters’ encoding is in UTF-8. The line endings are in OS X / Unix mode.

Follow us in the social networks and stay tuned with more news from our multi-thematic blog Out4Mind!

Source code (UTF-8 ; OS X / UNIX):

About Carlos Santos

Frequency of master studies in Electrical and Computer Engineering. Freelancer developer (also works remotely): Websites, Web Applications (JAVA and PHP), J2SE/J2EE, C/C++ and Android. Private instructor and professional trainer in computer science and electrical engineering. Teaches in classrooms and remotely using Skype and Team Viewer. Interests: Music, audio, video, science, astronomy and mythology.

Leave a Reply

Your email address will not be published and it is optional.