Verkettete Liste: Unterschied zwischen den Versionen

Aus KGS-Wiki
(Seite angelegt, muss noch erweitert werden)
 
(Endlich nicht mehr lückenhaft.)
 
(7 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt)
Zeile 8: Zeile 8:
Die einfachsten Fälle sind die leere Liste:
Die einfachsten Fälle sind die leere Liste:


<uml>
<graphviz format="svg">
@startuml
digraph EmptyList {
hide empty description
fontname="Source Sans Pro,Linux Biolinum,Helvetica,Arial,sans-serif"
skinparam linetype ortho
node [fontname="Source Sans Pro,Linux Biolinum,Helvetica,Arial,sans-serif"]
state List1 {
edge [fontname="Source Sans Pro,Linux Biolinum,Helvetica,Arial,sans-serif"]
state "head" as h1
    layout="neato";
h1: null
    subgraph cluster_empty {
state "tail" as t1
        head [label=<<TABLE BORDER="0" CELLSPACING="0" CELLBORDER="1"><TR><TD>head</TD><TD>null</TD></TR></TABLE>>, shape="none", pos="0,0!"];
t1: null
        tail [label=<<TABLE BORDER="0" CELLSPACING="0" CELLBORDER="1"><TR><TD>tail</TD><TD>null</TD></TR></TABLE>>, shape="none", pos="1,0!"];
h1 -[hidden]right-> t1
    }
}
}
@enduml
</graphviz>
</uml>
 
... und eine einelementige Liste:
... und eine einelementige Liste:


<uml>
<graphviz format="svg">
@startuml
digraph ListOneElement {
hide empty description
fontname="Source Sans Pro,Linux Biolinum,Helvetica,Arial,sans-serif"
skinparam linetype ortho
node [fontname="Source Sans Pro,Linux Biolinum,Helvetica,Arial,sans-serif"]
state List1 {
edge [fontname="Source Sans Pro,Linux Biolinum,Helvetica,Arial,sans-serif"]
state "head" as h1
    layout="neato";
h1: 42
    compound="true";
state "tail" as t1
    subgraph cluster_node {
t1: null
        nodeLabel [label="Element 1", shape="plaintext", pos="0.5,0.5!"];
h1 -[hidden]right-> t1
        head [label=<<TABLE BORDER="0" CELLSPACING="0" CELLBORDER="1"><TR><TD>head</TD><TD>42</TD></TR></TABLE>>, shape="none", pos="0,0!"];
        tail [label=<<TABLE BORDER="0" CELLSPACING="0" CELLBORDER="1"><TR><TD>tail</TD><TD>null</TD></TR></TABLE>>, shape="none", pos="1,0!"];
    }
}
}
@enduml
</graphviz>
</uml>


An diese Liste können nun weitere Elemente angefügt werden, indem schrittweise neue Listen erzeugt werden:
An diese Liste können nun weitere Elemente angefügt werden, indem schrittweise neue Listen erzeugt werden:


