Verkettete Liste

Visualisierung

New-Operator

• Mit dem New-Operator kann zur Laufzeit (dynamisch) Speicherplatz reserviert und angelegt werden

• Vorteil:– Es wird lediglich der benötigte Speicherplatz

reserviert und nicht beispielsweise über ein Feld (unnötig) viel oder zu wenig Speicherplatz reserviert

– Man kann den Speicher wieder freigeben, ohne die Speicherorganisation zu zerstören (Destruktoren machen zum ersten Mal Sinn)

– Objekte können als Pointer angelegt werden– Einfacher als in der strukturierten

Programmiersprache C (dort mit malloc und calloc und free)

Typ

Hersteller

Farbe

KW / PS

Auto *next

Klasse Auto

Nutzdaten

Pointer auf nächstes Objekt

Lege neues Objekt an

Auto *start = NULL

Auto *ende = NULL

Das Programm wird gestartet

Typ

Hersteller

Farbe

KW / PS

Auto *next

Klasse Auto

Nutzdaten

Pointer auf nächstes Objekt

Lege neues Objekt an

Auto *start = NULL

Auto *ende = NULL

Button wird geklickt

Typ

Hersteller

Farbe

KW / PS

Auto *next

Klasse Auto

Nutzdaten

Pointer auf nächstes Objekt

Lege neues Objekt an

Typ

Hersteller

Farbe

KW / PS

Auto *next

Auto *start = NULL

Auto *ende = NULL

= NULL

Auto *temp

Mit dem New-Operator wirdein neues Objekt angelegt

Typ

Hersteller

Farbe

KW / PS

Auto *next

Klasse Auto

Nutzdaten

Pointer auf nächstes Objekt

Lege neues Objekt an

Typ

Hersteller

Farbe

KW / PS

Auto *next

Auto *start = NULL

Auto *ende = NULL

= NULL

Auto *temp

Wenn *start = Null ist,Setze *start und *ende

auf das neue Objekt

Typ

Hersteller

Farbe

KW / PS

Auto *next

Klasse Auto

Nutzdaten

Pointer auf nächstes Objekt

Lege neues Objekt an

Typ

Hersteller

Farbe

KW / PS

Auto *next

Auto *start

Auto *ende

= NULL

Auto *temp

Das ist der Fall

Typ

Hersteller

Farbe

KW / PS

Auto *next

Klasse Auto

Nutzdaten

Pointer auf nächstes Objekt

Lege neues Objekt an

Typ

Hersteller

Farbe

KW / PS

Auto *next

Auto *start

Auto *ende

= NULL

Auto *temp

Button wird geklickt

Typ

Hersteller

Farbe

KW / PS

Auto *next

Klasse Auto

Nutzdaten

Pointer auf nächstes Objekt

Lege neues Objekt an

Typ

Hersteller

Farbe

KW / PS

Auto *next

Typ

Hersteller

Farbe

KW / PS

Auto *next

Auto *start

Auto *

= NULL

= NULL

Auto *temp

Mit dem New-Operator wirdein neues Objekt angelegt

Typ

Hersteller

Farbe

KW / PS

Auto *next

Klasse Auto

Nutzdaten

Pointer auf nächstes Objekt

Lege neues Objekt an

Typ

Hersteller

Farbe

KW / PS

Auto *next

Typ

Hersteller

Farbe

KW / PS

Auto *next

Auto *start

Auto *ende

= NULL

= NULL

Auto *temp

Wenn *start = Null ist,Setze *start und *ende

auf das neue Objekt

Typ

Hersteller

Farbe

KW / PS

Auto *next

Klasse Auto

Nutzdaten

Pointer auf nächstes Objekt

Lege neues Objekt an

Typ

Hersteller

Farbe

KW / PS

Auto *next

Typ

Hersteller

Farbe

KW / PS

Auto *next

Auto *start

Auto *ende

= NULL

= NULL

Auto *temp

Das ist nicht der Fall

Typ

Hersteller

Farbe

KW / PS

Auto *next

Klasse Auto

Nutzdaten

Pointer auf nächstes Objekt

Lege neues Objekt an

Typ

Hersteller

Farbe

KW / PS

Auto *next

Typ

Hersteller

Farbe

KW / PS

Auto *next

Auto *start

Auto *ende

= NULL

= NULL

Auto *temp

Jetzt tritt der else-Fall in Kraft

Typ

Hersteller

Farbe

KW / PS

Auto *next

Klasse Auto

