Arrays und Listen

Inhaltsverzeichnis:

Einführung

Dieser Artikel behandelt Arrays und Listen, ihre Unterschiede, ihre Eigenschaften und die konkrete Anwendung in Delphi.

Ein Array ist eine geordnete Menge gleichartiger Datentypen. Eine Liste ist eine geordnete Menge möglicherweise verschiedener Datentypen.

Es gibt bestimmte Operationen, die mit geordneten Mengen vorgenommen werden können. Dazu gehört der Zugriff auf ein bestimmtes Element, das Suchen nach einem bestimmten Element und das Einfügen und Löschen von Elementen. Eine weitere Operation ist das Sortieren, der Sortiervorgang besteht aus einer bestimmten Menge von Lösch- und Einfügeoperationen.

Arrays

Arrays sind dadurch gekennzeichnet, daß die Elemente über einen Index angesprochen werden. Die Elemente liegen hintereinander im Speicher.

Arrays sind statisch, d.h. Arrays können ihre Größe nicht ändern. Damit haben sie eine maximale Anzahl von Elementen, die nicht überschritten werden kann. Werden weniger Elemente benutzt, dann ist der restliche Speicher verschwendet. Die maximal mögliche Größe ist vom Speicher abhängig. Die Größe des Arrays wird beim Anlegen festgelegt.

Der Zugriff auf ein bestimmtes Element kann direkt erfolgen. Bei einer Suche muß jedes Element des Arrays durchsucht werden, bis der Eintrag gefunden ist. Ist das Array entsprechend dem Suchkriterium sortiert, dann kann eine binäre Suche angewendet werden.

Beim Einfügen oder Löschen eines Elementes müssen alle nachfolgenden Elemente im Array verschoben werden.

Listen

Listen sind dadurch gekennzeichnet, das die Elemente über Zeiger miteinander verbunden werden. Die Elemente liegen an unterschiedlichen Stellen im Speicher.

Listen sind dynamisch, d.h. Listen können ihre Größe problemlos ändern. Die maximale Anzahl von Elementen ist nur vom Speicher abhängig.

Der Zugriff auf ein bestimmtes Element kann nicht direkt erfolgen. Ausgehend vom ersten Element muß die Liste bis zum gewünschten Element durchgegangen werden. Bei einer Suche muß jedes Element des Arrays durchsucht werden, bis der Eintrag gefunden ist. Eine binäre Suche kann nicht angewendet werden.

Es gibt einfach und doppelt verkettete Liste. Einfach verkettete Listen erlauben nur eine Bewegung vom ersten Element zum nächsten. Doppelt verkette Listen erlauben auch eine Bewegung in die andere Richtung.

Beim Einfügen oder Löschen eines Elementes müssen nur die Zeiger für Verkettung geändert werden.

Bei einer Liste muß für jedes Element einzeln Speicher reserviert und freigegeben werden. m * SizeOf(Pointer) + x + n * SizeOf(Element) + x

Auch wenn der Name es vermuten ließe, TList ist keine verkettete Liste, sondern die Kapselung eines Pointer-Arrays.

Eine gute Beschreibung zu verketteten Listen und die ihre Programmierung in Pascal habe ich als Teil eines Pascal Kurses im Internet gefunden, darum spare ich mir das hier.

Pointer-Arrays

Pointer-Arrays sind ein Kompromiß zwischen Arrays und Listen. Sie sind dadurch gekennzeichnet, daß die Elemente über ein Array von Pointern verwaltet werden. Die Elemente können dadurch, wie bei einem Array, über einen Index angesprochen werden. Die Elemente liegen an unterschiedlichen Stellen im Speicher.

Pointer-Arrays sind statisch, d.h. sie können ihre Größe nicht ändern. Damit haben sie eine maximale Anzahl von Elementen, die nicht überschritten werden kann. Werden weniger Elemente benutzt, dann ist der restliche Speicher verschwendet. Diese Verschwendung bezieht sich aber nur auf den Platz für einen Pointer pro Element. Die maximal mögliche Größe ist vom Speicher abhängig. Die Größe des Arrays wird beim Anlegen festgelegt.