<uml>
<graphviz format="svg">
@startuml
digraph ListTwoElements {
hide empty description
    compound="true"
skinparam linetype ortho
fontname="Source Sans Pro,Linux Biolinum,Helvetica,Arial,sans-serif"
state List1 {
node [fontname="Source Sans Pro,Linux Biolinum,Helvetica,Arial,sans-serif"]
state "head" as h1
edge [fontname="Source Sans Pro,Linux Biolinum,Helvetica,Arial,sans-serif"]
h1: 42
    layout="neato";
state "tail" as t1
    subgraph cluster_node1 {
h1 -[hidden]right-> t1
        nodeLabel1 [label="Element 1", shape="plaintext", pos="0.5,0.5!"];
        head1 [label=<<TABLE BORDER="0" CELLSPACING="0" CELLBORDER="1"><TR><TD>head</TD><TD>42</TD></TR></TABLE>>, shape="none", pos="0,0!"];
        tail1 [label=<<TABLE BORDER="0" CELLSPACING="0" CELLBORDER="1"><TR><TD>tail</TD><TD PORT="ptr">&nbsp;</TD></TR></TABLE>>, shape="none", pos="1,0!"];
    }
    subgraph cluster_node2 {
        nodeLabel2 [label="Element 2", shape="plaintext", pos="3.5,0.5!"];
        head2 [label=<<TABLE BORDER="0" CELLSPACING="0" CELLBORDER="1"><TR><TD>head</TD><TD>23</TD></TR></TABLE>>, shape="none", pos="3,0!"];
        tail2 [label=<<TABLE BORDER="0" CELLSPACING="0" CELLBORDER="1"><TR><TD>tail</TD><TD>null</TD></TR></TABLE>>, shape="none", pos="4,0!"];
    }
    tail1:ptr -> head2 [lhead="cluster_node2"];
}
</graphviz>
 
Ein Element nach dem anderen:
 
<graphviz format="svg">
digraph ListThreeElements {
    compound="true"
fontname="Source Sans Pro,Linux Biolinum,Helvetica,Arial,sans-serif"
node [fontname="Source Sans Pro,Linux Biolinum,Helvetica,Arial,sans-serif"]
edge [fontname="Source Sans Pro,Linux Biolinum,Helvetica,Arial,sans-serif"]
    layout="neato";
    subgraph cluster_node1 {
        nodeLabel1 [label="Element 1", shape="plaintext", pos="0.5,0.5!"];
        head1 [label=<<TABLE BORDER="0" CELLSPACING="0" CELLBORDER="1"><TR><TD>head</TD><TD>42</TD></TR></TABLE>>, shape="none", pos="0,0!"];
        tail1 [label=<<TABLE BORDER="0" CELLSPACING="0" CELLBORDER="1"><TR><TD>tail</TD><TD PORT="ptr">&nbsp;</TD></TR></TABLE>>, shape="none", pos="1,0!"];
    }
    subgraph cluster_node2 {
        nodeLabel2 [label="Element 2", shape="plaintext", pos="3.5,0.5!"];
        head2 [label=<<TABLE BORDER="0" CELLSPACING="0" CELLBORDER="1"><TR><TD>head</TD><TD>23</TD></TR></TABLE>>, shape="none", pos="3,0!"];
        tail2 [label=<<TABLE BORDER="0" CELLSPACING="0" CELLBORDER="1"><TR><TD>tail</TD><TD PORT="ptr">&nbsp;</TD></TR></TABLE>>, shape="none", pos="4,0!"];
    }
    subgraph cluster_node3 {
        nodeLabel3 [label="Element 3", shape="plaintext", pos="6.5,0.5!"];
        head3 [label=<<TABLE BORDER="0" CELLSPACING="0" CELLBORDER="1"><TR><TD>head</TD><TD>69</TD></TR></TABLE>>, shape="none", pos="6,0!"];
        tail3 [label=<<TABLE BORDER="0" CELLSPACING="0" CELLBORDER="1"><TR><TD>tail</TD><TD PORT="ptr">null</TD></TR></TABLE>>, shape="none", pos="7,0!"];
    }
    tail1:ptr -> head2 [lhead="cluster_node2"];
    tail2:ptr -> head3 [lhead="cluster_node3"];
}
</graphviz>
 
== Operationen ==
 
=== Suchen ===
Selbst wenn die Liste sortiert ist, kann nur dadurch nach Elementen suchen, dass man die ganze Liste von vorn nach hinten durchgeht. Da jedes Element nur mit seinem direkten Nachfolger verbunden ist, können auch keine Algorithmen wie die [[Binäre Suche]] eingesetzt werden. Die Suche in einer verketteten Liste hat damit eine [[Laufzeit]] in {{O|n}}.
 
=== Einfügen ===
 
Am Ende einer Liste kann man einfach ein neues Element anfügen, indem man ein neues Listen-Objekt mit einem Eintrag erzeugt:
 
<graphviz format="svg">
digraph ListThreeElementsPlusNew {
    compound="true"
fontname="Source Sans Pro,Linux Biolinum,Helvetica,Arial,sans-serif"
node [fontname="Source Sans Pro,Linux Biolinum,Helvetica,Arial,sans-serif"]
edge [fontname="Source Sans Pro,Linux Biolinum,Helvetica,Arial,sans-serif"]
    layout="neato";
    subgraph cluster_node1 {
        nodeLabel1 [label="Element 1", shape="plaintext", pos="0.5,0.5!"];
        head1 [label=<<TABLE BORDER="0" CELLSPACING="0" CELLBORDER="1"><TR><TD>head</TD><TD>42</TD></TR></TABLE>>, shape="none", pos="0,0!"];
        tail1 [label=<<TABLE BORDER="0" CELLSPACING="0" CELLBORDER="1"><TR><TD>tail</TD><TD PORT="ptr">&nbsp;</TD></TR></TABLE>>, shape="none", pos="1,0!"];
    }
    subgraph cluster_node2 {
        nodeLabel2 [label="Element 2", shape="plaintext", pos="3.5,0.5!"];
        head2 [label=<<TABLE BORDER="0" CELLSPACING="0" CELLBORDER="1"><TR><TD>head</TD><TD>23</TD></TR></TABLE>>, shape="none", pos="3,0!"];
        tail2 [label=<<TABLE BORDER="0" CELLSPACING="0" CELLBORDER="1"><TR><TD>tail</TD><TD PORT="ptr">&nbsp;</TD></TR></TABLE>>, shape="none", pos="4,0!"];
    }
    subgraph cluster_node3 {
        nodeLabel3 [label="Element 3", shape="plaintext", pos="6.5,0.5!"];
        head3 [label=<<TABLE BORDER="0" CELLSPACING="0" CELLBORDER="1"><TR><TD>head</TD><TD>69</TD></TR></TABLE>>, shape="none", pos="6,0!"];
        tail3 [label=<<TABLE BORDER="0" CELLSPACING="0" CELLBORDER="1"><TR><TD>tail</TD><TD>null</TD></TR></TABLE>>, shape="none", pos="7,0!"];
    }
    subgraph cluster_new {
        bgcolor="#00B169"
        nodeLabel4 [label="Neues Element", shape="plaintext", pos="9.5,0.5!"];
        head4 [label=<<TABLE BORDER="0" CELLSPACING="0" CELLBORDER="1"><TR><TD>head</TD><TD>1337</TD></TR></TABLE>>, shape="none", pos="9,0!"];
        tail4 [label=<<TABLE BORDER="0" CELLSPACING="0" CELLBORDER="1"><TR><TD>tail</TD><TD>null</TD></TR></TABLE>>, shape="none", pos="10,0!"];
    }
    tail1:ptr -> head2 [lhead="cluster_node2"];
    tail2:ptr -> head3 [lhead="cluster_node3"];
}
</graphviz>
 
... und dann den <code>tail</code> des letzten Listenelements darauf zeigen lässt.
 
<graphviz format="svg">
digraph ListThreeElementsNewAdded {
    compound="true"
fontname="Source Sans Pro,Linux Biolinum,Helvetica,Arial,sans-serif"
node [fontname="Source Sans Pro,Linux Biolinum,Helvetica,Arial,sans-serif"]
edge [fontname="Source Sans Pro,Linux Biolinum,Helvetica,Arial,sans-serif"]
    layout="neato";
    subgraph cluster_node1 {
        nodeLabel1 [label="Element 1", shape="plaintext", pos="0.5,0.5!"];
        head1 [label=<<TABLE BORDER="0" CELLSPACING="0" CELLBORDER="1"><TR><TD>head</TD><TD>42</TD></TR></TABLE>>, shape="none", pos="0,0!"];
        tail1 [label=<<TABLE BORDER="0" CELLSPACING="0" CELLBORDER="1"><TR><TD>tail</TD><TD PORT="ptr">&nbsp;</TD></TR></TABLE>>, shape="none", pos="1,0!"];
    }
    subgraph cluster_node2 {
        nodeLabel2 [label="Element 2", shape="plaintext", pos="3.5,0.5!"];
        head2 [label=<<TABLE BORDER="0" CELLSPACING="0" CELLBORDER="1"><TR><TD>head</TD><TD>23</TD></TR></TABLE>>, shape="none", pos="3,0!"];
        tail2 [label=<<TABLE BORDER="0" CELLSPACING="0" CELLBORDER="1"><TR><TD>tail</TD><TD PORT="ptr">&nbsp;</TD></TR></TABLE>>, shape="none", pos="4,0!"];
    }
    subgraph cluster_node3 {
        nodeLabel3 [label="Element 3", shape="plaintext", pos="6.5,0.5!"];
        head3 [label=<<TABLE BORDER="0" CELLSPACING="0" CELLBORDER="1"><TR><TD>head</TD><TD>69</TD></TR></TABLE>>, shape="none", pos="6,0!"];
        tail3 [label=<<TABLE BORDER="0" CELLSPACING="0" CELLBORDER="1" BGCOLOR="#00B169"><TR><TD>tail</TD><TD PORT="PTR">&nbsp;</TD></TR></TABLE>>, shape="none", pos="7,0!"];
    }
    subgraph cluster_new {
        bgcolor="#00B169"
        nodeLabel4 [label="Neues Element", shape="plaintext", pos="9.5,0.5!"];
        head4 [label=<<TABLE BORDER="0" CELLSPACING="0" CELLBORDER="1"><TR><TD>head</TD><TD>1337</TD></TR></TABLE>>, shape="none", pos="9,0!"];
        tail4 [label=<<TABLE BORDER="0" CELLSPACING="0" CELLBORDER="1"><TR><TD>tail</TD><TD>null</TD></TR></TABLE>>, shape="none", pos="10,0!"];
    }
    tail1:ptr -> head2 [lhead="cluster_node2"];
    tail2:ptr -> head3 [lhead="cluster_node3"];
    tail3:ptr -> head4 [lhead="cluster_new", color="#00B169"];
}
}
state List2 {
</graphviz>
state "head" as h2
 
h2: 23
 
state "tail" as t2
In der Mitte einer Liste kann man einfach ein neues Element anfügen, indem man ein neues Listen-Objekt mit einem Eintrag erzeugt:
t2: null
 
h2 -[hidden]right-> t2
<graphviz format="svg">
digraph ListThreeElementsPlusNew {
    compound="true"
fontname="Source Sans Pro,Linux Biolinum,Helvetica,Arial,sans-serif"
node [fontname="Source Sans Pro,Linux Biolinum,Helvetica,Arial,sans-serif"]
edge [fontname="Source Sans Pro,Linux Biolinum,Helvetica,Arial,sans-serif"]
    layout="neato";
    subgraph cluster_node1 {
        nodeLabel1 [label="Element 1", shape="plaintext", pos="0.5,0.5!"];
        head1 [label=<<TABLE BORDER="0" CELLSPACING="0" CELLBORDER="1"><TR><TD>head</TD><TD>42</TD></TR></TABLE>>, shape="none", pos="0,0!"];
        tail1 [label=<<TABLE BORDER="0" CELLSPACING="0" CELLBORDER="1"><TR><TD>tail</TD><TD PORT="ptr">&nbsp;</TD></TR></TABLE>>, shape="none", pos="1,0!"];
    }
    subgraph cluster_node2 {
        nodeLabel2 [label="Element 2", shape="plaintext", pos="3.5,0.5!"];
        head2 [label=<<TABLE BORDER="0" CELLSPACING="0" CELLBORDER="1"><TR><TD>head</TD><TD>23</TD></TR></TABLE>>, shape="none", pos="3,0!"];
        tail2 [label=<<TABLE BORDER="0" CELLSPACING="0" CELLBORDER="1"><TR><TD>tail</TD><TD PORT="ptr">&nbsp;</TD></TR></TABLE>>, shape="none", pos="4,0!"];
    }
    subgraph cluster_node3 {
        nodeLabel3 [label="Element 3", shape="plaintext", pos="6.5,0.5!"];
        head3 [label=<<TABLE BORDER="0" CELLSPACING="0" CELLBORDER="1"><TR><TD>head</TD><TD>69</TD></TR></TABLE>>, shape="none", pos="6,0!"];
        tail3 [label=<<TABLE BORDER="0" CELLSPACING="0" CELLBORDER="1"><TR><TD>tail</TD><TD>null</TD></TR></TABLE>>, shape="none", pos="7,0!"];
    }
    subgraph cluster_new {
        bgcolor="#00B169"
        nodeLabel4 [label="Neues Element", shape="plaintext", pos="2,-1!"];
        head4 [label=<<TABLE BORDER="0" CELLSPACING="0" CELLBORDER="1"><TR><TD>head</TD><TD>1337</TD></TR></TABLE>>, shape="none", pos="1.5,-1.5!"];
        tail4 [label=<<TABLE BORDER="0" CELLSPACING="0" CELLBORDER="1"><TR><TD>tail</TD><TD>null</TD></TR></TABLE>>, shape="none", pos="2.5,-1.5!"];
    }
    tail1:ptr -> head2 [lhead="cluster_node2"];
    tail2:ptr -> head3 [lhead="cluster_node3"];
}
}
t1 --right--> List2
</graphviz>
@enduml
</uml>


