WildMag-Archiv

Records, auch zusammengesetzte Datentypen genannt, sind im Prinzip eine Ausnahme unter den hier vorgestellten Strukturen. Ein Record dient nicht zur Speicherung vieler gleichförmiger Daten sondern zur logischen Zusammenfassung verschiedener Datentypen. Vergleichbar ist das mit einem Adressbuch: Jede einzelne Adresse setzt sich aus Name, Straße, Hausnummer, Postleitzahl und Ort zusammen, also drei Strings und zwei Nummern. Das Buch an sich besteht aber aus einer Vielzahl dieser logischen Einheiten, weshalb ich hier auch auf diesen Typ eingehe.

Ein Record fasst also zusammengehörige Daten zusammen, so dass man sie als Einheit betrachten kann:

struct Adresse
{
  string Name;
  string Straße;
  int Hausnummer;
  int PLZ;
  string Ort;
};
// Adress-Variable anlegen
Adresse MeineAdresse;
// Auf die Bestandteile zugreifen
MeineAdresse.PLZ = 52062;

Arrays sind oft die erste Datenstruktur, die man neben den elementaren Datentypen kennenlernt. Sie brauchen keinen zusätzlichen Speicherplatz für Verwaltungsinformationen, lassen sich einfach Anlegen ('new') und Löschen ('delete') und bieten den schnellstmöglichen Zugriff auf Elemente bekannter Position ('x = array[ pos ];'). Allerdings sind sie völlig unflexibel. Wer schon mal mit dem Gedanken gespielt hat, in ein Array in der Mitte etwas einzufügen, der dürfte schnell bemerkt haben, dass er dazu zum einen die bestehende Struktur vergrößern müßte, was oft einem kompletten Neuanlegen und Umkopieren gleich kommt. Aber selbst wenn man am Ende noch Platz für eventuelle Vergrößerungen gelassen hat, muss man alle Elemente von der gewünschten neuen Position an ein Feld nach hinten verschieben, um den Platz für das neue Element zu gewinnen. Abhilfe schaffen hier Listen.

Listen bestehen aus Ketten, deren einzelne Glieder zum einen die zu speichernden Datenelemente enthalten, zum anderen aber auch Verweise auf das folgende und u.U. auf das vorherige Glied:

[Daten01|Verweis]-->[Daten02|Verweis]-->[Daten03|Verweis]

Dadurch ist es relativ einfach, Elemente einzufügen, da man nur den Verweis des vorherigen Elementes auf das neue setzen muss, sowie dessen Verweis auf das folgende:

1) [Daten01|Verweis]------------------------>[Daten02|Verweis]
                        [Daten03|Verweis]

2) [Daten01|Verweis]-                      ->[Daten02|Verweis]
                     \                    /
                      ->[Daten03|Verweis]-

Das Löschen funktioniert analog, man setzt einfach den Verweis des Vorgängers des zu löschenden Elements auf dessen Nachfolger.

Diese Flexibilität erkauft man sich allerdings durch zwei Nachteile: Man kann nicht mehr direkt auf das n-te Element zugreifen, da dessen Position im Speicher nicht direkt bekannt ist. Wann immer man nicht zufällig alle Elemente von Anfang bis Ende nacheinander abarbeiten möchte, muss man sich immer vom Anfang der Kette bis zum gesuchten Element durchhangeln, was natürlich entsprechend Rechenzeit kostet. Ein anderer Nachteil ist, dass die Listendarstellung auch immer noch Speicherplatz für die Verweise braucht, was bei kleinen Datensätzen, z.B. einfachen Integer-Werten, schon zu einer Verdopplung des Bedarfs führt.

Listen machen also immer dann Sinn, wenn man zum einen die Möglichkeit braucht, Elemente problemlos einfügen und löschen zu können, zum anderen aber die Elemente bei der Verarbeitung immer in der gegebenen Reihenfolge benötigt.

Eine einfache Liste lässt sich wie folgt aufbauen:

struct Liste
{
  int Wert;
  Liste* Next;
};
Liste* MeineListe;

MeineListe ist nun ein Verweis auf das erste Listenelement. Auf diesem Verweis bauen sämtliche Listenoperationen auf. Operationen, die den Anfang der Liste betreffen, arbeiten direkt auf MeineListe, alle anderen nehmen es alS Startpunkt, um das zu modifizierende Element zu finden.

