Datenstrukturen: Verkettete Listen

Verkettete Listen sind Datenstrukturen, welche aus einzelnen miteinander verknüpften Elementen bestehen. Die Elemente werden Knoten genannt. Jeder dieser Knoten besteht aus einem Wert und einer Referenz zu dem nächsten Knoten in der Liste. Der erste Knoten der Liste wird Kopf oder Head genannt. Über den Head der Liste ist jedes darin enthaltene Element zu erreichen.

Verkettete Listen sind dynamisch erweiterbar. An jeder Stelle der Liste kann ein Element hinzugefügt oder entfernt werden. Dazu müssen lediglich die Referenzen der beteiligten Knoten angepasst werden. Zur besseren Handhabung werden verkettete Listen meist in einer Adapter-Klasse gespeichert. Diese enthält beispielsweise Informationen über die Länge der Liste und erlaubt standardmäßige Listen-Operationen, wie einfügen oder entfernen. Es ist beispielsweise vorteilhaft in der Adapter-Klasse den letzten Knoten einer Liste immer griffbereit zu haben um ein Element an das Ende der Liste einfügen zu können ohne zuerst durch die gesamte Liste itterieren zu müssen.

Doppelt verkettete Liste

Doppelt verkettete Listen besitzen neben der Referenz auf den nächsten Knoten zudem eine Referenz auf den vorherigen Knoten. Damit werden Operationen auf der Liste zwar aufwendiger, es ist jedoch möglich die Liste auch rückwärts zu durchlaufen.

Angeber Wissen

Zwar ist der zusätzliche Speicherplatz kaum der Rede wert, man kann die Vor- und Rückwärtz-Referenz allerdings per XOR-Operation in einer Variable zusammenfassen. Iteriert man durch die Liste muss in diesem Fall nur der Zeiger zum letzten Knoten aufbewart werden. Möchte man zum nächsten Knoten gelangen, so kann dessen Adresse über eine weitere XOR-Operation wieder hergestellt werden.

Ein Nachteil von verketteten Listen ist der Aufwandt bei einem Zugriff auf ein Element in der Liste. Anders als bei einem Array, bei dem direkt auf das gewünschte Element zugegriffen werden kann, muss bei der vergetteten Liste vom Kopf der Liste aus jeder dazwischen liegende Knoten durchlaufen werden. Der Objektzugriff ist damit aufwendiger als bei einem Array.

package com.florianbuchner.library.collection;

public class LinkedList<T> implements List<T> {

	private ListNode firstNode;
	
	private ListNode lastNode;
	
	private int size = 0;
	
	@Override
	public int size() {
		return size;
	}

	@Override
	public T get(int index) {
		return this.getNode(index).value;
	}
	
	private ListNode getNode(int index) {
		if (index >= size || index < 0) {
			throw new IndexOutOfBoundsException();
		}
		if (index - size < 0) {
			int pos = 0;
			ListNode node = this.firstNode;
			while(pos != index) {
				node = node.rightNode;
				pos++;
			}
			return node;
		}
		else {
			int pos = this.size - 1;
			ListNode node = this.lastNode;
			while(pos != index) {
				node = node.leftNode;
				pos--;
			}
			return node;
		}
	}

	@Override
	public T remove(int index) {
		ListNode node = this.getNode(index);
		if (node.rightNode != null) {
			node.rightNode.leftNode = node.leftNode;
		}
		if (node.leftNode != null) {
			node.leftNode.rightNode = node.rightNode;
		}
		
		if (this.size <= 1) {
			this.firstNode = null;
		}
		else if (index == 0) {
			this.firstNode = this.firstNode.rightNode;
		}
		
		if (this.size <= 2) {
			this.lastNode = null;
		}
		else if (index == size -1) {
			this.lastNode = this.lastNode.leftNode;
		}
		
		this.size--;
		return node.value;
	}

	@Override
	public void add(T item) {
		if (this.firstNode == null) {
			this.firstNode = new ListNode(null, null, item);
		}
		else {
			final ListNode node = new ListNode(this.lastNode != null ? this.lastNode : this.firstNode, null, item);
			(this.lastNode != null ? this.lastNode : this.firstNode).rightNode = node;
			this.lastNode = node;
		}
		this.size++;
	}

	@Override
	public void clear() {
		this.firstNode = null;
		this.lastNode = null;
		this.size = 0;
	}

	class ListNode {
		
		public ListNode(ListNode leftNode, ListNode rightNode, T value) {
			this.leftNode = leftNode;
			this.rightNode = rightNode;
			this.value = value;
		}
		
		ListNode leftNode;
		ListNode rightNode;
		T value;
	}
}

Skip-Listen

Skip-Listen sind Listen, welche neben den Referenzen auf das vorherige oder nächste Element zudem Referenzen auf weiter entfernte Elemente besitzen. Damit ist es möglich eine gewisse Anzahl an Iterationen zu überspringen. Skip-Listen können nicht nur eine, sondern mehrere Ebenen von Referenzen besitzen.

Komplexität