<uml>
... und dann den <code>tail</code> des vorhergehenden Listenelements darauf zeigen lässt. Damit das Ende der alten Liste nicht verloren geht, muss auch der <code>tail</code> des neu eingefügten Elements entsprechend gesetzt werden.
@startuml
 
hide empty description
<graphviz format="svg">
skinparam linetype ortho
digraph ListThreeElementsPlusNew {
state List1 {
    compound="true"
state "head" as h1
fontname="Source Sans Pro,Linux Biolinum,Helvetica,Arial,sans-serif"
h1: 42
node [fontname="Source Sans Pro,Linux Biolinum,Helvetica,Arial,sans-serif"]
state "tail" as t1
edge [fontname="Source Sans Pro,Linux Biolinum,Helvetica,Arial,sans-serif"]
h1 -[hidden]right-> t1
    layout="neato";
    subgraph cluster_node1 {
        nodeLabel1 [label="Element 1", shape="plaintext", pos="0.5,0.5!"];
        head1 [label=<<TABLE BORDER="0" CELLSPACING="0" CELLBORDER="1"><TR><TD>head</TD><TD>42</TD></TR></TABLE>>, shape="none", pos="0,0!"];
        tail1 [label=<<TABLE BORDER="0" CELLSPACING="0" CELLBORDER="1" BGCOLOR="#00B169"><TR><TD>tail</TD><TD PORT="ptr">&nbsp;</TD></TR></TABLE>>, shape="none", pos="1,0!"];
    }
    subgraph cluster_node2 {
        nodeLabel2 [label="Element 2", shape="plaintext", pos="3.5,0.5!"];
        head2 [label=<<TABLE BORDER="0" CELLSPACING="0" CELLBORDER="1"><TR><TD>head</TD><TD>23</TD></TR></TABLE>>, shape="none", pos="3,0!"];
        tail2 [label=<<TABLE BORDER="0" CELLSPACING="0" CELLBORDER="1"><TR><TD>tail</TD><TD PORT="ptr">&nbsp;</TD></TR></TABLE>>, shape="none", pos="4,0!"];
    }
    subgraph cluster_node3 {
        nodeLabel3 [label="Element 3", shape="plaintext", pos="6.5,0.5!"];
        head3 [label=<<TABLE BORDER="0" CELLSPACING="0" CELLBORDER="1"><TR><TD>head</TD><TD>69</TD></TR></TABLE>>, shape="none", pos="6,0!"];
        tail3 [label=<<TABLE BORDER="0" CELLSPACING="0" CELLBORDER="1"><TR><TD>tail</TD><TD>null</TD></TR></TABLE>>, shape="none", pos="7,0!"];
    }
    subgraph cluster_new {
        bgcolor="#00B169"
        nodeLabel4 [label="Neues Element", shape="plaintext", pos="2,-1!"];
        head4 [label=<<TABLE BORDER="0" CELLSPACING="0" CELLBORDER="1"><TR><TD>head</TD><TD>1337</TD></TR></TABLE>>, shape="none", pos="1.5,-1.5!"];
        tail4 [label=<<TABLE BORDER="0" CELLSPACING="0" CELLBORDER="1"><TR><TD>tail</TD><TD PORT="PTR">&nbsp;</TD></TR></TABLE>>, shape="none", pos="2.5,-1.5!"];
    }
    tail1:ptr -> nodeLabel4:nw [lhead="cluster_new", color="#00B169"];
    tail4:ptr -> head2 [lhead="cluster_node2", color="black;0.7:#00B169"];
    tail2:ptr -> head3 [lhead="cluster_node3"];
}
}
state List2 {
</graphviz>
state "head" as h2
 
h2: 23
=== Entfernen ===
state "tail" as t2
 
h2 -[hidden]right-> t2
Ein Element entfernt man einfach, indem man den <code>tail</code> von dessen Vorgänger auf dessen Nachfolger zeigen lässt. Für die Liste ist dieses Element dann nicht mehr existent. In den meisten modernen [[Programmiersprache]]n springt außerdem, sobald keine [[Referenz]]en mehr auf ein [[Objekt (Informatik)|Objekt]] zeigen, ein Mechanismus namens ''Garbage Collection'' an. Dieses Objekt, auf das nun nicht mehr aus dem Programm heraus zugegriffen werden kann, wird dann aus dem Speicher gelöscht.
 
<graphviz format="svg">
digraph ListThreeElements {
    compound="true"
fontname="Source Sans Pro,Linux Biolinum,Helvetica,Arial,sans-serif"
node [fontname="Source Sans Pro,Linux Biolinum,Helvetica,Arial,sans-serif"]
edge [fontname="Source Sans Pro,Linux Biolinum,Helvetica,Arial,sans-serif"]
    layout="neato";
    subgraph cluster_node1 {
        nodeLabel1 [label="Element 1", shape="plaintext", pos="0.5,0.5!"];
        head1 [label=<<TABLE BORDER="0" CELLSPACING="0" CELLBORDER="1"><TR><TD>head</TD><TD>42</TD></TR></TABLE>>, shape="none", pos="0,0!"];
        tail1 [label=<<TABLE BORDER="0" CELLSPACING="0" CELLBORDER="1"><TR><TD>tail</TD><TD PORT="ptr">&nbsp;</TD></TR></TABLE>>, shape="none", pos="1,0!"];
    }
    subgraph cluster_node2 {
        nodeLabel2 [label="Element 2", shape="plaintext", pos="3.5,0.5!"];
        head2 [label=<<TABLE BORDER="0" CELLSPACING="0" CELLBORDER="1"><TR><TD>head</TD><TD>23</TD></TR></TABLE>>, shape="none", pos="3,0!"];
        tail2 [label=<<TABLE BORDER="0" CELLSPACING="0" CELLBORDER="1"><TR><TD>tail</TD><TD PORT="ptr">&nbsp;</TD></TR></TABLE>>, shape="none", pos="4,0!"];
    }
    subgraph cluster_node3 {
        nodeLabel3 [label="Element 3", shape="plaintext", pos="6.5,0.5!"];
        head3 [label=<<TABLE BORDER="0" CELLSPACING="0" CELLBORDER="1"><TR><TD>head</TD><TD>69</TD></TR></TABLE>>, shape="none", pos="6,0!"];
        tail3 [label=<<TABLE BORDER="0" CELLSPACING="0" CELLBORDER="1"><TR><TD>tail</TD><TD PORT="ptr">null</TD></TR></TABLE>>, shape="none", pos="7,0!"];
    }
    tail1:ptr -> head2 [lhead="cluster_node2"];
    tail2:ptr -> head3 [lhead="cluster_node3"];
}
}
state List3 {
</graphviz>
state "head" as h3
 
h3: 69
<graphviz format="svg">
state "tail" as t3
digraph ListThreeElementsOneRemoved {
h3 -[hidden]right-> t3
    compound="true"
t3: null
    splines="curved"
fontname="Source Sans Pro,Linux Biolinum,Helvetica,Arial,sans-serif"
node [fontname="Source Sans Pro,Linux Biolinum,Helvetica,Arial,sans-serif"]
edge [fontname="Source Sans Pro,Linux Biolinum,Helvetica,Arial,sans-serif"]
    layout="neato";
    subgraph cluster_node1 {
        nodeLabel1 [label="Element 1", shape="plaintext", pos="0.5,0.5!"];
        head1 [label=<<TABLE BORDER="0" CELLSPACING="0" CELLBORDER="1"><TR><TD>head</TD><TD>42</TD></TR></TABLE>>, shape="none", pos="0,0!"];
        tail1 [label=<<TABLE BORDER="0" CELLSPACING="0" CELLBORDER="1" BGCOLOR="#00B169"><TR><TD>tail</TD><TD PORT="ptr">&nbsp;</TD></TR></TABLE>>, shape="none", pos="1,0!"];
    }
    subgraph cluster_node2 {
        nodeLabel2 [label="Element 2", shape="plaintext", pos="3.5,0.5!"];
        head2 [label=<<TABLE BORDER="0" CELLSPACING="0" CELLBORDER="1"><TR><TD>head</TD><TD>23</TD></TR></TABLE>>, shape="none", pos="3,0!"];
        tail2 [label=<<TABLE BORDER="0" CELLSPACING="0" CELLBORDER="1"><TR><TD>tail</TD><TD PORT="ptr">&nbsp;</TD></TR></TABLE>>, shape="none", pos="4,0!"];
    }
    subgraph cluster_node3 {
        nodeLabel3 [label="Element 3", shape="plaintext", pos="6.5,0.5!"];
        head3 [label=<<TABLE BORDER="0" CELLSPACING="0" CELLBORDER="1"><TR><TD>head</TD><TD>69</TD></TR></TABLE>>, shape="none", pos="6,0!"];
        tail3 [label=<<TABLE BORDER="0" CELLSPACING="0" CELLBORDER="1"><TR><TD>tail</TD><TD PORT="ptr">null</TD></TR></TABLE>>, shape="none", pos="7,0!"];
    }
    tail1:ptr -> head3 [lhead="cluster_node3", color="#00B169"];
    tail2:ptr -> head3 [lhead="cluster_node3"];
}
}
t1 --right--> List2
</graphviz>
t2 --right--> List3
 
