- Datenstrukturen, deren Größe sich während der Laufzeit des Programms ändert
-
bestehen aus Basiseinheiten (Knoten) mit Daten und Zeigern
-
werden über die Zeiger zusammengehängt
- Knoten können verschiedene Anzahl von Zeigern besitzen
- Zeiger können auf nichts verweisen (Wert null)
- Zeiger können rückwärts oder auf den eigenen Knoten zeigen
- mindestens ein Zeiger muss "von außen" auf die Struktur verweisen (im Bild der Zeiger start)
-
grundsätzlich beliebig viele Daten im Knoten
- i.f. aber nur eine (Fließkomma-)Zahl
- dient als Suchschlüssel für die anderen (nicht betrachteten) Daten
- Knoten haben genau einen Zeiger
- auf jeden Knoten zeigt genau ein Zeiger
-
der Zeiger des letzten Knotens ist null
(kein Ring)
-
Knoten für Listen als Java-Klasse: ListenKnoten.java
- Datenfelder von ListenKnoten haben Standard-Zugriffsklasse ("package")
- direkter Zugriff möglich für Klassen aus dem selben Paket (z.B. Liste)
- kein Zugriff für externe Klassen
-
Beispiel: Aufbau der obenstehenden Liste
ListenKnoten meineListe = new ListenKnoten(16.0); ListenKnoten neuerKnoten = new ListenKnoten(42.0); neuerKnoten.naechster = meineListe; meineListe = neuerKnoten; neuerKnoten = new ListenKnoten(5.0); neuerKnoten.naechster = meineListe; meineListe = neuerKnoten;
-
Grundidee: Knoten direkt an die passende Stelle einfügen
- dazu zunächst durch die Liste laufen, um Einfügestelle zu finden
-
Problem:
- Stelle gefunden, sobald größeres Element auftaucht
- neues Element davor einfügen
- Rückwärtslaufen geht nicht
- Lösung: zweiten Zeiger mitnehmen, der immer einen zurückhinkt
-
Implementierung in Java:
- zusätzliche Klasse Liste
- enthält Zeiger auf 1. Element
- enthält Methoden zum Einfügen, Suchen etc.
-
Fallunterscheidungen beim Einfügen nötig:
- Liste ist leer → neues Element wird Start-Element
- Start-Element ist kleinstes → wird einfach vorgehängt
- Start-Element ist größstes → wird hinten angehängt
- sonst richtig einfädeln
- Beispielprogramm: Liste.java
- Nachteil: Suchen dauert lange (immer durch Liste durchlaufen)
- sehr nützliche Kombination aus Liste und Array
- verwendbar als wachsendes/schrumpfendes Array
-
implementiert Interface List →
- add(Object o) fügt o an das Ende der Liste an
- remove(Object o) entfernt (erstes Auftreten von) o aus der Liste
- isEmpty() ist true, falls Liste leer
-
erlaubt Array-Zugriff
- get(int index) gibt Objekt an Position index zurück
- set(int index, Object o) speichert o an Position index
- size() gibt Anzahl der Elemente zurück