Anlegen des ersten Elements

MeineListe = new Liste;
MeineListe->Next = NULL;

Anfügen eines Elements an eine bestehende Liste

// Hilfs-Zeiger 'Element'
Liste* Element = MeineListe;
// Suche Listen-Ende
while( Element->Next != NULL )
  Element = Element->Next;
// Füge Element an
Element->Next = new Liste;
Element->Next->Next = NULL;

Löschen eines Elements aus der Mitte

// Hilfs-Zeiger 'Element'
Liste* Element = MeineListe;
// suche Vorgänger des zu löschenden Elements
while( Element->Next->Wert != GesuchterWert )
  Element = Element->Next;
// Hilfs-Zeiger 'Next'
Liste* Next = Element->Next;
// Entferne Element aus der Liste
Element->Next = Element->Next->Next;
// Entferne gelöschtes Element aus dem Speicher
delete Next;

Einfügen eines Elements in der Mitte

// Hilfs-Zeiger 'Element'
Liste* Element = MeineListe;
// suche Einfüge-Stelle (zukünfigen Vorgänger)
while( Element->Next->Wert != GesuchterWert )
  Element = Element->Next;
// Hilfs-Zeiger 'Neu'
Liste* Neu = new Liste;
// Füge Element in die Liste ein
Neu->Next = Element->Next->Next;
Element->Next = Neu;

Die weiteren denkbaren Operationen sind mit ein wenig Übung leicht selbst zu implementieren, wie immer hilft das gedankliche Durchspielen in Kombination mit Papier und Bleistift.

Um den ersten Nachteil der Listen, das aufwendige Suchen von bestimmten Elementen, zu umgehen, lassen sich diese zu Bäumen erweitern. Bäume gleichen Listen, erlauben aber Verzweigungen. Ein Element hat nun nicht immer einen Nachfolger, es können je nach Baumart auch zwei oder mehr sein. Die einfachste Sorte ist hierbei die mit maximal zwei Nachfolgern, welche dementsprechend Binärbaum genannt wird. Der Sinn ist, dass man bei jedem Element direkt weiß, ob man in der einen oder in der anderen Richtung weiter suchen muss. So kann man z.B. sagen: Links folgen nur Werte die kleiner sind als der Wert des Elements, rechts folgen die größeren.

                      [ 10 ]
                     /      \
                  [ 5 ]    [ 20 ]
                 /     \
              [ 2 ]   [ 9 ]

Bei einem geschickt aufgebauten Baum kann man so mit jedem Schritt die Anzahl der möglichen Elemente halbieren, während bei den Listen die Anzahl immer um eins verringert wurde. Die Anzahl der Schritte, um einen Baum mit 1024 Elementen zu durchsuchen ist somit maximal 10 (2¹⁰ = 1024), bei einer Liste sind es genau die 1024, was 100 mal länger dauert.

Das Arbeiten mit einem Baum gestaltet sich aber etwas anders als von Listen gewohnt. So muss man z.B. bei der gegebenen Vorschrift (links kleiner, rechts größer) nicht unbedingt in der Mitte des Baumes Elemente einfügen. Statt dessen hängt man sie einfach den Regeln folgend an's Ende. Ein möglicher Aufbau sähe so aus:

struct Knoten
{
  int Wert;
  Knoten* Links;
  Knoten* Rechts;
};
Knoten* Wurzel;

Die einzelnen Elemente eines Baumes heißen Knoten (engl: Node), wobei der Anfangsknoten Wurzel (engl: Root) genannt wird.

Hinzufügen eines Knotens

void Hinzufuegen( Knoten* knoten, int Wert )
{
  if( Wert < knoten->Wert ) // links
  {
    if( knoten->Links == NULL ) // Blatt erreicht
    {
      // neuen Knoten erzeugen
      knoten->Links = new Knoten;
      // Knoten initialisieren
      knoten = knoten->Links;
      knoten->Links = NULL;
      knoten->Rechts = NULL;
      knoten->Wert = Wert;
    }
    else
    {
      // rekursiv das passende Blatt suchen
      Hinzufuegen( knoten->Links, Wert );
    }
  }
  else // rechts
  {
    // analog zu links
  }
}

Suchen eines Knotens

