Tutorium Algorithmen und Datenstrukturen 2

Übungsblatt 2: Dynamische Datenstrukturen

Aufgabe 2-1

In ihrer einfachsten Form besteht eine nicht-leere lineare Liste aus nichts weiter als einem Wert („Kopf“ der Liste, hier eine Ganzzahl) und einem Verweis auf die Liste der restlichen Werte („Rumpf“).

Implementieren Sie eine Klasse LinearList mit genau diesen beiden Feldern. Nennen Sie den Kopf head und den Rumpf tail.

Aufgabe 2-2

Die folgenden Teilaufgaben beziehen sich auf Ihre Lösung aus Aufgabe 2-1 und auf die bereitgestellte Klasse MutableLinearList, die Ihre Lösung durch Vererbung erweitert.

1. MutableLinearList ist eine lineare Liste mit zusätzlichen Objektmethoden zum Verändern und Abfragen der Liste. Studieren Sie wenigstens eine dieser Methoden so weit, dass Sie ihre Funktionsweise detailliert beschreiben können.
   Merke: Nicht das Was ist am wichtigsten, sondern das Warum!
2. Schreiben Sie eine Methode start(), in der eine lineare Liste vom Typ MutableLinearList erzeugt wird. Die Liste soll genau die drei Elemente 42, 8 und 15 in dieser Reihenfolge haben.
3. In Java stellt das Paket java.util einen ganzen Sack voll mit verschiedenen dynamischen Datenstrukturen zur Verfügung. Die Klasse java.util.LinkedList ist eine fertige Implementierung einer doppelt verketteten linearen Liste. Finden Sie heraus, welche Methoden(aufrufe) in LinkedList denen in MutableLinearList am ehesten entsprechen.

Zusatzaufgabe 2-3

Verwenden Sie eine LinkedList zur Implementierung eines Stapels für Strings. Ihr Stapel soll eine eigene Klasse sein mit den beiden Objektmethoden push(String) und pop().

$Id: HEADER.html,v 1.3 2008/05/21 01:41:29 aj3 Exp $