Der Zugriff auf ein bestimmtes Element kann direkt erfolgen. Bei einer Suche muß jedes Element des Arrays durchsucht werden, bis der Eintrag gefunden ist. Ist das Pointer-Array entsprechend dem Suchkriterium sortiert, dann kann eine binäre Suche angewendet werden.

Beim Einfügen oder Löschen eines Elementes müssen alle Pointer für die nachfolgenden Elemente im Pointer-Array verschoben werden.

Gegenüberstellung

Quasidynamische Arrays

Wie man erkennen kann, leiden Arrays im wesentlichen unter der Größenbeschränkung. Es gibt eine Möglichkeit diese Beschränkung zu umgehen. Es wird ein neues Array angelegt die Elemente in das neue Array kopiert und dann das alte Array gelöscht.

Dieser Vorgang kostet natürlich Zeit und benötigt während des Kopierens doppelt so viel Speicher. Hier haben die Pointer-Arrays auch wieder entsprechende Vorteile, da nur die Pointer kopiert werden müssen, nicht die (größeren) Elemente.

Arrays in Object Pascal

In Object Pascal gibt es verschiedene Möglichkeiten mit Arrays zu arbeiten.

Konstanten-Array
Die Elemente liegen direkt im Code. Das Array und sein Inhalt können nicht verändert werden. Der Compiler erzeugt Code für die Bereichsprüfung, wenn der entsprechende Compilerschalter gesetzt ist.

const
  Bitmask: array[0..3] of Integer = ($01, $02, $04, $08);

Array-Variable
Die Elemente liegen im Stack (lokale Variable) oder im 'Datensegment' (globale Variable). Der Speicher wird automatisch reserviert und freigegeben. Die (maximale) Anzahl der Elemente muß zur Entwicklungszeit bekannt sein. Der Compiler erzeugt Code für die Bereichsprüfung, wenn der entsprechende Compilerschalter gesetzt ist.

procedure ...
var
  arr: array[0..10] of Double;

dynamisch erzeugtes Array
Die Elemente liegen im Heap. Die (maximale) Anzahl der Elemente muß erst zur Laufzeit bekannt sein. Der Programmierer muß sich selbst um Speicherreservierung, Freigabe und Resourcenschutz kümmern. Der Programmierer muß eigenen Code zur Bereichsprüfung schreiben. Der Programmierer kann bei Bedarf die Größe des Arrays verändern, siehe quasidynamische Arrays. Der entsprechende Code dafür muß vom Programmierer selbst erzeugt werden.

type
  TMyItem = Double;
  PMyArray = ^TMyArray;
  TMyArray = array[0..16000] of TMyItem;

var
  arr: PMyArray;
  ..
begin
  ...
  GetMem(arr, ItemCount * SizeOf(TMyItem));
  try
    ...
    arr^[0] := 0.0;
    ...
  finally
    FreeMem(arr);
  end;

Die in TMyArray festgelegte Größe ist rein fiktiv und kann beliebig gewählt werden.

Delphi's dynamisches Array
Hierbei handelt es sich um ein dynamisch erzeugtes Array. Der Compiler fügt jedoch automatisch Code ein, um dem Programmierer die Arbeit zu erleichtern. Zusätzlich dazu gibt es einen Referenzmechanismus.

Die Elemente liegen im Heap. Die (maximale) Anzahl der Elemente muß erst zur Laufzeit bekannt sein. Der Programmierer muß sich selbst um die Speicherreservierung kümmern. Der Compiler erzeugt Code für die Bereichsprüfung, wenn der entsprechende Compilerschalter gesetzt ist. Der Programmierer kann bei Bedarf die Größe des Arrays verändern, siehe quasidynamische Arrays. Für Speicherreservierung, Größenänderung und Freigabe steht die Procedure SetLength zur Verfügung. Mit Length kann die aktuelle Größe abgefragt werden.