bool Suchen( Knoten* knoten, int Wert )
{
  if( knoten == NULL )
  {
    // Ende erreicht, ohne den Wert zu finden
    return false;
  }
  else
  {
    if( Wert == knoten->Wert ) // Wert gefunden
    {
      return true;
    }
    else if( Wert < knoten->Wert ) // links suchen
    {
      return Suchen( knoten->Links, Wert );
    }
    else // rechts suchen
    {
      return Suchen( knoten->Rechts, Wert );
    }
  }
}

Das Löschen von Knoten gestaltet sich etwas schwieriger. Ich werde es in dieser kurzen Vorstellung nicht weiter behandeln, da es in vielen einfachen Anwendungen auch nicht erforderlich ist. Nähere Erklärungen finden sich in den Literaturhinweisen.

Stacks als solche bezeichnen nicht direkt eine Implementierung, so wie Listen, sondern ein Funktionsprinzip, welches sich auf verschiedene Weise umsetzen lässt. Auf einem Stack kann man Daten ablegen. Herunternehmen kann man immer nur das Element, welches man als letztes hinzugefügt hat. Im wirklichen Leben bietet sich das Verfahren z.B. beim Auseinandernehmen einer Playstation zwecks Einbau eines MOD-Chips an: Zuerst entfernt man den Gehäusedeckel und legt ihn beiseite. Danach entnimmt man das CD-Laufwerk, dann die metallische Abschirmung. Und in jedem Schritt fallen noch ein paar Schrauben an. Wenn man das Ding wieder zusammensetzen möchte, ist es ganz sinnvoll, das genau in umgekehrter Reihenfolge zu tun, und genau dieses Problem taucht auch ab und an in der Programmierung auf, weshalb es den Stack gibt.

Ein Stack ist am einfachsten als Array zu implementieren. Man merkt sich in einer zusätzlichen Variablen, welches das nächste freie Element des Arrays ist, und speichert dann entweder dort den neuen Wert und inkrementiert den Zähler bzw. dekrementiert ihn beim Auslesen und gibt dann den vorhandenen Wert zurück.

int Stack[1000];
int Position;
void Speichern( int Wert )
{
  Stack[ Position ] = Wert;
  Position++;
}
int Laden()
{
  Position--;
  return Stack[ Position ];
}

Natürlich bedarf es noch weiterer Abfragen um sicherzustellen, dass nicht z.B. auf einen vollen Stack ein weiteres Element abgelegt wird, aber im Prinzip reicht dieser Code für einen handelsüblichen Stack aus.

Queues sind Verwandte der Stacks, der Unterschied ist, dass man bei ihnen nur das Element abrufen kann, das als erstes gespeichert wurde. Sinn macht das beispielsweise in der Druckerwarteschlange, in die jedes Programm hinten seine Druckaufträge einreiht und der Drucker sie dann in der gegebenen Reihenfolge abarbeitet. Aber auch an allen anderen Stellen, an denen eine Ein-/Ausgabe gepuffert wird, sei es bei der Übertragung von Daten zum CD-Brenner oder den Windowsnachrichten zwischen OS und Applikation, kommen Queues zum Einsatz. Sie ermöglichen, dass Schreib- und Lesezyklen nicht synchron laufen müssen, wie es bei einer ungepufferten Übertragung der Fall wäre, da die Daten so schon mal eine gewisse Zeit im Puffer verbleiben können.

Implementieren lässt sich ein Queue ganz analog zum Stack:

int Queue[ 1000 ];
int Anfang;
int Ende;
void Speichern( int Wert )
{
  Queue[ Ende ] = Wert;
  Ende++;
}
int Laden()
{
  Anfang++;
  return Queue[ Anfang ];
}

Zu beachten ist allerdings, dass man hier noch zusätzliche Abfragen braucht, um den Queue als Ring nutzen zu können. Schließlich will man ja nicht nach 1000 Einträgen einen neuen Queue anlegen, obwohl davon schon 500 schon wieder ausgelesen wurde, also die ersten 500 Einträge wieder frei sind. Hier bietet es sich an, ein Ende %= 1000 einzufügen.

