Neben den Arrays und den Records stellt uns die Programmiersprache PASCAL ( DELPHI ) noch eine weitere außerordentlich nützliche Datenstruktur zur Verfügung: die Pointer (siehe Feldermodell). Mithilfe von Pointern kann man sich sehr viele nicht vordefinierte eigene Datenstrukturen selbst herstellen. Dies wollen wir beispielsweise anhand der Datenstruktur Liste deutlich machen, die einerseits eine der am häufigstens verwendeten Datenstrukturen ist, andererseits aber nicht von der Programmiersprache zur Verfügung gestellt wird, so daß wir sie selbst mit den Mitteln der Sprache definieren (implementieren) müssen. Dies eben wollen wir mithilfe der Pointer tun.

Die Datenstruktur "Liste"
Eine Liste L ist wie ein Array A eine Folge von Feldern. Anders als beim Array sind diese Felder nicht durch Integer indiziert. Und anders als beim Array können wir mitten in die Liste weitere Felder einschieben, wir können die Liste von beiden Seiten verlängern und kürzen, ja wir können sogar die Liste in zwei Listen zerhacken oder eine Liste aus zwei anderen zusammensetzen. Da die Elemente der Liste keine festen Plätze haben, macht es keinen Sinn, ihnen feste Adressen innerhalb der Liste zuzuordnen. Wir werden also nicht so etwas wie   L[w] oder L.w  schreiben, wobei w die Adresse eines Feldes innerhalb der Liste ist. Dafür haben wir aber Listenoperationen, die die oben beschriebenen Vorgänge beschreiben:

