Theoretische Informatik

Verkettete Liste

Inhaltsübersicht

In unserem Video wird dir die verkettete Liste einfach erklärt. Dort erklären wir dir mit Hilfe von Beispielen die einfach verkettete Liste und die doppelt verkettete Liste. Zusätzlich zeigen wir dir wie du innerhalb dieser Form der dynamischen Datenstrukturen unterschiedliche Operationen, wie Suchen, Einfügen und Löschen vornehmen kannst.

In unserem Blogbeitrag findest du zusätzliche Formen der verketteten Listen und auch noch eine einfach verkettete Liste Java-Implementierung, als auch einen doppelt verkettete Liste Java-Quellcode.

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:

L=None | [A, L_{A}]

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.

Verkettete Liste
Verkettete Liste

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 O(n) 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.

Einfach verkettete Liste
Einfach verkettete Liste

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.

Einfach verkettete Liste Einfügen
Einfach verkettete Liste Einfügen

Das Einfügen neuer Elemente lässt sich sehr schnell mit einer Laufzeit von O(1) 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.

Verkettete Liste Löschen
Verkettete Liste Löschen

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 O(1).

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.

doppelt verkettete Liste
Doppelt verkettete Liste

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();

}

}


Andere Nutzer halten diese Inhalte aus dem Bereich „Theoretische Informatik“ für besonders klausurrelevant

Hallo, leider nutzt du einen AdBlocker.

Auf Studyflix bieten wir dir kostenlos hochwertige Bildung an. Dies können wir nur durch die Unterstützung unserer Werbepartner tun.

Schalte bitte deinen Adblocker für Studyflix aus oder füge uns zu deinen Ausnahmen hinzu. Das tut dir nicht weh und hilft uns weiter.

Danke!
Dein Studyflix-Team

Wenn du nicht weißt, wie du deinen Adblocker deaktivierst oder Studyflix zu den Ausnahmen hinzufügst, findest du hier eine kurze Anleitung. Bitte lade anschließend die Seite neu.