Wenn man die Implementierung einer Datenstruktur außer Acht lässt und die Sicht nur auf die Funktionalität beschränkt, erhält man einen abstrakten Datentyp. So kann man z.B. zuerst spezifizieren, was die Datenstruktur ermöglichen soll (Element hinzufügen, Element auslesen, Element suchen) und darauf das weitere Programm aufbauen. Die Implementierung kann sich dann problemlos von Version zu Version ändern, ohne dass man die Teile des Programms, die auf die Datenstruktur zugreifen, ändern muss. Dieses Konzept manifestiert sich zum einen in der traditionellen Trennung von C-Header und -Quellcode (bzw. Interface/Implementation in Pascal), zum anderen aber auch in den sogenannten Containern in C++.

Eine Spezifikation für einen Stack sähe dann z.B. so aus:

Elemente : x
Stack    : s
Element dem Stack hinzufügen : Push( s, x );
Element vom Stack holen      : x = Pop( s );
Stack initialisieren         : Init( s );

Im nächsten Schritt erstellt man dann die passenden Funktionen:

// Header [stack.h]
// benutze Elemente vom Typ INT
typedef int Element;
// der konkrete Datentyp des Stacks ist irrelevant
typedef void* Stack;
void Push( Stack s, Element x );
Element Pop( Stack s );

Bis dahin wurde noch nicht festgelegt, um was es sich bei dem Stack eigentlich handelt, nur, was er kann. Die Implementierung kann man nun analog zur oben genannten schreiben:

// Sourcecode [stack.c]
// Beschreibe das Aussehen des Stacks
struct StackStruct
{
  Element Array[ 1000 ];
  int Position;
};
void Push( Stack s, Element x )
{
  ((StackStruct*) s)->Array[ ((StackStruct*) s)->Position ] = x;
  Position++;
}

Obgleich die Technik des ADT elementar für die rein imperativen Sprachen ist, sollte jeder, der objektorientiert arbeitet, von der Verwendung dieser Art ADT absehen. Die Klasse ist das logische Äquivalent zum ADT, weshalb der Stack in C++ als solche umgesetzt werden sollte:

// Header [stack.h]
typedef int Element;
class Stack
{
 public:
  void Push( Element x );
  Element Pop();
 protected:
  Element Array;
  int Position;
}
// Sourcecode [stack.cpp]
void Stack::Push( Element x )
{
  Array[ Position ] = x;
  Position++;
}

Man sieht leicht, dass die durch die Sprache ermöglichte Zusammenfassung von Daten und Methoden eine sauberere Schreibweise ermöglicht, in der umständliches Casten praktisch überflüssig wird. Die Idee, die dahinter steckt, ist jedoch die gleiche. Auch hier kann man die Klasse nach Belieben neu implementieren, ohne dass der Rest des Programms (oder des Programmier-Teams) etwas davon mitbekommt.

Da die Umsetzung der ADT nun recht komplex ist, aber in gleichem Maße sprachspezifisch, möchte ich an dieser Stelle nicht näher darauf eingehen. C++-Programmierern sei aber geraten, sich mit den Begriffen Template und Container vertraut zu machen.

Allgemeine Sortieralgorithmen kann man grob in zwei Kategorien einteilen: Die einfachen und die fortgeschrittenen. Einfache Sortieralgorithmen sind leicht zu verstehen, in wenigen Codezeilen zu implementieren und dadurch bei kleinen Mengen (10 bis 20 Einträge) auch durchaus sinnvoll. Allerdings beträgt ihr Aufwand im Schnitt n². Das heißt, dass sich die Anzahl der Schritte, die sie benötigen, bis die Menge sortiert ist, sich für für die doppelte Anzahl Elemente vervierfacht.

Fortgeschrittenere Sortieralgorithmen sind meist etwas komplizierter, haben aber den Vorteil, dass sie bei größeren Mengen weitaus schneller sind, da sie nur einen Aufwand von n * log(n) haben, d.h. bei einer verdoppelten Anzahl Elemente benötigen sie nur wenig mehr als doppelt so viele Schritte, welche allerdings einzeln betrachtet mehr Rechenzeit benötigen als die der einfachen Verfahren. Bei einigen hundert zu sortierenden Elementen ist der Unterschied aber schon mehr als deutlich.