@enduml
Dass der <code>tail</code> von Element 2 weiterhin auf Element 3 zeigt, ist nicht weiter tragisch. Element 2 ist trotzdem aus der Liste verschwunden, weil es keinen Weg mehr gibt, zu Element 2 hin zu navigieren. Dem Verweis von Element 2 auf Element 3 kann man nicht rückwärts folgen.
</uml>


{{Lückenhaft}}
==Zum Weiterlesen==
* {{Inf-Schule|2.3.6.2.3|Einfach verkettete Listen}}
* {{VisuAlgo|list|Linked List}}


[[Kategorie:Datenstrukturen]]
[[Kategorie:Datenstrukturen]]

Aktuelle Version vom 25. September 2024, 20:09 Uhr

Eine verkettete Liste (engl. linked list) ist eine Datenstruktur, die beliebig viele Elemente in linearer Form speichern kann, d.h. zu jedem Element außer dem letzten existiert genau ein Nachfolger und zu jedem Element außer dem ersten existiert genau ein Vorgänger.

Verkettete Listen sind rekursiv definiert und bestehen aus zwei Teilen:

  1. einem Objekt, genannt head; das ist das erste Element der (Teil-)Liste
  2. einer verketteten Liste, genannt tail; das ist der gesamte Rest der Liste

