20. April 2009

Datenstrukturen: Liste in Java programmieren (Prg2)

Die Daten können auf dem PC in verschiedenen Formen organisiert bzw. gespeichert werden. Der Vorteil einer Liste sind folgende:

  • dynamische Speicherzuordnung (es wird nur Speicher zugewiesen, wenn auch Daten vorhanden sind)
  • das Hinzufügen bzw. Löschen eines Datensatzes in die Liste ist sehr schnell

Ein Nachteil ist jedoch, dass das Indexieren sehr langsam ist, denn wenn man auf das letzte Element zugreifen will, muss die Liste komplett von vorne durchsucht werden.

Damit man dies versteht, werde ich die Funktionsweise und Umsetzung in Java etwas erläutern.

Funktionsweise einer Liste (LinkedList)

Statt wie in einem Array, dass man per Index auf jedes Element zugreifen kann, muss in einer Liste (LinkedList) jedes Element vorher aufgerufen werden (wenn man das letzte Element haben möchte).

linkedlist-liste-java

Objekt 1 besteht aus 2 Feldern: 1 Feld speichert die zu speichernde Information und das zweite Feld speichert die Referenz auf das nächste Objekt, die eine weitere Information enthält. Die einfachste Verkettung erfolgt also, wenn ein Objekt nur die Referenz auf das nachstehende Objekt speichert. So kennt ein Objekt maximal einen Speicherort bzw. eine Referenz eines anderen Objekts (siehe Abbildung).

An beliebiger Stelle einfügen

Was tut man nun, wenn man der Position 2 von 3 existierenden Elementen einen neuen Datensatz einfügen will? In unserem Beispiel also möchte ich an der Stelle mit der 37 die Zahl 50 speichern, d.h. das der neue Datensatz zwischen 99 und 37 eingefügt werden muss (gezählt wird ab 0).

Lösung

Man ändert die Referenz im Objekt mit der 99. Statt auf die 37 Referenzieren, referenziert man auf das neue Objekt mit der 50. Damit aber die Referenz auf die 37 nicht verloren geht, muss diese zwischen gespeichert werden. Im Objekt 50 muss anschließend wieder die Referenz auf das Objekt mit der 37 gespeichert werden.

Eine kleine Lösung biete ich hier als Download an. Meine Lösung ist jedoch nicht effektiv genug und enthält noch kleine Fehler, aber der Aufbau und das Prinzip sollten damit deutlich werden.

Wer sich die Liste richtig ausführlich erklären lassen will, kann sich die Vorlesung an der Uni Osnabrück online angucken und dazulernen: Video - Liste in Java programmieren (1 Stunde 22 Minuten).

Einen Kommentar schreiben