Home > Technology > Computer Science > Programming > C++ > Singly linked lists in C++ (Part III)

Singly linked lists in C++ (Part III)

 In the first and second parts of this article, we saw the definition of singly linked lists, methods for inserting, removing and listing nodes and one example with a list with nodes using a “struct” to define each node. Now, we are going to implement a singly linked list with classes and with some different approaches from the previous examples, regarding the management of nodes. In the end, you can find a link to download all the files described here with comments. In the sections of code I’ll be posting here, I’ll be skipping the “includes“.

On this implementation, the nodes will be inserted in an ordered way and duplicated values won’t be allowed.

We will find 3 classes:

  • Node
  • List
  • Iterator

Class “Node” will be the smaller and easiest one and it’ll be defined just on the header file (in “Node.h”). Let’s see its definition:

class Node {
public:
    Node(const int v = 0, Node *node = NULL) : value(v), next(node) {}
    ~Node() {}
    int value;
    Node *next;
};

In the class’ constructor (line 3), we can pass as parameters, the value for the new node and a pointer for the next node. By default, the value will be zero and the pointer for the next node will be set to NULL.

Let’s now see the definition of the class “List” (in “List.h”):

class List {
private:
    Node *head;
public:
    List();
    ~List();
    bool isEmpty();
    bool insert(int);
    bool remove(int);
    void clear();
    Iterator *getIterator();
};

Notice that we make here a reference to a class “Iterator” that will be used to iterate the nodes. Also notice that the head is declared as “private”, so we can only have access the nodes using the iterator, as we will see later.

We can find the following functions and methods for this class:

  • isEmpty() – returns “true” if the list doesn’t have any nodes (empty list) or “false” if it does.
  • insert(int) – Inserts a node with an integer number in the list, in an ordered way. It will return “true” if the node was successfully inserted or “false” it the number is already stored in the list.
  • remove(int) – Removes a node that contains the integer number that was passed in the parameter. It will return “true” if the value was successfully removed or “false” if the value was not found in the list or if the list is empty.
  • clear() – Removes all the nodes in the list.
  • getIterator() – Returns an iterator so we can access the nodes of the list, starting by the node pointed by the head (first node).

Implementation of the classe(in “List.cpp”):

List::List() {
    head = new Node();
}

List::~List() {
    if (!isEmpty()) {
        clear();
    }
    delete head;
}

bool List::isEmpty() {
    return (head->next==NULL);
}

bool List::insert(int v) {
    Node *search = head;
    while (search->next!=NULL) {
        Node *test = search->next;
        if (test->value==v) {
            return false;
        }
        else {
            if (test->value > v) {
                break;
            }
        }
        search = search->next;
    }
    Node *newNode = new Node(v, search->next);
    search->next = newNode;
    return true;
}

bool List::remove(int v) {
    if (isEmpty()) {
        return false;
    }
    Node *search = head;
    while (search->next!=NULL) {
        Node *test = search->next;
        if (test->value==v) {
            search->next = test->next;
            delete test;
            return true;
        }
        search = search->next;
    }
    return false;
}

void List::clear() {
    while (head->next!=NULL) {
        Node *remove = head->next;
        head->next = remove->next;
        std::cout << "Clearing node with the value: " << remove->value << std::endl;
        delete remove;
    }
}

Iterator *List::getIterator() {
    Iterator *i = new Iterator(head);
    return i;
}



Let’s now see some relevant considerations and some differences from the previous examples:

  • Notice that, in the class’ constructor, we define the head as a node that, by default, will have its value with zero and the pointer for the next node set to NULL (line 2). On the previous implementations (parts 1 and 2 of this  article), the head was defined as a direct pointer to the first node. Now, it will be its “next” pointer that will be pointing for the first node. This way, we can simplify the methods for inserting and removing nodes, because we won’t need to test if these operations are being made at the head of the list, once the head will always be seen as a hypothetical “first” node, whose value will always be ignored.
  • A detail of the destructor of the class (line 5): Instead of using a recursive function, we will now use a different way to clear all the nodes from the list as we will see next. Because the head was declared as an object of the class “Node”, we will have to destroy it with the “delete” statement (line 9).
  • In order to test if the list is empty, we won’t be testing if the head is pointing to NULL (as we did before), but by testing if its “next” pointer is NULL (line 13).
  • As it was already said, to insert a new node we will just need to implement the code as the insertion was being made on any position within the list. We have to test if the value is already stored in the list (line 20), returning “false” if it is, and search for a node whose value is greater than the one we want to insert (line 24), exiting the loop if we find one. In the end, on line 30, the new node will be inserted before the node that has a greater value or at the tail, in case the new value is greater than any existing value on the list (the “while” loop will end without having found any greater value). This insertion process is very similar to the one we saw in the first part of this article.
  • To remove a node, we do it as if we were removing a node on any position within the list, including the tail, where we will be always testing the node ahead (line 41), as we saw in the second part of this article.
  • To clear the list, instead of using a recursive function, we will make successive removals at the head (using the “next” pointer of the “head node” – line 54) until the list becomes empty (“while” loop in line 53). The “cout” statement, in line 56, is only there to help the reader to understand how the nodes are being removed.
  • Finally, we have the function to get the list’s iterator, that will return an iterator initiated with the “head node” (line 62). We will going to see this class right below.

Definition of the class “Iterador” (in “Iterator.h”):

class Iterator {
private:
    Node *node;
public:
    Iterator(Node *node);
    ~Iterator();
    Node *getNode();
};

Here we find just one function, “getNode()”, which will return the node that is being iterated.

Implementation of the class “Iterator” (in “Iterator.cpp”):

Iterator::Iterator(Node *node) {
    this->node = node;
}

Iterator::~Iterator() {}

Node *Iterator::getNode() {
    if (node==NULL) {
        return NULL;
    }
    node = node->next;
    return node;
}

Notice that in the constructor, we copy the received pointer (that will be the head, in case we are getting this iterator from the list) for the local Node object (line 2).

In function “getNode()”, we should test if the iterator has already reached the end of the list (line 8), when the node is NULL. Normally, in the case, we can implement an exception and throw it.  However, here we will just return NULL. The same will happen when we reach the end of the list. In line 11, we always advance the iterator’s node to the next node before returning it. This way, when we first iterate a list returned by the class “List”, it will move to the first node, after the head, and it will return NULL when we reach the end of the list. We can then use this iterator to list all the nodes from the list in a loop, until it returns NULL.

The following example, from the file “main.cpp”, will show how can we do it:

    Iterator *i = list->getIterator();
    Node *node;
    while ((node=i->getNode())!=NULL) {
        cout << "Value: " << node->value << endl;
    }
    delete i;



I’m not going further with the code of the file “main.cpp”, because it implementation is pretty trivial regarding to the use of the class “List”.

You can download the file “class_list.zip which contains all the class files and the file “main.cpp” with comments. The line endings are set to “OS X / UNIX”.

Notes:

  • The implementation of lists, stacks, queues and other similar structures, already exists in the C++ STL (Standard Template Library). However, for studying this subjets, it is always a nice idea that you start by implementing your own structures.
  • In this example, the list is limited to integer values. A list can be implementing to be used in a generic way by using “templates”. I’ll talk about “template classes” soon!

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

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.