Linked list¶

One basic mechanism for implementing dynamic data structures is the so-called linked list.

Linked lists consist of struct-type elements, each separately allocated with the command new. In addition to the actual value stored in the list, each element includes a pointer, by which the next list element can be found. We also need a separate pointer-type variable where we store the location of the list’s first element. Sometimes, it is efficient to also have a second pointer variable to store the address of the last element in the list.

For instance, if we want to store text in a list so that each line of an email is a separate element of the list, we need the following struct-type and the ”log” pointers:

struct List_item {
    string  text_line;
    List_item*  next;
};

List_item*  first;
List_item*  last;

When you add three elements into a list like this, the result is as:

In the illustration above, we emphasized the dynamically allocated List_item structs with a grey background. Also, the value nullptr is usually depicted as ”grounding” in the illustrations.

Every time we insert a new element into the list, we use new to allocate space for the struct that includes the actual value we want to insert, as well as log data related to the implementation of this structure (that is, the pointer pointing to the next element of the list). Every time we remove an element from the list, we use the delete command to deallocate the space reserved for it.

Also, when inserting and removing elements, we have to update the pointer values so that they store the correct memory addresses.

A good way to implement list structures is hiding the abovementioned struct type and pointers pointing to the first and last elements of the list in the private part of the class, and implementing all the operations needed for handling the list as class methods.

Naturally, you are allowed to use even more complex structures (such as trees and graphs). Only the sky is the limit once you have understood the basics of handling link fields of struct type.

Task list with C++ pointers¶

Explore the project examples/08/task_list in Qt Creator. If you are also interested in executing and editing the program code, copy it under your student directory.

The project includes three files of program code:

list.hh, the public interface of the list class
main.cpp, the user of the class
list.cpp, the implementation of the list class.

The main program includes nothing particularly interesting about dynamic memory management , which is why we will review the most essential parts of the list-class next.

list.hh:

lines 12-13:

The purpose of the list is to insert new elements at the end and remove elements at the beginning. When an element is removed, its value is stored in the reference parameter removed_task.

line 17:

For the first time, we have to implement a destructor for a class. If the lifetime of a List-type object comes to an end and the list is not empty, the destructor deallocates the reserved cells in the list.

In C++, the destructor method shares its name with the class, but there is an additional tilde character at the beginning of its name. The destructor will be automatically called behind the scenes when an object comes to the end of its lifetime.

lines 20-23:

Define a struct-type that allows us to present the individual elements of the list. Because the type List_item has been defined in the private part of the class, we can only use it in the methods of the class.

lines 25-26:

The logging member variables that are supposed to store the location of the first and last elements of the list.

In this example, we keep track also of the address of the list’s last element. This is sensible if you are going to add the elements at the end of the list. Why?
list.cpp:

Constructor:

The constructor initializes both log pointer member variables with the value nullptr, which will later be interpreted to mean that there are no elements in the list (the list is empty).

Destructor:

When the List object reaches the end of its lifetime, the destructor is called automatically. It deallocates all the dynamically allocated elements (that are of the type List_item) still remaining in the list.

As the list was implemented in this example with the normal C++ pointers, deallocating the dynamic memory is the programmer’s responsibility. Therefore, if we did not have the destructor, some memory would remain allocated.

The way the destructor works is that on each round of the loop, one element is deleted at the beginning of the list, and the memory allocated to it is deallocated.

Method print:

List printing has been implemented with a ”standard mechanism” that works every time we need to go through the list’s elements from the beginning to the end.

The temporary pointer variable is set to point to the first element of the list. For as long as its value is not nullptr (why will its value eventually be nullptr?), we print the contents of the pointed element. Finally, we move the temporary pointer to point to the next element on the list.

Method add_back:

It is easiest to understand the procedure of adding an element into the list if you draw a picture animating the steps you need to take.

The basic idea is as follows. Allocate dynamically a new struct of the type List_item and save its address. Then, update all the relevant pointers so that the list is preserved in the desired form. Please note that inserting needs to be done in different ways depending on whether we want to add the first element into an empty list, or whether the list already has elements. (Why?)

Method remove_front:

In this implementation, we always remove the first element of the list, the one where first_ points to. Before removal, we must be sure that the list includes some elements. If it does not, we inform about an error (return value false).

The actual removing goes as follows. You remove the first element from the list, which means that you update the pointers to make the member variable first_ point to the next element after the element you want to remove (or to nullptr, if we removed the last element of the list).

After updating the pointers, we deallocate the memory reserved for the element we want to delete.

Please note that removing an element is done differently when it is the only element of the list to when it is not.

Method is_empty:

This method is a simple one. The list is empty if first_ is nullptr, just like it was with the constructor.

Summary¶

When implementing linked data structures, you must always keep in mind all the special situations you can encounter with data structures. In this example, inserting and removing must be done differently in different situations.

Inserting data into an empty list requires different actions to inserting into a list that is not empty. Consequently, removing the last remaining element of the list is different to removing the elements when there are several of them left.

In order for you to be successful with the most complicated list situations, it is good to pause while implementing your list and think about the situations you might have to consider:

inserting the first element into an empty list
removing the only remaining element from a list
inserting an element to the beginning of a list
removing the first element of a list
inserting an element in the middle of a list
removing an element from the middle of a list
inserting an element at the end of a list
removing an element from the end of a list.