Nutzdaten

Pointer auf nächstes Objekt

Lege neues Objekt an

Typ

Hersteller

Farbe

KW / PS

Auto *next

Typ

Hersteller

Farbe

KW / PS

Auto *next

Auto *start

Auto *ende

= NULL

Auto *temp

setze den Pointer *ende->next auf *temp

Typ

Hersteller

Farbe

KW / PS

Auto *next

Klasse Auto

Nutzdaten

Pointer auf nächstes Objekt

Lege neues Objekt an

Typ

Hersteller

Farbe

KW / PS

Auto *next

Typ

Hersteller

Farbe

KW / PS

Auto *next

Auto *start

Auto *ende

= NULL

Auto *temp

Setzte den Pointer *ende auf *temp

Typ

Hersteller

Farbe

KW / PS

Auto *next

Klasse Auto

Nutzdaten

Pointer auf nächstes Objekt

Lege neues Objekt an

Typ

Hersteller

Farbe

KW / PS

Auto *next

Typ

Hersteller

Farbe

KW / PS

Auto *next

Auto *start

Auto *ende

= NULL

Auto *temp

Button wird geklickt

Typ

Hersteller

Farbe

KW / PS

Auto *next

Klasse Auto

Nutzdaten

Pointer auf nächstes Objekt

Lege neues Objekt an

Typ

Hersteller

Farbe

KW / PS

Auto *next

Typ

Hersteller

Farbe

KW / PS

Auto *next

Auto *start

Auto *ende

= NULL

Auto *temp

Mit dem New-Operator wirdein neues Objekt angelegt

Typ

Hersteller

Farbe

KW / PS

Auto *next = NULL

Typ

Hersteller

Farbe

KW / PS

Auto *next

Klasse Auto

Nutzdaten

Pointer auf nächstes Objekt

Lege neues Objekt an

Typ

Hersteller

Farbe

KW / PS

Auto *next

Typ

Hersteller

Farbe

KW / PS

Auto *next

Auto *start

Auto *ende

= NULL

Auto *temp

Typ

Hersteller

Farbe

KW / PS

Auto *next = NULL

Wenn *start = Null ist,Setze *start und *ende

auf das neue Objekt

Typ

Hersteller

Farbe

KW / PS

Auto *next

Klasse Auto

Nutzdaten

Pointer auf nächstes Objekt

Lege neues Objekt an

Typ

Hersteller

Farbe

KW / PS

Auto *next

Typ

Hersteller

Farbe

KW / PS

Auto *next

Auto *start

Auto *ende

= NULL

Auto *temp

Typ

Hersteller

Farbe

KW / PS

Auto *next = NULL

Das ist aber nicht der Fall. Also tritt

wieder der else-Fall in Kraft

Typ

Hersteller

Farbe

KW / PS

Auto *next

Klasse Auto

Nutzdaten

Pointer auf nächstes Objekt

Lege neues Objekt an

Typ

Hersteller

Farbe

KW / PS

Auto *next

Typ

Hersteller

Farbe

KW / PS

Auto *next

Auto *start

Auto *ende

Auto *temp

Typ

Hersteller

Farbe

KW / PS

Auto *next = NULL

setze den Pointer *ende->next auf *temp

Typ

Hersteller

Farbe

KW / PS

Auto *next

Klasse Auto

Nutzdaten

Pointer auf nächstes Objekt

Lege neues Objekt an

Typ

Hersteller

Farbe

KW / PS

Auto *next

Typ

Hersteller

Farbe

KW / PS

Auto *next

Auto *start

Auto *ende

Auto *temp

Typ

Hersteller

Farbe

KW / PS

Auto *next = NULL

Setzte den Pointer *ende auf *temp

Typ

Hersteller

Farbe

KW / PS

Auto *next

Klasse Auto

Nutzdaten

Pointer auf nächstes Objekt

Lege neues Objekt an

Typ

Hersteller

Farbe

KW / PS

Auto *next

Typ

Hersteller

Farbe

KW / PS

Auto *next

Auto *start

Auto *ende

Auto *temp

Typ

Hersteller

Farbe

KW / PS

Auto *next = NULL

Und so würde es weiter gehen.Ein neues Objekt würde angelegt werden durch Klicken des Buttons.*temp zeigt auf das neue Objekt.

Die Pointer würden wie zuvor

ver- bzw. umgebogen werden.

Typ

Hersteller

Farbe

KW / PS

Auto *next

Klasse Auto

Nutzdaten