Die einfachsten Fälle sind die leere Liste:

... und eine einelementige Liste:

An diese Liste können nun weitere Elemente angefügt werden, indem schrittweise neue Listen erzeugt werden:

Ein Element nach dem anderen:

Operationen

Suchen

Selbst wenn die Liste sortiert ist, kann nur dadurch nach Elementen suchen, dass man die ganze Liste von vorn nach hinten durchgeht. Da jedes Element nur mit seinem direkten Nachfolger verbunden ist, können auch keine Algorithmen wie die Binäre Suche eingesetzt werden. Die Suche in einer verketteten Liste hat damit eine Laufzeit in .

Einfügen

Am Ende einer Liste kann man einfach ein neues Element anfügen, indem man ein neues Listen-Objekt mit einem Eintrag erzeugt:

... und dann den tail des letzten Listenelements darauf zeigen lässt.


In der Mitte einer Liste kann man einfach ein neues Element anfügen, indem man ein neues Listen-Objekt mit einem Eintrag erzeugt:

... und dann den tail des vorhergehenden Listenelements darauf zeigen lässt. Damit das Ende der alten Liste nicht verloren geht, muss auch der tail des neu eingefügten Elements entsprechend gesetzt werden.

Entfernen

Ein Element entfernt man einfach, indem man den tail von dessen Vorgänger auf dessen Nachfolger zeigen lässt. Für die Liste ist dieses Element dann nicht mehr existent. In den meisten modernen Programmiersprachen springt außerdem, sobald keine Referenzen mehr auf ein Objekt zeigen, ein Mechanismus namens Garbage Collection an. Dieses Objekt, auf das nun nicht mehr aus dem Programm heraus zugegriffen werden kann, wird dann aus dem Speicher gelöscht.

Dass der tail von Element 2 weiterhin auf Element 3 zeigt, ist nicht weiter tragisch. Element 2 ist trotzdem aus der Liste verschwunden, weil es keinen Weg mehr gibt, zu Element 2 hin zu navigieren. Dem Verweis von Element 2 auf Element 3 kann man nicht rückwärts folgen.

Zum Weiterlesen

Abgerufen von „https://wiki.kah.gs/index.php?title=Verkettete_Liste&oldid=6502“