Verkettete Listen in Java

Was Listen von Arrays unterscheidet und wie man eigene einfach verkettete Listen implementiert

Neben Arrays stehen in Java als Datenstruktur auch sogenannte verkettete Listen zu Verfügung. Listen ähneln im Gebrauch und in der Funktion Arrays, unterscheiden sich aber gleichzeitig auch in einigen Punkten von ihnen. Je nach Einsatzszenario entscheidet man sich deswegen für Listen und gegen Arrays oder andersherum.

Der erste Unterschied zwischen einer Liste und einem Array offenbart sich schon bei der Initialisierung/Deklarierung. Bei einem Array muss man schon vor dem Benutzen die genaue Länge angeben. Dies ist insofern unpraktisch, wenn man noch gar nicht weiß, wie groß das Array überhaupt wird. Diese Gedanken muss man sich bei einer Liste nicht machen, sie wächst einfach dynamisch mit. Damit ist das Vergrößern und auch das Verkleinern während der Laufzeit kein Problem.

Der Nachteil von Listen ist abgesehen von einem höheren Speicherverbrauch, das etwas kompliziertere Handling im Gegensatz zu Arrays. Statt wie in Arrays direkt auf ein Element in einer Liste zugreifen zu können, muss man sich in verketteten Listen erst einmal zu dem entsprechenden Element „durchhangeln“. Dies geht zur Lasten der Geschwindigkeit und birgt ein höheres Fehlerpotential bei der Programmierung.

Man unterscheidet grundsätzlich zwischen einfach und mehrfach oder doppelt verketteten Listen. In Java wurden schon spezielle Listen, wie die Klassen ArrayList, LinkedList und Vector implementiert. Diese leiten sich von der abstrakten Klasse AbstractList ab, die schon grundlegende Funktionalität für Listen liefert. Für ein besseres Verständnis von Listen, kann es aber nicht schaden, wenn man selbst einmal, zumindestens eine einfach verkettete Liste, selbst implementiert. Dies wollen wir nun nachfolgend einmal tun.

Grundsätzlich kann die Implementierung einer einfach verketteten Liste ganz unterschiedlich aussehen. Nachfolgend verwenden wir zwei Klassen. Beim Hinzufügen eines neuen Listenelements, soll dieses immer am Anfang der Liste stehen (dies kann man natürlich auch ändern, z.B. so das ein neues Element immer am Schluss steht).

Klasse ListenElement

public class ListenElement {

	private String thema;
	private ListenElement next;
	
	public ListenElement(String thema) {
		this.thema = thema;
	}

	public String getThema() {
		return thema;
	}

	public ListenElement getNext() {
		return next;
	}

	public void setNext(ListenElement next) {
		this.next = next;
	}
}

Klasse ThemenListe

public class ThemenListe {
	private ListenElement anfang;
	// Groesse der Liste
	private int groesse;

	public boolean beinhaltet(String thema) {
		boolean enthaelt = false;
		ListenElement aktuellePos = anfang;
		while (aktuellePos != null && enthaelt == false) {
			if (aktuellePos.getThema() == thema) {
				enthaelt = true;
			}
			aktuellePos = aktuellePos.getNext();
		}
		return enthaelt;
	}

	public boolean hinzufuegen(String thema) {
		boolean erfolgreich = false;
			ListenElement pos = new ListenElement(thema);
			pos.setNext(anfang);
			anfang = pos;
			erfolgreich = true;
			groesse++;
			return erfolgreich;
	}


	public boolean entfernen(String thema) {
		boolean erfolgreich = false;
		if (beinhaltet(thema) && this.getGroesse() != 0) {

			ListenElement aktuellepos = anfang;
			ListenElement vorherigepos = null;

			while (aktuellepos != null && 
					!aktuellepos.getThema().equals(thema)) {
				vorherigepos = aktuellepos;
				aktuellepos = aktuellepos.getNext();
			}
			if (vorherigepos != null) {
				vorherigepos.setNext(aktuellepos.getNext());
			} else {
				anfang = anfang.getNext();
			}
			erfolgreich = true;
			groesse--;
		}

		return erfolgreich;
	}

	public int getGroesse() {
		return groesse;
	}


	/**
	 * Methode zur Rueckgabe aller Themen in einem Array
	 * 
	 * @return Alle Themen in einen Array gespeichert
	 */
	public String[] getThemen() {
		String[] themen = new String[getGroesse()];
		ListenElement aktuellePos = anfang;
		for (int i = 0; i < getGroesse(); i++) {
			themen[i] = aktuellePos.getThema();
			aktuellePos = aktuellePos.getNext();
		}
		return themen;
	}
}
	

Testklasse

public class test {

	public static void main(String[] args) {

		// Neue Liste erzeugen
		ThemenListe themen = new ThemenListe();

		// Fuegt drei Themen der Liste hinzu
		themen.hinzufuegen("News");
		themen.hinzufuegen("Sport");
		themen.hinzufuegen("Gosship");

		// Loescht ein Thema wieder
		themen.entfernen("Sport");

		// Gibt alle Themen der Liste in einem Array aus
		for (int i = 0; i < themen.getThemen().length; i++) {
			System.out.println(themen.getThemen()[i]);
		}

	}
}