Zu beachten ist, dass es sich bei immer um den durchschnittlichen Aufwand handelt, also den bei einer zufälligen Menge. Ist die Menge z.B. schon praktisch sortiert und nur das letzte Element steht an der falschen Stelle, so sind einfache Verfahren oft die bessere Variante, da sie diese Eigenschaften leicht ausnutzen können. Auf der anderen Seite kann man sie genauso austricksen, in dem man die Menge z.B. absteigend sortiert, was bei einigen einfachen Verfahren zu einer weitaus längeren Laufzeit führt.

Insertionsort zählt zu den einfachen Verfahren. Hierbei unterteilt man die Menge in einen sortierten und einen unsortierten Abschnitt. Zu Anfang besteht der sortierte Abschnitt nur aus einem einzigen Element, dem ersten Element der Gesamtmenge. In jedem Schritt wird nun das erste Element aus der unsortierten Menge genommen und an die richtige Stelle im bereits sortierten Abschnitt eingefügt.

Ein Beispiel:

unsortierte Menge
[8 3 1 0 2 9 4 5]

Initialisierung
sortiert  : [8]
unsortiert: [3 1 0 2 9 4 5]

Schritte
[3 8] [1 0 2 9 4 5]
[1 3 8] [0 2 9 4 5]
[0 1 3 8] [2 9 4 5]
[0 1 2 3 8] [9 4 5]
[0 1 2 3 8 9] [4 5]
[0 1 2 3 4 8 9] [5]
[0 1 2 3 4 8 9 5]

Man sieht leicht, dass die sortierten Elemente dabei oft verschoben werden müssen, um Platz für die neu eingefügten zu machen. Um genau zu sein, muss für jedes der n Elemente im Schnitt die Hälfte der schon sortierten Elemente verschoben werden, also n/4. Zusammen ergibt das einen Aufwand von n²/4. (2500 für n=100)

Und als Quellcode:

void InsertionSort( int* Menge, int Anzahl )
{
  for( int i=0; i < Anzahl; i++ )
  {
    // wähle nächstes Element
    int Element = Menge[ i ];
    // Suche Einfüge-Position;
    for( int j=0; ( Menge[ j ] < Element ) && j < i; j++ );
    // folgende Elemente verschieben
    for( int k=i; k > j; k-- )
      Menge[ k ] = Menge[ k-1 ];
    // Element einfügen
    Menge[ j ] = Element;
  }
}

Mergesort ist ein gutes Lehrbeispiel für fortgeschrittene Sortierverfahren, da es im Gegensatz zu beispielsweise Quicksort gut nachvollziehbar ist. Bei Mergesort wird die Ausgangsmenge zunächst immer weiter rekursiv in Hälften zerteilt, bis man nur noch einzelne Elemente hat. An dieser Stelle stoppt die Rekursion, um auf dem Rückweg die einzelnen Untermengen zusammenzufügen. Dabei hat man ja jedesmal zwei Teile, die für sich sortiert sind, weshalb man immer nur die ersten Elemente der beiden Teile betrachten muss. Das kleiner übernimmt man in die sortierte Menge, entfernt sie in dem Teil, aus dem man sie entnommen hat und wiederholt das so lange, bis die beiden Teile leer sind.

Die Beispielmenge von oben wird dann so sortiert

unsortierte Menge
[8 3 1 0 2 9 4 5]

Aufteilen
[8 3 1 0 2 9 4 5]
[8 3 1 0] [2 9 4 5]
[8 3] [1 0] [2 9] [4 5]
[8] [3] [1] [0] [2] [9] [4] [5]

Zusammensetzen
[3 8] [0 1] [2 9] [4 5]
[0 1 3 8] [2 4 5 9]
[0 1 2 3 4 5 8 9]

Das Suchen ist eine sehr datenstrukturspezifische Angelegenheit. Die bereits vorgestellen Bäume sind geradezu darauf optimiert, eine effiziente Suche zu ermöglichen, die Listen hingegen lassen sich ausschließlich linear, d.h. Element für Element, durchsuchen. Dazwischen gibt es aber noch zwei weitere Varianten, die auf Arrays aufbauen.

Dieses Verfahren ist die logische Konsequenz auf der linearen Suche. In einer sortierten Menge bietet es sich an, zuerst mal das mittlere Element zu prüfen. Wenn dies größer als das gesuchte ist, kann man seine Suche direkt auf die erste Hälfte einschränken und dort wieder halbieren, so lange, bis man entweder das gewünschte Element gefunden hat oder aber der zu durchsuchende Bereich auf Null schrumpft, was bedeutet, dass das Element gar nicht vorhanden ist.

