---

Aufgabe Doppelt verkettete Liste

Letzte Änderung: 30. November 2020, 15:32 Uhr
17 Punkte — im Detail
Ansicht:   |  

Die Datenstrukur doppelt verkettete Liste ist eine situationsabhängige Alternative zu Arrays. Die Datenstruktur besteht aus Elementen, die neben ihren eigentlichen Werten zusätzlich ein Vorgänger- und ein Nachfolgerelement kennen. Hier ein Beispiel für zwei Einträge einer doppelt verketteten Liste:

Die Datenstruktur selbst enthält zwei Zeiger, die auf das erste und letzte Element zeigen. In einer leeren Liste sind beide mit dem nullptr belegt. Im folgenden Beispiel wurde der Wert 8 an Position 1 in die verkettete Liste eingefügt:

Wir werden die Funktionalität unserer doubly_linked_list so implementieren, dass der Nutzer der Datenstruktur nie mit Objekten vom Typ element interagieren muss. Das reduziert die Fehleranfälligkeit des Programms.

Aufgaben

1. Deklarieren Sie struct element und struct doubly_linked_list mit den nötigen Membervariablen. Die Datenstruktur und deren Methoden sollen in einer Headerdatei doubly_linked_list.h definiert und in einer Datei doubly_linked_list.cpp implementiert werden.
   Denken Sie an die rule of three: Beim Implementieren von Datenstrukturen mit Zeigerdatentypen (in diesem Fall doubly_linked_list) müssen sie den Destruktor (~doubly_linked_list()), den Copy-Konstruktor (doubly_linked_list(const doubly_linked_list&)) und den Copy-Assignment-Operator (doubly_linked_list& operator=(const doubly_linked_list&)) explizit überschreiben. Das gilt nicht für element, da die doubly_linked_list für deren Management zuständig ist.
2. Implementieren Sie folgende Memberfunktionen des element-Structs:
   1. void insert_after(uint64_t value);
      Anhängen eines neuen Elementes.
      Beachten Sie, dass das Nachfolgeelement von dem aktuellen Struct nicht verloren geht.
   2. void insert_before(uint64_t value);
      Hinzufügen eines neuen Elements vor der aktuellen Position.
      Beachten Sie, dass das Vorgängerelement von dem aktuellen Struct nicht verloren geht.
   3. element* remove();
      Lösche das aktuelle Element aus der Liste, gibt das Vorgängerelement zurück.
3. Implementieren Sie folgende Memberfunktionen in doubly_linked_list. Versuchen Sie dabei die Zugriffe auf die Knoten minimal zu halten.
   1. void append(uint64_t val) und void prepend(uint64_t val);
      Hängt ein neues Element ans Ende (bzw. an den Anfang) der Liste.
   2. bool insert_at(uint64_t val, size_t position);
      Fügt ein neues Element an der angegebenen Position in die Liste ein. Gibt zurück, ob das Einfügen erfolgreich war.
      
   3. size_t size();
      Ermittelt die Anzahl der Elemente der Liste.
   4. bool remove(size_t position);
      Löscht das Element, welches sich an der übergebenen Position befindet.
      Gibt zurück, ob das Löschen erfolgreich war. Denken Sie daran, dass sie dynamisch allokierte Objekte in C++ explizit durch delete löschen müssen.
   5. uint32_t operator[](size_t position) oder uint32_t get(size_t position);
      Gibt das Element an der angegebenen Position zurück.
      Gibt einen beliebigen Wert zurück, wenn der Index ungültig ist.
      
      Achtung: In vernünftigen Programmiersprachen (etwa in Python) würde man hier einen Fehler (Exception) werfen, wenn der Index außerhalb der gültigen Reichweite ist. In C++ geht das zwar theoretisch auch, bringt aber eventuell Laufzeitoverhead mit sich. Daher sieht man oft die alternative Variante, dass der Rückgabewert bei ungültigen Indizes nicht fest definiert ist. In modernem, sicherem C++ würde man grundsätzlich Exceptions bevorzugen.
      
      Übrigens: Viele Datenstrukturen in der C++-Standardbibliothek prüfen bei get, ob der angefragte Index gültig ist und werfen wenn nötig eine Exception, die operator[]-Implementierungen hingegen nicht.
   6. void print();
      Gibt alle Werte der Liste von vorne nach hinten aus.
   7. void append_merge(doubly_linked_list &b) und void prepend_merge(doubly_linked_list &b);
      Bonus: Überträgt alle Knoten einer anderen Liste an ans Ende (bzw. an den Anfang) an. Die andere Liste ist danach leer.
   8. void sort();
      Bonus: Sortiert die Liste.
4. Zeigen Sie die Verwendung aller Funktionen in ihrer main-Methode.
5. Welche der Operationen in doubly_linked_list sind unabhängig von der Listenlänge schnell, welche langsam? Begründen Sie Ihre Antwort kurz.