How can we access an element at an arbitrary position of a list? How can we insert an element into a list at an arbitrary position or delete it from there? Why are insertion and deletion of elements operations that can always be executed by LEDA with a constant number of steps? (Unlike when using an array, where we must shift elements to the left or to the right during an insertion or deletion operation in order to make space or to “fill a hole”, respectively.) To answer these questions, we must deal a little bit with the internal structure of LEDA lists.

Let us have a quick look at Figure 2.12. It shows again the list that was constructed by the last program.

Figure 2.12. A list with 5 integer numbers

LEDA lists are built up with the help of containers. These containers store the actual information that the data type shall hold, single integer numbers in this example. Furthermore, the structuring of the data type takes place by and in the containers; in a linear list this means the linking of the individual containers into a linear sequence.

However, we cannot access these containers directly. Rather, we can only access the contents of a container indirectly via a so-called item. An item is the address of a container and therefore comparable with an ordinary pointer of C++.

As soon as we have an item, we can access the information within the container belonging to the item via this item. These contents are also denoted as the attributes of the item. So the attributes are what is classically called a list element. We can access solely the attributes, but not the structural information that is put additionally into the containers to produce the functionality of the data type. Therefore, items make the efficiency of pointers possible, ruling out their possibilities for abuse, though. In other words, an access via an item can never mix up the internal structure of the data structure.^[14]

Many data structures of LEDA are built up according to this item-container-concept. Dictionaries (class dictionary) and priority queues (class p_queue) are further examples. In the categorization of the LEDA types these types are called item-based structured types.

The items belonging to the respective data types also form a LEDA type of its own. Items of linear lists for example form the type list_item. In the categorization of the LEDA types such objects are denoted as being of an item type. There, it is distinguished between dependent and independent item types: Dependent item types belong to containers that can occur only in a larger structure, like for example list items, whose associated containers can live only within a list. Independent item types, however, refer to containers that are viable by themselves outside a comprehensive structure. Examples of this are arbitrarily large integer numbers (class integer) and rationals (class rational), to which we will come later.

Let us finally stop this academic pre-skirmish, we want to see items in action now! Let us fill a list with the same numbers as in the previous program and then access them via items. We get an item by asking the list for it. We then can read and write the contents of a container via such an item. We can insert another container before and behind the container. Starting from this item, we reach items referring to the adjacent containers by suitable methods of the class list. Thus, items also serve to iterate over a structure.

#include <LEDA/list.h>
#include <iostream>

using leda::list;
using leda::list_item;
using std::cout;
using std::endl;


int main() 
{
  list<int> L;

  list_item it_back,it_front;

  it_front = it_back = L.push(1);
  it_back = L.insert(5, it_back, leda::after); 
  L.insert(2, it_back); // implicit leda::after
  it_front = L.insert(3, it_front, leda::before);
  L.insert(5, it_front, leda::before);


  list_item it;

  forall_items(it,L)
      cout << L[it] << " ";
  cout << endl;

  forall_rev_items(it,L)
      cout << L[it] << " ";
  cout << endl;

  it = L.first();
  L[it] = 7;

  for(it = L.first(); it != nil; it = L.succ(it))
      cout << L.contents(it) << " ";
  cout << endl;
  
  for(it = L.last(); it != nil; it = L.pred(it))
      cout << L.contents(it) << " ";
  cout << endl;
  
  int counter = 0;
  for(it = L.first(); counter < 2 * L.size(); 
      it = L.cyclic_succ(it), counter++)
      cout << L.contents(it) << " ";
  cout << endl;
}

The output of the program is

5 3 1 5 2
2 5 1 3 5
7 3 1 5 2
2 5 1 3 7
7 3 1 5 2 7 3 1 5 2

The construction of the list is performed here by explicit insertions of containers at certain positions. The first

it = L.push(x);

returns an item it that refers to the container just inserted. Starting from this item, we can insert further containers by

it = L.insert(x, it, position);

