Doubly-linked list¶

Let us implement a set of integers as a doubly-linked list in which the elements are stored in ascending order. Also, if you attempt to add an integer that is already in the set, the addition fails (this means that each integer can be in the set only once).

For example, a set consisting of the elements 2, 5, 6, and 10, looks like this:

In the illustration above, shared_ptr pointers are depicted as white circles, and normal pointers as black circles.

In the program code, the member variable pointing to the first element of the list as well as the field in each element that points to the next element are implemented with the type shared_ptr. The reason is that this way, you do not have to deallocate the elements of the list with delete.

Then why has it been smart to implement the member variable pointing to the last element and the field pointing to the previous element in the list as a normal pointer?

Examine the example program that you can find in the directory examples/09/two_way_list. The implementation of the list is in the files two_way_list.hh and two_way_list.cpp.

The code is quite long, and it is not reasonable to go through it line by line here. The functions dealing with addition and deletion have comments on most of their important parts, which means that you are able to study them by yourself. However, here are some overall notions about the implementation.

It has been necessary to implement one of the link fields (i.e. pointers) in the list elements as shared_ptr, and one as a normal pointer, because of the following reasons.
- By using shared_ptr, the programmer does not have to remember to deallocate dynamic memory.
- On the other hand, if both of the pointers in the list element were shared_ptr-type, the memory would never be deallocated, because consequent elements would point to each other.
  
  Overall, this is the weakness of shared_ptr: Using it alone, you cannot implement structures that include pointer loops (A points to B and B points to A, or a longer chain).
- Then again, the member variable pointing to the last element of the list is a normal pointer, because when you remove the last element (lines 103-104 in two_way_list.cpp) from a non-empty list, that member variable must be set to point to the originally second-to-last element (i.e. the previous element of the element under removal):
```
last_ = last_->prev;
```
  If last_ were not a normal pointer, we would end up in a situation where we would have to assign a normal pointer into a shared_ptr pointer somewhere else than at initialization. This is dangerous, and almost always leads to problems.
Every time you need to handle shared_ptr-type pointers in the same expression as normal pointers, using the method get, you can get the memory address object that shared_ptr is pointing to as a normal pointer. The value you receive can be assigned into a normal pointer variable, and you can compare it with a normal pointer.

You must not deallocate the normal pointer you receive from the method get with delete, because that will mess up the internal log of shared_ptr.
It is worth noting that with adding as well as with removing, we had to examine several very special cases which we talked about at the end of the material section 8.4.2.
Every time we handle a pointer structure that is even a little bit more complicated than a singly-linked list, we almost always end up with expressions of the following form:
```
a->b->c
```
In other words, the operator -> must be written several times in the same expression.

In fact, there is nothing odd about it. The C++ rules on the order of operation dictate that the expression is interpreted from left to right.

If it will make this easier, you can think of replacing the arrow operator with the text: ”pointing to a field of a struct called”. The example you just saw would be interpreted as: the value of a, pointing to a field of a struct called b, pointing to a field of a struct called c.