Verkettete Liste

Einfach erklärt

Bei der verketteten Liste handelt es sich um eine dynamische Datenstruktur in der Informatik. Heißt also, dass sich die Datenstruktur innerhalb der Laufzeit des Programms an den Speicherbedarf flexibel anpassen kann.  Listen sind im Allgemeinen dazu da, unterschiedliche Datentypen (Integer, String, etc.) abzuspeichern. Eine Liste besteht dabei aus mehreren Bestandteilen. Die wichtigsten sind für uns dabei zum einen der Speicher, auf dem die Elemente abgelegt werden können. Zum anderen aus Zeigern, mit denen man von einem zum nächsten Element navigieren kann. Da es aber möglich ist, dynamische Elemente hinzuzufügen und zu löschen, kann ein Element einer verketteten Liste selbst auch wieder eine Liste oder ein Array sein. Deshalb muss hauptsächlich darauf geachtet werden, dass stets genug Speicher zur Verfügung steht, um einer Liste weitere Elemente hinzuzufügen.

Einfach verkettete Liste

Eine einfach verkettete Liste besteht aus Knoten und Zeigern. In den Knoten werden die Daten hinterlegt – also zum Beispiel Zahlen oder Zeichenketten. In den Zeigern wird auf den unmittelbaren Nachfolger des Elements verwiesen. Das heißt dann auch, dass ein Knoten nur Kenntnisse über diesen einen Nachfolger hat und der Durchlauf entsprechend nur in eine Richtung funktioniert.

Aufbau

Doch wie lässt sich eine einfach verkettete Liste umsetzten? Das geschieht ganz einfach rekursiv:

Eine Liste L ist entweder leer oder sie besteht aus einem Knoten. Dieser enthält dann zum einen ein Objekt vom Datentyp A, und zum anderen einen Verweis auf eine Liste desselben Typs. Der Zeiger des letzten Elements einer Liste wird auch Nullzeiger genannt. Er zeigt auf die leere Liste.

direkt ins Video springen

Operationen

Innerhalb von verketteten Listen können natürlich auch unterschiedliche Operationen vorgenommen werden. Zum einen die allgemeine Suche innerhalb der Listen, als auch das Einfügen neuer Werte. Des Weiteren kann man auch Elemente aus den verketteten Listen löschen.

Suchen

Bei der Suche innerhalb einer einfach verketteten Liste, muss jedes einzelne Element nacheinander durchlaufen werden, bis das tatsächlich gesuchte Objekt gefunden wird, oder wir bereits am Ende der Liste angekommen sind. Entsprechend zeigt die Laufzeitkomplexität ein langsames Ergebnis von auf.

Einfügen

Wenn ein Element in eine Liste eingefügt werden soll, muss zunächst ein Speicherplatz reserviert werden, welcher dann dynamisch zugeordnet werden kann.

Innerhalb des folgenden Beispiels soll am Ende der Liste eine 44 eingefügt werden. Der Zeiger weist ins Leere, weshalb nur noch den Zeiger des Vorgängers auf das neue Element gerichtet werden muss.

direkt ins Video springen

Soll ein Element in der Mitte einfügt werden – zum Beispiel die 33 zwischen 22 und 44 –, dann muss sich zunächst der Zeiger des neuen Elements auf seinen Nachfolger richten. Im Anschluss wird dann der Vorgängerzeiger umgehängt.

direkt ins Video springen

Das Einfügen neuer Elemente lässt sich sehr schnell mit einer Laufzeit von realisieren.

Verkettete Liste löschen

Das Löschen von Elementen funktioniert ganz ähnlich. Will man die 44 am Ende löschen, dann muss nur der Vorgängerzeiger von der 33 in einen Nullzeiger umwandelt und anschließend der bisher belegte Speicherplatz freigeben werden.

Beim Löschen eines mittleren Elements – hier der 22 – wird zuerst der Zeiger des Vorgängers 11 auf den Nachfolger 33 gerichtet. Erst danach darf man den Zeiger von der 22 zur 33 entfernen. Zum Schluss wird auch hier der Speicher wieder freigegeben.

direkt ins Video springen

Stack und Kellerautomat

Wenn wir als Basisoperationen das Einfügen und Löschen nur des jeweils ersten Elementes einer Liste zulassen, dann haben wir nichts anderes als einen Kellerspeicher. Wie man diesen in einen Kellerautomat einsetzt, zeigen wir dir in diesem Video. Ein solcher Kellerspeicher speichert und löscht in .

Doppelt verkettete Liste