Hashing geht die Suche von einer ganz anderen Seite an. Jedem Element wird ein Schlüssel zugeordnet, anhand dessen die Position im Speicher bestimmt wird. Am einfachsten wird das an einem Beispiel deutlich: Man legt sich eine Datenbank an, die die Rückwärtssuche von den Telefonnummern des eigenen Adressbuches erlaubt, so dass man eingehende Anrufe direkt den Namen zuordnen kann. Der einfachste Ansatz wäre nun, ein Array anzulegen, was so jeder möglichen Telefonnummer einen Namen zuordnet:

GesuchterName = Namen[ Telefonnummer ];

Jetzt kann man in einem einzigen Schritt den richtigen Namen finden, langwierige Suchen werden überflüssig. Bei im Schnitt 4 Stellen Vorwahl (die führende Null kann man ja weglassen) und 6 Stellen Rufnummer wären das aber 10 Stellen oder 10 Milliarden Einträge, was selbst bei Namen, die nur ein Zeichen lang sind, 10 GB Speicher erforderte. Da man aber nur vielleicht 100 Nummern speichern möchte, braucht man einen geeigneteren Schlüssel. Die Konsequenz ist dann, z.B. nur die letzten drei Stellen der Telefonnummer zu betrachten:

GesuchterName = Namen[ Telefonnummer % 1000 ];

Jetzt braucht man nur noch ein Array mit 1000 Einträgen, hat allerdings ein Problem: Wenn mehrere Telefonnummern die gleichen drei letzten Stellen haben, landen sie auf dem gleichen Speicherplatz. Abhilfe schafft hier das sogenannte offene Hashing. Dabei nimmt man kein Array aus Namen sondern eines aus Listen. So bestimmt man zuerst über Hashing die richtige Liste und muß dann nur noch in dieser den richtigen Eintrag finden. Da man via Hashing die Suche aber schon sehr gut eingrenzen kann, ist der Aufwand, die Liste zu durchsuchen, oft gering.

Liste = NamensListen[ Telefonnummer % 1000 ];
SucheInListe( Liste, Telefonnummer );

Jetzt sollte auch klar sein, warum man am besten die letzten und nicht die ersten drei Stellen der Telefonnummer nimmt: Wenn man z.B. in Köln wohnt und die Hälfte der Einträge aus der eigenen Stadt kommen, beginnen 50 von 100 Nummern mit 221, landen also in der gleichen Liste. Nimmt man hingegen die letzten drei Stellen, erhält man eine weitaus zufälligere Verteilung, was die Listen verkürzt und die Suche beschleunigt.

Hashing steht und fällt mit dem Algorithmus, der die Schlüsselwerte berechnet. Wenn man an dieser Stelle nicht aufpasst, bleibt man leicht auf dem Niveau einer einfachen linearen Liste. Findet man aber eine Möglichkeit zur gleichmäßigen Verteilung, ist es die schnellste denkbare Suche, da man das Ergebnis nach ein, zwei Schritten erhält. Wie man nun am besten die Schlüssel berechnet hängt immer von den Ausgangsdaten ab, ein totsicheres Konzept gibt es nicht. Oft ist ein Pseudo-Zufallszahlen-Generator eine gute Ausgangsbasis:

int a = 5;
int b = 17;
int m = 23;
Liste = NamensListen[ ( a * Telefonnummer + c ) % m ];
SucheInListe( Liste, Telefonnummer );

Dabei erzielt man mit Primzahlen die besten Ergebnisse, nur sollten a und b in der gleichen Größenordnung wie m liegen. Je nachdem, wie viel Speicher man hat und wie schnell man das Ergebnis braucht, sollte man zusehen, dass m irgendwo im Bereich von n bis 3*n liegt, wenn n die Anzahl der Einträge ist. Das ist natürlich auch nur eine Faustregel, Ausprobieren wirkt Wunder.

Abschließend sei noch darauf hingewisen, dass es auch das sogenannte geschlossene Hashing gibt. Der Unterschied ist, dass man die Elemente mit dem gleichen Schlüssel nicht in lineare Listen packt sondern für ein Element, was an einer schon belegten Position gespeichert werden soll, eine Ersatzposition sucht, z.B. die nächste freie im Array.