Tutorial zu zyklischen Listen
Inhalt
Hier eine kleine Übersicht, in welche Teile sich das Tutorial gliedert.
I - Grundlagen
II - Skizze
III - Realisierung in C++
IV - Analyse
V - Fazit
VI - Beispiel
Alles in allem bleibt mir glaube ich noch, euch viel Spaß beim Lesen zu wünschen
(Nachtrag: Bei dem ganzen Tutorial steht eigentlich die Idee im Vordergrund. Man kann sich natürlich über Stil und Lowlevel Optimierung streiten, aber das überlasse ich Leuten die Zeit dafür haben.)
I - Grundlagen
Listen sind erstmal Datenstrukturen. Also Strukturen, welche dazu dienen gleichartige Objekte zu Gruppieren, um sie in Gruppen zu verarbeiten. Im Prinzip also erstmal das selbe wie ein Array. Die Wiki-Göttin sagt hierzu
Verkettete Listen gehören zu den dynamischen Datenstrukturen, die eine Speicherung von einer im Vorhinein nicht bestimmten Anzahl von miteinander in Beziehung stehenden Werten einfacher oder zusammengesetzter Datentypen erlauben. Sie werden durch Zeiger auf die jeweils folgende(n) Knoten oder Speicherzellen des Arbeitsspeichers realisiert.
Der wohl wichtigste Unterschied zwischen Listen und sogenannten Reihungen (Arrays) ist, dass die Anzahl der zu speichernden Element bei einer Liste im nicht vorher bekannt sein muss (also anders als bei einem Array).
Ebenfalls können wir keine implizite Indizierung der Objekte verwenden, also nicht ohne weiteres auf ein x-beliebiges Objekt der Liste zugreifen. Während wir bei einem Array die Speicherposition eines Objekts aus seinem Index im Array berechnen können, müssen wir ein Objekt in der Liste erst finden.
Es zeichnet sich schon recht deutlich ab, welche Anwendungsbereiche Listen haben: Falls wir eine erstmal unbestimmte Anzahl von gleichartigen Objekten speichern wollen, uns jedoch mit sequenziellem Zugriff zufrieden geben, dann sind Listen genau das, was wir haben wollen.
Wie auch immer, gibt es unzählige Tutorials und Dokumentationen zur Implementierung von verketteten Listen. Was macht eine Kreisförmige Liste dann so besonders?
Wie der Name schon sagt ist die Liste kreisförmig. Also eher ein Ring, als eine Liste. Entsprechend gibt es auch keinen definierten Anfang (Kopf) und kein bestimmtes Ende (Schwanz) in der Liste. Also haben wir schonmal ein wenig Verwaltungsaufwand gespart. Auch bei den gängigen Operationen wie Suchen, Einfügen und Löschen in/ aus der Liste werden wir weniger Sonderfälle behandeln müssen und generell mit weniger Operationen auskommen, als bei einer regulären Liste (Das ist natürlich gut, denn schliesslich entsprechen weniger Operationen grob gesehen erstmal weniger Rechenaufwand).
II - Skizze
Überlegen wir uns erstmal grob, wie man sowas anstellen könnte. Wie in der
klassischen doppelt verketteten Liste Kapseln wir die Objekte in sogenannte Knoten. Dabei besteht ein Knoten aus eben einem solchen Datenobjekt, sowie zwei Zeigern zu einem eindeutigen Nachfolgerknoten und einem eindeutigen Vorgängerknoten. Durch die verzeigerung der Knoten untereinander ergibt sich dann die Struktur der Liste.
Da wird keinen Kopf und keinen Schwanz mehr haben, müssen wir uns irgendwie anders Zugang zu der Liste verschaffen. Das machen wir einfach, indem wir uns irgend einen Knoten merken. Von diesem aus, können wir dann die Liste traversieren, indem wir sukzessive auf die Nachfolger- und Vorgängerknoten zugreifen.
III - Realisierung in C++
Zuerst möchte ich noch anmerken, dass jeder Mensch einen eigenen Programmierstil hat und das ich mir bewusst bin, dass meiner sicher nicht zu den Besten gehört
Davon ab, hoffe ich ihr könnt etwas mit dem Programmcode anfangen.
Zuerst einmal, will ich die Liste für generische Datentypen verwenden. Dazu verwende ich
templates. Um Sauber mit den Knoten zu arbeiten lege ich eine innere Klasse an (mitsamt einem Konstruktor, der uns später das Leben etwas einfacher macht.) Dazu direkt die Deklaration der gängigen Methoden.
|
C-/C++-Quelltext
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
template <typename BaseType> class List {
public:
//! A pointer to an arbitrary node in the list.
struct Node {
BaseType key;
Node* previous;
Node* next;
Node(BaseType& key, Node* next, Node* previous) : key(key), next(next), previous(previous) { }
} *current;
//! Creates an empty list.
List();
//! Create a copy of a list.
List(const List& other);
//! Removes a list.
virtual ~List();
//! Is the list empty?
bool isEmpty() const;
//! Insert a key into the list.
void insert(BaseType& key);
//! Find an Element in the list.
Node* find(BaseType& key);
//! Remove a node.
void remove(Node*);
//! Clear the list.
void clear();
}
|
Zunächst nehmen wir uns die simplen Methoden vor. Das einfachste sind hier wohl Kon- und Destruktor. Der Standardkonstruktor erstellt eine leere Liste, also eine Liste, in der sich keine Element befinden. Entsprechend können wir natürlich auch kein Element mit
current referenzieren.
|
|
C-/C++-Quelltext
|
1
2
3
4
|
template <typename BaseType>
List<BaseType>::List() {
current = 0;
}
|
Der Destruktor muss den dynamisch allozierten Speicher freigeben. Also einfach die Liste leeren. Das delegieren wir mal geschickt zur
clear()-Methode und überlegen uns später, wie genau wir das machen.
|
|
C-/C++-Quelltext
|
1
2
3
4
|
template <typename BaseType>
List<BaseType>::~List() {
clear();
}
|
Es ist auch sicher nützlich, zu erfahren, ob sich überhaupt irgendwelche Schlüssel in der Liste befinden. Hierzu benutzen wir die
isEmpty()-Methode. Diese prüft, ob es Knoten gibt. Dazu prüfen wir nach, ob wir mit
current einen Knoten referenzieren. Falls wir das nämlich tun, so existiert mindestens ein Knoten und die Liste ist dementsprechend nicht leer.
|
|
C-/C++-Quelltext
|
1
2
3
4
|
template <typename BaseType>
bool List<BaseType>::isEmpty() const {
return current == 0;
}
|
Als nächstes wollen wir natürlich unsere Liste auch mit Schlüsseln füllen. Dazu widmen wir uns dann der
insert(key)-Methode. Da die Schlüssel der Liste nicht geordnet sind, können wir den neuen Schlüssel also an eine beliebige Position einfügen. Hierfür bietet sich
current an, da dieser Knoten die einzige Stelle der Liste ist, die wir kennen.
Wir wollen also den neuen Schlüssel hinter dem aktuellen Knoten (
current) einsetzen. Hierbei treffen wir allerdings auf den ersten Randfall: Wenn unsere Liste leer ist, dann existiert kein aktueller Knoten hinter dem wir den neuen Schlüssel einfügen können. Ist die Liste also leer, so erstellen wir einen ersten Knoten.
|
|
C-/C++-Quelltext
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
template <typename BaseType>
void List<BaseType>::insert(BaseType& key) {
if (isEmpty()) {
current = new Node;
current->key = key;
current->next = current;
current->previous = current;
} else {
Node* node = new Node(key, current, current->next);
current->next = node;
node->next->previous = node;
current = current->next;
}
}
|
Die letzte Anweisung beim Einfügen setzt den aktuellen Knoten auf den eben eingefügten. Das ist natürlich nicht notwendig, aber es erweist sich für spätere Zwecke als sinnvoll. Alles in allem sollte man das aber unter
Geschmackssache verbuchen.
Als nächstes Wollen wir uns mit dem Suchen in der Liste beschäftigen. Hier kommt nämlich eine weitere Facette im Vergleich zu regulären Listen hinzu: Wir wissen, wegen Ermangelung von klar definierten Start- und Endknoten in der Liste, nicht, wann wir eine erfolglose Suche beenden müssen. Hierbei machen wir uns den Trick zu Nutzen, dass wir zwei Knoten anhand ihrer Speicheraddresse vergleichen können. Wir merken uns also, bei welchem Knoten wir die Suche begonnen haben und terminieren, falls wir diesen Knoten wieder erreichen.
|
|
C-/C++-Quelltext
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
template <typename BaseType>
List<BaseType>::Node* List<BaseType>::find(BaseType& key) {
// Desired key is not in the empty list.
if (isEmpty()) return 0;
// Remember where we started.
Node* start = current;
do {
// Have we found the desired key?
if (current->key == key) return current;
// Investigate the next element in the list.
current = current->next;
} while (current != start);
return 0;
}
|
Nachdem wir Schlüssel einfügen und suchen können, möchten wir ab und an auch mal den ein oder anderen Schlüssel entfernen. Hierzu verwenden wir die
remove(node)-Methode. Ich möchte der Methode einen Knoten statt einem Element übergeben. Wenn wir kurz drüber nachdenken, merken wir, dass wir durchaus gleiche Objekte mehrmals in der Liste ablegen können. Daher können wir ein zu löschendes Element nicht mehr eindeutig an seinem
key identifizieren. Entsprechend können wir die Rückgabe einer Suchoperation (welche ja ein Knoten ist) direkt verwenden um das Element zu löschen. Wir können also auch nur Elemente löschen, die in der Liste vorhanden sind. Hierbei gibt es den Randfall, das wir das letzte Element der Liste löschen.
|
|
C-/C++-Quelltext
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
template <typename BaseType>
void List<BaseType>::remove(List<BaseType>::Node* node) {
// Do we have only one element in the list?
if (node->next == node) {
delete current;
current = 0;
} else {
node->previous->next = node->next;
node->next->previous = node->previous;
if (current == node) current = node->next; // Avoid dangling pointer!
delete node;
}
}
|
Wichtig: Beim
remove() treffen wir eine sehr wichtige Annahme: Der Knoten, welcher als Parameter übergeben wird, ist ein Knoten aus der Liste. Angenommen wir führen im Programm gerade zwei Listen mit Integer-Werten und nehmen (via
find(key)) einen Knoten aus der ersten Liste und versuchen ihn aus der zweiten Liste zu löschen, so kann folgendes passieren:
a) Die erste Liste hat nur ein Element: Wir löschen das aktuelle Element der zweiten Liste. Alle anderen Elemente gehen verloren, sind aber nicht gelöscht ->
Memory Leak!
b) Die zweite Liste hat nur ein Element: Dieses wird korrekt entfernt, auch wenn es nicht das Element ist, welches wir löschen wollten.
c) Sonst:
node wird aus der ersten Liste entfernt. Klappt alles, ist aber vermutlich auch nicht dass, was wir eigentlich tun wollten.
Fazit: Immer aufpassen, dass nur Knoten aus Listen gelöscht werden, die diese Knoten auch enthalten!
Zu guter letzt möchten wir auch noch die gesamte Liste löschen können. Hier also die
clear()-Methode.
|
|
C-/C++-Quelltext
|
1
2
3
4
|
template <typename BaseType>
void List<BaseType>::clear() {
while (!isEmpty()) remove(current);
}
|
Jetzt gibt's noch den
sugar. Zuerst wäre da der
copy-c'tor um eine Liste zu duplizieren. Hierbei werden wir wirklich alle Objekte verdoppeln, um nicht irgendwelche Quirx durch Seiteneffekte zu provozieren.
|
|
C-/C++-Quelltext
|
1
2
3
4
5
6
7
8
9
|
template <typename BaseType>
List<BaseType>::List(const List<BaseType>& other) {
Node* start = other.current;
Node* node = other.current;
do {
insert(node->key);
node = node->next;
} while (node != start);
}
|
Hier versteckt sich allerdings implizit die Annahme, das die entsprechenden Operatoren und Konstruktoren für den Basistypen der Liste definiert sind. Ist das nicht der Fall, so gibt's Compilerfehler. Das selbe Verfahren kann man verwenden um den Zuweisungsoperator zu überladen.
Das sollten eigentlich alle Operationen sein, die man so im Alltag erstmal braucht. Ich hoffe der Code kompiliert vernünftig bei euch und ihr seid auch so von der Kürze angetan wie ich
Falls es Probleme/Unklarheiten gibt steht dies hier ja in einem Forum, indem man Nachfragen kann.
Als zusätzlichen
candy könnte man noch die Konkatenation von Listen implementieren. Hierzu kann man einfach die Addition überladen.
|
|
C-/C++-Quelltext
|
1
2
3
4
5
6
7
8
9
10
11
|
template <typename BaseType>
List<BaseType> List<BaseType>::operator + (const List<BaseType>& other) const {
List concat(*this);
Node* start = other.current;
Node* node = other.current;
do {
insert(node->key);
node = node->next;
} while (node != start);
return concat;
}
|
IV - Analyse
Im Wesentlichen unterscheidet sich die zyklische Liste nicht von regulären Listen, was die Performance angeht. Falls wir strikt sequenzielle Zugriffe auf die Schlüssel annehmen, sind die Operationen amoritisiert genauso teuer. Beispiel:
Um einen Knoten zu löschen benötigt eine reguläre Liste einen Aufwand, welcher linear zur Größe der Liste ist. Das Löschen in der zyklischen Liste besteht genaugenommen aus dem Finden & Löschen des Schlüssels. Das Finden benötigt linearen Aufwand und das Löschen nur eine konstante Anzahl von Operationen. Also ist das Löschen auch wieder linear.
Obwohl die Operationen in der zyklischen und regulären Liste asymptotisch gleich teuer sind, zeichnet sich die zyklische Liste durch weniger Fallunterscheidungen und weniger Operationen aus. Genaugenommen ist die zyklische Liste also um einen konstanten Faktor schneller als die normale Liste.
V - Fazit
Zirkuläre Listen unterscheiden sich von der Handhabung nicht von regulären Listen. Ihre Struktur ist ringförmig und die Operationen sind in der Regel simpler, was die positive Eigenschaft der zyklischen Listen ist, die mich am meisten überzeugt.
VI - Beispiel
Kurz bevor ich mit dem Tutorial "fertig" bin, kommt mir die Idee, vielleicht ein kurzes Beispiel zu geben, wie man die Liste verwenden kann. Ein interessanter Fall (und der Grund, warum alles
public deklariert ist) ist ein sogenanntes
mapping. Dabei handelt es sich um eine Funktion, welche auf alle Schlüssel in der Liste angewendet wird. Nehmen wir mal an, eine solche funktion
f liegt als Funktion, Methoden, Zeiger oder
functor vor. Um
f auf jeden Schlüssel einer Liste
L anzuwenden können wir eine kleine Schleife verwenden.
|
|
C-/C++-Quelltext
|
1
2
3
4
5
6
7
|
void demoMap() {
void* start = L.current;
do {
L.current->key = f(L.current->key);
L.current = L.current->next;
} while (start != L.current);
}
|
Und das war's auch schon! Ich hoffe ihr hattet Spaß beim Lesen des Tutorials und freue mich auf eure Kritik.
So long,
Michael.
Zitat von »Wikipedia«
Verkettete Listen gehören zu den dynamischen Datenstrukturen, die eine Speicherung von einer im Vorhinein nicht bestimmten Anzahl von miteinander in Beziehung stehenden Werten einfacher oder zusammengesetzter Datentypen erlauben. Sie werden durch Zeiger auf die jeweils folgende(n) Knoten oder Speicherzellen des Arbeitsspeichers realisiert.
Sämtliche COdes die hier reingestelt wurde, sehen danach nicht aus 
14.05.2024, 10:16
Zum Seitenanfang