Wenn sich die Liste nun noch zusätzlich um einen Verweis auf den Vorgängerknoten erweitert, dann entsteht daraus eine doppelt verkettete Liste. Folglich gibt es in solchen Listen noch einen zweiten Nullzeiger: Den, der vom ersten Element auf seinen Vorzeiger zeigt.

direkt ins Video springen

Doppelt verkettete Listen haben gegenüber einfach verketteten einerseits den Vorteil, dass sie sich auch von hinten nach vorne durchsuchen lassen. Außerdem lässt sich ein Knoten schneller löschen, weil der Vorgängerknoten bekannt ist – bei einfach verketteten Listen kennt ein Knoten ja nur den Nachfolger! Andererseits muss der Vorgängerzeiger zusätzlich gespeichert und beim Löschen und Einfügen angepasst werden.

Weitere Formen

Es gibt aber auch noch weitere Formen der verketteten Listen:

• Listenkopf: Datenfeld mit zusätzlichen Informationen, welches auf das erste Element zeigt.
• Skip-Liste: Beschleunigen die Suche in sortierten verketteten Listen durch zusätzliche Zeiger.
• Adaptive Listen: Unterscheidet sich in drei Strategien
  • MoveToFront: Bei einem Zugriff auf ein Objekt wird dieses entfernt und wiederum am Anfang der Liste wieder eingefügt.
  • Transpose: Elemente werden beim Zugriff mit ihrem Vorgänger vertauscht.
  • Gratification: Zusätzliche Speichreung von Zugriffshäufigkeit.
• Listen in der objektorientierten Programmierung:

Einfach verkettete Liste Java

Im Folgenden zeigt sich ein einfach verkette Liste Java-Code. Die Implementierung wird zur besseren Übersicht in zwei Klassen aufgeteilt.

Klasse Element

class Element {

Object objekt;

element nachfolger;

public element(Object objekt) {

this.objekt= objekt;

nachfolger = null;

}

public void setnachfolger(element nachfolger) {

this.nachfolger = nachfolger;

}

public element getnachfolger() {

return nachfolger;

}

public Object geto() {

return objekt;

}

}

Klasse verkettete Liste

public class EinfachVerketteteListeJava {

element startelement = new element(„Kopf“);

public EinfachVerketteteListeJava() {}

public void letzteHinzufuegen(Object o){

element newElem = new element(o);

element lastElem = getletztesElement();

letztesElement.setnachfolger(neuesElement);

}

public void danachEinfuegen(Object vorgaenger, Object neuItem) {

element neuesElement, nachfolger, pointerElem;

pointerElem = startelement.getnachfolger();

while(pointerElem != null && !pointerElem.getObj().equals(pItem)){

pointerElem = pointerElem.getnachfolger();

}

neuesElement = new element(neuItem);

nachfolger = pointerElem.getnachfolger();

pointerElem.setnachfolger(neuesElement);

neuesElement.setnachfolger(nachfolger);

}

public void loeschen (Object o){

element l = startelement;

while (l.getnachfolger() != null && !l.getObj().equals(o)){

if(l.getnachfolger().getObjekt().equals(o)){

if(l.getnachfolger().getnachfolger()!=null)

l.setnachfolger(l.getnachfolger().getnachfolger());

else{

l.setnachfolger(null);

break;

}

}

l = l.getnachfolger();

}

}

public boolean finden(Object o){

element l = startelement;

while (l != null){

if(l.getObjekt().equals(o))

return true;

l = l.nachfolger;

}

return false;

}

public element geterstesElement() {

return startelement;

}

public element getletztesElement() {

element l = startelement;

while(l.getnachfolger() != null){

l = l.getnachfolger();

}

return l;

}

public void liste() {

element l = startelement;

while(l != null){

System.out.println(l.getObjekt());

le = le.getNextElem();

}

}

public static void main(String[] args) {

EinfachVerketteteListeJava liste = new EinfachVerketteteListeJava();

list.addLast(„1“);

list.addLast(„2“);

list.addLast(„3“);

list.addLast(„4“);

list.addLast(„5“);

list.danachEinfuegen(„2“, „neu“);

list.loeschen(„3“);

list.liste();

System.out.println(„erstes Element: “ + liste.geterstesElement().getObjekt());

System.out.println(„ist ‚3‘ enthalten? “ + liste.finden(„3“));

System.out.println(„ist ‚5‘ enthalten? “ + liste.finden(„5“));

System.out.println(„letztes Element: “ + liste.getletztesElement().getObjekt());

}

}