Pointer auf nächstes Objekt

Lege neues Objekt an

Typ

Hersteller

Farbe

KW / PS

Auto *next

Typ

Hersteller

Farbe

KW / PS

Auto *next

Auto *start

Auto *ende

Auto *temp

Typ

Hersteller

Farbe

KW / PS

Auto *next = NULL

Folgende Erweiterungsmöglichkeiten wären denkbar.

1. Erweiterung der Klasse mit dem Pointerprevious (vorheriger Knoten)

(Hier rot dargestellt)

Auto *prev

Auto *prev

Auto *prev= NULL

Auto *prev Pointer auf vorheriges Objekt

Typ

Hersteller

Farbe

KW / PS

Auto *next

Klasse Auto

Nutzdaten

Pointer auf nächstes Objekt

Lege neues Objekt an

Typ

Hersteller

Farbe

KW / PS

Auto *next

Typ

Hersteller

Farbe

KW / PS

Auto *next

Auto *start

Auto *ende

Auto *temp

Typ

Hersteller

Farbe

KW / PS

Auto *next = NULL

Auto *prev

Auto *prev

Auto *prev= NULL

Eine weitere Erweiterungsmöglichkeit wäre danach:

Ein Löschen einzelner Knoten

Auto *prev Pointer auf vorheriges Objekt

Typ

Hersteller

Farbe

KW / PS

Auto *next

Klasse Auto

Nutzdaten

Pointer auf nächstes Objekt

Lege neues Objekt an

Typ

Hersteller

Farbe

KW / PS

Auto *next

Typ

Hersteller

Farbe

KW / PS

Auto *next

Auto *start

Auto *ende

Auto *temp

Typ

Hersteller

Farbe

KW / PS

Auto *next = NULL

Auto *prev

Auto *prev

Auto *prev= NULL

Der gelb dargestellte Knoten soll gelöscht werden.

Was muss alles geprüft werden?Welche Pointer müssen verbogen

werden ?

Auto *prev Pointer auf vorheriges Objekt

Typ

Hersteller

Farbe

KW / PS

Auto *next

Klasse Auto

Nutzdaten

Pointer auf nächstes Objekt

Lege neues Objekt an

Typ

Hersteller

Farbe

KW / PS

Auto *next

Typ

Hersteller

Farbe

KW / PS

Auto *next

Auto *start

Auto *ende

Auto *temp

Typ

Hersteller

Farbe

KW / PS

Auto *next = NULL

Auto *prev

Auto *prev

Auto *prev= NULL

Eine weitere Erweiterungsmöglichkeit wäre danach:

Ein Einfügen eines Knoten an eine bestimmte Stelle.

Hier grün eingefärbt.

Auto *prev Pointer auf vorheriges Objekt

Typ

Hersteller

Farbe

KW / PS

Auto *next

Auto *prev

Typ

Hersteller

Farbe

KW / PS

Auto *next

Klasse Auto

Nutzdaten

Pointer auf nächstes Objekt

Lege neues Objekt an

Typ

Hersteller

Farbe

KW / PS

Auto *next

Typ

Hersteller

Farbe

KW / PS

Auto *next

Auto *start

Auto *ende

Auto *temp

Typ

Hersteller

Farbe

KW / PS

Auto *next = NULL

Auto *prev

Auto *prev

Auto *prev= NULL

Eine weitere Erweiterungsmöglichkeit wäre danach:

Das Ändern der Nutzdaten eines Knoten an eine

bestimmte Stelle. Hier grün eingefärbt.

Auto *prev Pointer auf vorheriges Objekt

Typ

Hersteller

Farbe

KW / PS

Auto *next

Klasse Auto

Nutzdaten

Pointer auf nächstes Objekt

Lege neues Objekt an

Typ

Hersteller

Farbe

KW / PS

Auto *next

Typ

Hersteller

Farbe

KW / PS

Auto *next

Auto *start

Auto *ende

Auto *temp

Typ

Hersteller

Farbe

KW / PS

Auto *next = NULL

Auto *prev

Auto *prev

Auto *prev= NULL

Auto *prev Pointer auf vorheriges Objekt

Eine weitere Erweiterungsmöglichkeit wäre danach:

Das Tauschen zweier Knoten bzw. derer Knoten

Hier grün eingefärbt.

Erweiterungsmöglichkeiten

• Sortierstartpointer

• Sortierendepointer

• Sortierpreviouspointer in der Klasse

• Sortiernextpointer in der Klasse