Dynamische Array-Variablen sind Zeiger, auch wenn man ihnen das nicht ansieht. Das hat entsprechende Auswirkungen. Wird eine normale Array Variable zugewiesen, dann wird deren Inhalt kopiert. Bei einer Dynamische Array-Variablen wird nur der Zeiger kopiert und der Referenzzähler erhöht. Wird anschließend ein Element geändert, dann ist dieses Element bei beiden Array-Variablen geändert. Anders sieht es bei SetLength aus. Wird nach einer Zuweisung die Größe des Arrays verändert, dann geschieht dies nur bei der einen Variablen. Die andere zeigt immer noch auf das alte Array. Das kann man sich zunutze machen und nach einer Zuweisung SetLength mit der aktuellen Größe (Length) aufrufen, um Änderungen in der anderen Variable zu verhindern. Ein solcher Aufruf stellt sicher, daß das Array einen Referenzzähler von 1 hat.

type
  TMyItem = Double;

var
  arr: array of TMyItem;
  ..
begin
  ...
  SetLength(arr, ItemCount);
  ...
  arr[0] := 0.0;
  ...

Klassen in der VCL

Die VCL stellt mehrere Klassen zur Verfügung, die intern mit Pointer-Arrays arbeiten. Die Klassen arbeiten quasidynamisch und verfügen über getrennte Eigenschaften für Kapazität (Capacity) und Größe (Count). Unter Größe wird dabei die Anzahl der verwendeten Elemente verstanden, unter Kapazität die maximale Anzahl.

Die Klassen stellen Methoden für die Veränderung der Größe, das Einfügen, Löschen, Vertauschen und Sortieren von Elementen zur Verfügung. Die Klassen führen generell eine Bereichsüberprüfung durch, der Speicher für das Pointerarray wird automatisch verwaltet. Der Programmierer muß sich selbst um Speicherreservierung, Freigabe und Resourcenschutz für die Klasse kümmern.

TList
TList ist die Kapselung eines Pointerarrays. Der Programmierer muß sich selbst um Speicherreservierung, Freigabe und Resourcenschutz für die Elemente kümmern. Der Zugriff auf die Elemente erfolgt über den Typ Pointer.

TThreadList
TThreadList ist eine threadsichere Kapselung für eine TList.

TObjectList
TObjectList ist eine Klasse, die sehr ähnlich, wie TList arbeitet. Der Unterschied ist, daß TObjectList anstelle des Typs Pointer den Typ TObject verlangt. TObjectList enthält eine Eigenschaft OwnsObjects, über welche festgelegt werden kann, ob die Elemente (vom Typ TObject abgeleitete Klassen) freigegeben werden sollen oder nicht.

TStringList
TStringList ist von TStrings abgeleitet. Das intern verwendete Array enthält zwei Pointer. Der eine zeigt auf einen String, der andere ist für eine Instanz gedacht, die von TObject abgeleitet ist. Diese Klasse ist besonders für Elemente geeignet, die über einen String angesprochen werden sollen.

TCollection
TCollection sorgt sich komplett um die Verwaltung von Instanzen, die von TCollectionItem abgeleitet sind. Der Programmierer muß sich nicht um die Reservierung oder Freigabe von Elementen kümmern. Suche und Sortierung sind nicht implementiert.

Vergleich zwischen TList und array of

Mehrdimensionale Arrays

Mehrdimensionale Arrays lassen sich als Arrays von Arrays zusammensetzen. Je nach Speicheralloziierung ergeben sich daraus zwei Modelle. Das eine tastet sich Dimension für Dimension vor, bis es zum Element kommt. Das andere überführt ein mehrdimensionales Array in ein eindimensionales.