Doppelt verkettete Liste Java

Hier findest du ein Beispiel für eine doppelt verkettete Liste Java-Implementierung. Da eine Liste aus einzelnen Elementen und dem Knoten besteht, wird der Code in die folgenden Klassen unterteilt.

Klasse Knoten

class Knoten {

Object objekt;

ListElement nachfolger, vorgaenger;

public Knoten (Object objekt) {

this.objekt = objekt;

nachfolger = null;

}

public void setnachfolger(ListElement nachfolger) {

this.nachfolger = nachfolger;

}

public void setvorgaenger(ListElement vorgaenger) {

this.vorgaenger = vorgaenger;

}

public ListElement getnachfolger() {

return nachfolger;

}

public ListElement getvorgaenger() {

return this.vorgaenger;

}

public Object geto() {

return objekt;

}

}

Klasse Listenimplementierung

public class DoppeltVerketteteListeJava {

ListElement startelement = new ListElement(„Anfang“);

ListElement endelement = new ListElement(„Ende“);

public DoppeltVerketteteListeJava() {

startelement.setnachfolger(endelement);

endelement.setvorgaenger(startelement);

}

public void addletztesElement(Object o){

ListElement neuesElement = new ListElement(o);

ListElement letztesElement = getletztesElement();

letztesElement.setnachfolger(neuesElement);

neuesElement.setvorgaenger(letztesElement);

}

public void danachEinfuegen (Object vorgaengerItem, Object neuItem) {

ListElement neuesElement, nachfolger = null, pointerElem;

pointerElem = startelement.getnachfolger();

while(pointerElem != null && !pointerElem.getObj().equals(vorgaengerItem)){

pointerElem = pointerElem.getnachfolger();

}

neuesElement = new ListElement(neuItem);

if(pointerElem != null){

nachfolger = pointerElem.getnachfolger();

pointerElem.setnachfolger(nachfolger);

nachfolger.setnachfolger(nachfolger);

neuesElement.setvorgaenger(pointerElem);

}

if(neuesElement != null)

nachfolger.setPrevElem(neuesElement);

}

public void davorEinfuegen (Object itemEinfuegen, Object neuItem){

ListElement neuesElement, pointerElem;

neuesElement = new ListElement(neuItem);

pointerElem = startelement.getnachfolger();

while(pointerElem != null){

if(pointerElem.getObj().equals(itemEinfuegen)){

neuesElement.setVorgaenger(pointerElem.getVorgaenger());

pointerElem.getVorgaenger().setneuesElement(neuesElement);

pointerElem.setvorgaenger(neuesElement);

neuesElement.setnachfolger(pointerElem);

break;

}

pointerElem = pointerElem.getnachfolger();

}

}

public void loeschen (Object o){

ListElement l = startelement;

while (l.getnachfolger() != null && !l.getObj().equals(o)){

if(l.getnachfolger().getObj().equals(o)){

if(l.getnachfolger().getnachfolger()!=null){

l.setnachfolger(l.getnachfolger().getnachfolger());

l.getnachfolger().setvorgaenger(l);

}else{

l.setnachfolger(null);

break;

}

}

l = l.getnachfolger();

}

}

public boolean find(Object o){

ListElement l = startelement;

while (l != null){

if(l.getObj().equals(o))

return true;

l = l.nachfolger;

}

return false;

}

public ListElement geterstesElement() {

return startelement;

}

public ListElement getletztesElement() {

ListElement l = startelement;

while(l.getnachfolger() != null){

l = l.getnachfolger();

}

return l;

}

public void liste() {

ListElement l = startelement;

while(l != null){

System.out.println(l.getObj());

l = l.getnachfolger();

}

}

public static void main(String[] args) {

DoppeltVerketteteListeJava list = new DoppeltVerketteteListeJava();

list.addLast(„1“);

list.addLast(„2“);

list.addLast(„3“);

list.addLast(„4“);

list.addLast(„5“);

list.insertAfter(„2“, „nach 2“);

list.loeschen(„4“);

list.davorEinfuegen(„3“, „vor 3“);

System.out.println(„erstes Element: “ + liste.getFirstElem().getObjekt());

System.out.println(„ist ‚4‘ enthalten? “ + liste.find(„4“));

System.out.println(„ist ‚5‘ enthalten? “ + liste.find(„5“));

System.out.println(„letztes Element: “ + liste.getLastElem().getObj());

System.out.println(„vorletztes Element: “ + liste.getletztesElement().getvorgaenger().getObjekt());

liste.liste();

}

}