2.3.1. Basic operations on lists

Learning objectives

The class list
Insertion and deletion of elements at the beginning and at the end of a list
Iterating over the elements of a list with forall and forall_rev

The Unix™ utility program tac reads all lines from standard input and outputs them again in reversed order. How can we implement this program with the help of LEDA? We must read line for line and store every line in a linear structure, then, after having read the last line, pass through this structure in reversed order, and thus output all lines from the last one to the first one.

Which structure do we choose? We could decide in favor of a (one-dimensional) array. Therein, we can store strings (containing the lines) in a linear sequence and both iterate from the front to behind and the other way round. However, this is not a good idea. Why not? Because we do not know in advance how many lines will come! We could say now “This does not hurt us because there is the comfortable resize() in LEDA!” However, we then either would have to make a resize() for every new line, thus wasting a lot of storage and time because of internal copy operations, or we could use a doubling strategy, making a resize() only sometimes, doubling the quantity of the array with every invocation (or enlarging the array by a different constant factor). (See also Exercise 10.) This strategy, however, means additional administrative cost for our program code, making the program error-prone. (We would have to remember how many elements are actually stored in the array; in general, this number would be smaller than A.high().)

So we throw away the idea with the resize(). What we need instead is a data structure in which we can insert an arbitrary number of elements without knowing beforehand how many of them will eventually come; a structure which the number of elements already being in the structure does not play a role for in the moment of insertion. The data structure of choice here is a linear list, implemented in LEDA by the class list.

Filling and emptying lists

Here is the program. It uses a LEDA list of strings:

list<string> L;

It reads line for line into a string variable and appends this string to the beginning of the list. After this, it successively removes every string from the beginning of the list and outputs it until the list is empty again. Thus the lines are output in reversed order.

Filename: Tac.C
#include <LEDA/list.h>
#include <LEDA/string.h>
#include <iostream>

using leda::list;
using leda::string;

int main() 
{
  string s;

  list<string> L;

  while(std::cin) {
    s.read('\n'); // same as s.read_line() or s.read(cin,'\n')
    L.push(s);
  }
  
  while(!L.empty()) 
    std::cout << L.pop() << '\n';
}

With the following lines input

I was born in a cross-fire hurricane
And I howled at my ma in the driving rain,
But it's all right now, in fact, it's a gas!
But it's all right. I'm Jumpin' Jack Flash,
It's a gas! Gas! Gas!

the program outputs

 
It's a gas! Gas! Gas!
But it's all right. I'm Jumpin' Jack Flash,
But it's all right now, in fact, it's a gas!
And I howled at my ma in the driving rain,
I was born in a cross-fire hurricane

what, lyrically speaking, makes no less sense then the original order.

Lists are a container type like arrays. The type parameter (string here) must be specified at the definition.

The method

L.push(x);

appends an element with value x to the beginning of a list.

L.pop();

removes the first element of a list and returns it. pop() has as precondition that the list be not empty.

L.empty();

tests whether a list is empty.

Here we use the method read() of the class string for reading in the strings. A separator character can be passed as an argument to read (which may well be different from the line separator). It then reads all following characters from standard input up to this separator character into the string (the separator character being excluded).

[Note] Note

In the above program, the output always starts with a blank line. This is due to the fact that another line separator is read at the end, which is appended as an (empty) line of its own. This in turn is due to the input stream handling by read(). The last line separator should actually be consumed and the input stream be empty then. This misconduct is remedied as of version 4.5 of LEDA.

Appending and deleting of elements at the end of a list

Let us get to know some further simple operations on lists. The following, algorithmically tremendously advanced program stores 5 numbers in a list, then iterates over the list and deletes the numbers again. Appending and deleting happens now at the end of the list:

Filename: ListBasicOperations.C
#include <LEDA/list.h>
#include <iostream>

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

int main() 
{

  list<int> L;

  L.append(5);
  L.append(3);
  L.append(1);
  L.append(5);
  L.append(2);

  cout << "There are " << L.size() << " elements in the list:\n";

  int x;

  forall(x,L)
    cout << x << " ";
  cout << endl;

  forall_rev(x,L)
    cout << x << " ";
  cout << endl;

  cout << "The first element is " << L.head() << endl; 
  cout << "The last element is "  << L.tail() << endl; 

  while(!L.empty()) 
    cout << L.pop_back() << " ";
  
  cout << endl;
}

The program outputs the following:

There are 5 elements in the list:
5 3 1 5 2
2 5 1 3 5  
The first element is 5
The last element is 2
2 5 1 3 5

A call of

L.append(x);

appends an element with value x at the end of a list. Figure 2.11 shows the status of the list after all append() operations of the above program.

Figure 2.11. Inserting and deleting of elements at the beginning and end of a list

Inserting and deleting of elements at the beginning and end of a list

A call of

L.pop_back();

deletes the element at the end of a list and returns it.

L.size();

returns the number of elements currently in the list.

The methods

L.head();
L.tail()

return the first and the last element of the list L, respectively.

Figure 2.11 also shows that the linear lists of LEDA are doubly linked internally, so that they can be traversed as easily from the front to behind as vice-versa. Even more: They are circular as we will see in the next section. Nevertheless, there are always a definite beginning and a definite end of the list. head() and tail() return the elements standing there.

Iterating with the forall macros

The above macro

forall(x, L) { ... }

shows the typical way how the elements of a container structure are traversed in LEDA. Thereby, the values of the list L are successively assigned to the variable x from the front to behind.

The related macro

forall_rev(x, L) { ... }

traverses the container structure from behind to front. These macros also exist for many other container types. Furthermore, there are yet some other forall macros all of which we will get to know by and by.

When iterating over containers with the help of a macro, the loop skip statements break and continue may be used within this macro as usual. (What we did not do above.)




Imprint-Dataprotection