It is possible to define by specification of leda::after or leda::before as possible values of position whether the new container is inserted into the list behind or before the container belonging to the item it, respectively. If the specification is missing, it is inserted behind the corresponding container.

insert() again returns an item that refers to the container just inserted. By picking this item and using it in the next call of insert() the structure can be built up by and by. In the above example the variables it_front and it_back of the type list_item always refer to the first and the last container, respectively, during the construction phase.

After the construction of the list, its contents are accessed solely via the list item it here.

The macro

forall_items(it, L) { ... }

makes it refer to every container of the list by and by. Thereby, the respective container can be accessed. forall_items iterates over the list from the front to behind.

In contrast, the macro

forall_rev_items(it, L) { ... }

iterates from behind to the front over the list.

As soon as we have an item it, we can access the respective attribute, that is the contents of the container, by the operator [] and also modify the attribute:

L[it] = new_value;

This is the way to modify the value of list elements. Furthermore, there is also the method assign(it, val), with which the value can be set anew. In contrast to [], it does not return any reference to the attribute so that it cannot be used in concatenation.

The contents of a container can also be accessed by the method

L.contents(it);

For an item it, it returns a copy of the contents of the list container, that is a copy of the attributes belonging to the item. Here, this is the integer number stored in the respective container.

Tip

The macros forall_items and forall_rev_items should be preferred to the forall macro for iterating over a structure because no assignment with value copying to the control variable is executed, which can be a time consuming operation, depending on the type parameter of the structure! The operator [] should be used for the access in the body of the macro since contents() also makes and returns a copy.

The method

L.first();

returns an item referring to the first container of the list; correspondingly

L.last();

returns an item referring to the last container.

The methods

L.succ(it);
L.pred(it);

return an item referring to the container succeeding or preceding the container referred to by the item it, see Figure 2.13. If we already stand on the last or the first container, they return the value nil. So the type list is actually a doubly linked list, which can be traversed from the front to behind and vice-versa.^[15]

Figure 2.13. Iteration in a list with the help of items

The item it refers to a container. Starting from there the list can be traversed forward and backward by the methods pred(), succ(), cyclic_pred(), and cyclic_succ().

LEDA's lists are even circular and can be traversed circularly forward and backward by the methods

L.cyclic_succ();
L.cyclic_pred();

These methods work like succ() and pred(). However, they do not return nil when standing on the first or the last container; in this case, they return an item referring to the last and the first container, respectively. The last loop in the above program therefore runs twice around in the list, in forward direction in the circle.

A closer look at the forall macros

The statements in LEDA for iterating over container structures are put into effect by macro expansion. The macro

forall_items(it, L) { ... }

for iterating over a list, for example, is expanded by C++ into a for loop. The expansion process introduces a new variable loop_it of type list_item and initializes it with an item that refers to the first container of the list; for every loop another variable of this kind is created by the expansion process. In every iteration of the loop, the value of loop_it is assigned to it, loop_it is advanced, and the body of the loop is executed. The loop ends when it has the value nil.

The expansion process creates the following code:

for(list_item loop_it = (L).first();
    it = loop_it, loop_it = (L).succ(loop_it); it)
      { ... }

This implies an important rule: If f() is any function that returns a list, the macro should not be used in the following form:

forall_items(it, f()) { ... }

The LEDA rule “Specification of the structure to be traversed in forall-macros” says exactly this:

	Warning
	The argument in a forall macro that specifies the structure over which it is iterated should not be a function call that returns the structure, but rather an object by itself representing a structure.

Just as well, it has to be paid attention to the following:

	Warning
	The control variable x may not be defined inside the macro, for example by forall(int x, L) { ... } The macro expansion would not work any more.

The iteration macros are stable in the sense that the element that the iterator it just stands on may be deleted. This is said by the LEDA rule “Modification of objects of an item-based container type while iterating over them”. It also says the following, though:

	Warning
	An iteration with the forall macros may not add any new elements to the container. Furthermore, it may not delete any element other than the one that the iterator item stands on.