first(L)       gibt das erste Listenfeld
last(L)        gibt das letzte Listenfeld
pred(L,a)      gibt das in L vor Feld a stehende Feld
next(L,a)      gibt das in L nach Feld a stehende Feld
insert(L,a,w)  fügt in die Liste hinter dem Feld a ein Feld mit dem Wert w ein.
delete(L,a)    nimmt aus der Liste das Feld a heraus
cons(L,L')     hängt die Liste L' hinten an die Liste L an

Zunächst definieren wir den Typ von Record, den wir für ein Listenelement verwenden wollen: die Komponente "vor" liefert die Position (den Index, die Adresse) des vorhergehenden Elements im Array, die Komponente "nach" die Position des nachfolgenden und die Komponente "wert" den eigentlichen Inhalt des Elements (hier ein Integer)

type elem = record
        vor:  integer;
        wert: integer;
        nach: integer;
     end;

Jetzt deklarieren wir einen Array a genügender Größe N, in dessen Komponenten unsere Elemente (Records) gespeichert werden können.Zugleich deklarieren wir einen zweiten Boolean-Array f , der zu jeder Position i angeben soll, ob diese Position im Array a schon besetzt ist (f[i]=1) oder nicht (f[i]=0). Und schließlich deklarieren wir noch 2 Positionsvariable p,q, die Array-Adressen speichern sollen, und eine Sonderposition nil = 0, die auf kein Feld des Arrays verweist, der ja erst mit 1 beginnt.

var a: array[1..N] of elem;
var f: array[1..N] of boolean;
var p,q: integer;
var i: integer;
const nil=0;

Als nächstes deklarieren wir eine Prozedur "new", die uns eine freie Position im Array a liefern soll. Diese Prozedur geht davon aus, daß der Array f zu Anfang mit Nullen gefüllt ist (diese Initialisierung des Arrays f muß als erstes im Hauptprogramm geschehen).

procedure new(var p:integer);
begin
    p:=1
    while f[p]=1 do p:=p+1;
    f[p]:=1
end;

Die Prozedur "free" erklärt eine Position wieder als frei, wenn wir sie nicht mehr brauchen,

procedure free(p:integer);
begin
    f[p]:=0
end;

Die nächste Prozedur schafft uns eine erste Liste mit 100 Elementen, die die Integer 1 bis 100 tragen. Die benachbarten Listenelemente verweisen aufeinander per Positionsangabe. So wie die Prozedur "new" geschrieben ist, liegen die 100 Listenelemente in der richtigen Reihenfolge in den ersten 100 Arrayfeldern, aber dies ist eine für uns unwichtige Tatsache, die sich auch bald ändern wird. Wichtig ist, daß wir durch die Verweise von jedem Listenelement zu seinem Vorgänger- und seinem Nachfolgerelement gelangen können, auch wenn diese nicht mehr in benachbarten Arrayfeldern liegen.

procedure anfangslist;
begin
    new(p);
    a[p].vor  := nil;
    a[p].wert := 1;
    a[p].nach := nil;
    q := p;

    for i:= 2 to 100 do begin
        new(p);
        a[q].nach := p;
        a[p].vor  := q;
        a[p].wert := i;
        a[p].nach := nil;
        q := p;
    end;
end;

Um durch die so geschaffene Liste zu wandern benötigen wir die Prozeduren "next" und "pred":

procedure next(var p:integer);
begin
    p:=a[p].nach
end;

procedure pred(var p:integer);
begin
    p:=a[p].vor
end;

Im Gegensatz zu der Datenstruktur "Array" können wir neue Elemente mitten in eine Liste einfügen oder herauslöschen. Das tun wir mit den Prozeduren "Insert" und "delete". Die Prozedur "insert" fügt hinter dem Element mit der Adresse p eine neues Element ein, welches den Integerinhalt w hat, die Prozedur "delete" löscht das Element mit der Adresse p aus der Liste heraus.

procedure insert(p,w:integer);
begin
    new(q);
    a[q].vor  := p;
    a[q].wert := w;
    a[q].nach := a[p].nach;
    a[p].nach := q;
    if a[q].nach <> nil then a[a[q].nach].vor := q;
end;

procedure delete(p:integer);
begin
    if a[p].vor  <> nil then a[a[p].vor].nach := a[p].nach;
    if a[p].nach <> nil then a[a[p].nach].vor := a[p].vor;
    free(p);
end;

Zuletzt noch das Hauptprogramm. Das initialisiert den Booleschen Array auf 0, schafft eine anfängliche Liste, wonach die Positionsvariablen p und q auf das letzte Element der Liste zeigen. Danach läuft die Positionsvariable p zum Anfang der Liste. Dann wird jedes zweite Listenelement gelöscht. Danach stehen p und q auf nil.

begin
    for i=1 to 100 do f[i]:=0;
    anfangslist;
    while a[p].vor <> nil do pred(p);
    q:=p;
    for i=1 to 50 do begin
        next(p); next(p); delete(q); q:=p;
    end;
end;

Wir hätten allerdings die Vorteile eines Arrays auch direkt nutzen können, indem wir mit den Positionen im Array gerechnet hätten. Um etwa jedes zweite Listenelement zu löschen, hätten wir auch einfacher
    for i = 0 to 49 do delete(2i+1)
schreiben können. Aber der Array diente nur zur Veranschaulichung, seine besonderen Möglichkeiten sollten gerade nicht genutzt werden, weil die Vorteile im Zuge weiterer Listenveränderungen ohnehin verloren gehen.

Um einen solchen Array, dessen Größe wir nicht im Voraus wissen können, nicht deklarieren zu müssen, stellt uns die Programmiersprache die Datenstruktur "Adresse" bzw. "Pointer" zu Verfügung mit den Operationen ^, new und free.

Benutzen wir statt des Arrays die originale Datenstruktur Pointer, so ändert sich fast nichts. Einzig der Recordtyp für die Listenelemente hat jetzt echte Pointerverweise anstelle von Arraypositionen. Wir können uns den Hauptspeicher wie einen großen Array vorstellen. Allerdings werden uns die Prozeduren "new" und "free" als Statements "new" und "free" zur Verfügung gestellt, ebenso wie die Adresskonstante nil. Die Adresse nil kann keinen Wert haben (der Wert ist immer undefiniert.)  Dieser Array "Hauptspeicher" ist für uns allerdings nicht indiziert durch Integer oder einen anderen ordinalen Typ.

type elem = record
        vor:  ^elem;
        wert: integer;
        nach: ^elem;
    end;

var p,q: ^integer;
var i: integer;

Die Prozeduren "new" und "free" werden durch die Statements "new" und "free" ersetzt, die aber dieselbe Funktion haben.

In den Prozeduren "anfangslist", "next" , "pred" , "insert", "delete" und dem Hauptprogramm wird nur die Schreibweise etwas geändert. Statt a[p] schreiben wir jetzt p^. Und die Initialisierung des Arrays f fällt weg.

procedure anfangslist;
begin
    new(p);
    p^.vor  := nil;
    p^.wert := 1;
    p^.nach := nil;
    q:=p;

    for i=2 to 100 do begin
        new(p);
        q^.nach := p;
        p^.vor  := q;
        p^.wert := i;
        p^.nach := nil;
        q:=p;
    end;
end;

procedure next(var p:integer);
begin
    p:=p^.nach
end;

procedure pred(var p:integer);
begin
    p:=p^.vor
end;

procedure insert(p,w:integer);
begin
    new(q);
    q^.vor  := p;
    q^.wert := w;
    q^.nach := p^.nach;
    p^.nach := q;
    if q^.nach <> nil then q^.nach.vor := q;
end;

procedure delete(p:integer);
begin
    if p^.vor <>  nil then p^.vor.nach := p^.nach;
    if p^.nach <> nil then p^.nach.vor := p^.vor;
    free(p);
end;

begin
    anfanglist;
    while p^.vor <> nil do pred(p);
    q:=p;
    for i=1 to 50 do begin
        next(p); next(p); delete(q); q:=p;
    end;
end;

Aufgabe: Verändern Sie die Prozeduren so, daß wir Pointer a  und e haben, die auf den Anfang bzw. das Ende der Liste zeigen, sodaß wir immer definierte Einstiegspunkte in die Liste haben. Schreiben Sie eine Prozedur "empty", die uns angibt, ob die Liste leer ist.