Verkettete Liste: Unterschied zwischen den Versionen

Aus KGS-Wiki
(Endlich nicht mehr lückenhaft.)
 
(3 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"];
}
}
state List2 {
</graphviz>
state "head" as h2
 
h2: 23
Ein Element nach dem anderen:
state "tail" as t2
t2: null
h2 -[hidden]right-> t2
}
t1 --[bold]right--> List2
@enduml
</uml>


<uml>
<graphviz format="svg">
@startuml
digraph ListThreeElements {
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!"];
state List2 {
        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!"];
state "head" as h2
    }
h2: 23
    subgraph cluster_node2 {
state "tail" as t2
        nodeLabel2 [label="Element 2", shape="plaintext", pos="3.5,0.5!"];
h2 -[hidden]right-> t2
        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
state "tail" as t3
h3 -[hidden]right-> t3
t3: null
}
t1 --[bold]right-> List2
t2 --[bold]right-> List3
@enduml
</uml>


== Operationen ==
== Operationen ==


=== Suchen ===
=== 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.
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 ===
=== Einfügen ===
Zeile 97: Zeile 99:
Am Ende einer Liste kann man einfach ein neues Element anfügen, indem man ein neues Listen-Objekt mit einem Eintrag erzeugt:
Am Ende einer Liste kann man einfach ein neues Element anfügen, indem man ein neues Listen-Objekt mit einem Eintrag erzeugt:


<uml>
<graphviz format="svg">
@startuml
digraph ListThreeElementsPlusNew {
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 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"];
}
}
state List2 {
</graphviz>
state "head" as h2
h2: 23
state "tail" as t2
h2 -[hidden]right-> t2
}
state List3 {
state "head" as h3
h3: 69
state "tail" as t3
h3 -[hidden]right-> t3
t3: null
}
state newElement #00B169 {
state "head" as h4 #00B169
h4: 1337
state "tail" as t4 #00B169
h4 -[hidden]right-> t4
t4: null
}
t1 --[bold]right-> List2
t2 --[bold]right-> List3
t3 --[hidden]right-> newElement
@enduml
</uml>


... und dann den <code>tail</code> des letzten Listenelements darauf zeigen lässt.
... und dann den <code>tail</code> des letzten Listenelements darauf zeigen lässt.


<uml>
<graphviz format="svg">
@startuml
digraph ListThreeElementsNewAdded {
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 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
h2 -[hidden]right-> t2
}
state List3 {
state "head" as h3
h3: 69
state "tail" as t3 #00B169
h3 -[hidden]right-> t3
}
state newElement #00B169 {
state "head" as h4 #00B169
h4: 1337
state "tail" as t4 #00B169
h4 -[hidden]right-> t4
t4: null
}
t1 --[bold]right-> List2
t2 --[bold]right-> List3
t3 --[bold,#00B169]right-> newElement
@enduml
</uml>


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


<uml>
<graphviz format="svg">
@startuml
digraph ListThreeElementsPlusNew {
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 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"];
}
}
state List2 {
</graphviz>
state "head" as h2
 
h2: 23
... 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.
state "tail" as t2
 
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" 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 List3 {
</graphviz>
state "head" as h3
 
h3: 69
=== Entfernen ===
state "tail" as t3
h3 -[hidden]right-> t3
t3: null
}
state newElement #00B169 {
state "head" as h4 #00B169
h4: 1337
state "tail" as t4 #00B169
h4 -[hidden]right-> t4
t4: null
}
t1 -[bold]right-> List2
t1 -[hidden]down-> newElement
newElement -[hidden]up-> List2
t2 -[bold]right-> List3
@enduml
</uml>


... und dann den <code>tail</code> des vorhergehenden Listenelements darauf zeigen lässt.
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.


<uml>
<graphviz format="svg">
@startuml
digraph ListThreeElements {
hide empty description
    compound="true"
state List1 {
fontname="Source Sans Pro,Linux Biolinum,Helvetica,Arial,sans-serif"
state "head" as h1
node [fontname="Source Sans Pro,Linux Biolinum,Helvetica,Arial,sans-serif"]
h1: 42
edge [fontname="Source Sans Pro,Linux Biolinum,Helvetica,Arial,sans-serif"]
state "tail" as t1 #00B169
    layout="neato";
h1 -[hidden]right-> t1
    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>


state List2 {
<graphviz format="svg">
state "head" as h2
digraph ListThreeElementsOneRemoved {
h2: 23
    compound="true"
state "tail" as t2
    splines="curved"
h2 -[hidden]right-> t2
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"];
}
}
state List3 {
</graphviz>
state "head" as h3
 
h3: 69
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.
state "tail" as t3
 
h3 -[hidden]right-> t3
==Zum Weiterlesen==
t3: null
* {{Inf-Schule|2.3.6.2.3|Einfach verkettete Listen}}
}
* {{VisuAlgo|list|Linked List}}
state newElement #00B169 {
state "head" as h4 #00B169
h4: 1337
state "tail" as t4 #00B169
h4 -[hidden]right-> t4
t4: null
}
t1 -[#lightgray]right> List2
t1 -[bold,#00B169]-> newElement
t4 -[bold,#00B169]down-> List2
t2 -[bold]right> List3
List1 -[hidden]up-> List2
' Diese Kombination von Befehlen ergibt das gewünschte Layout.
' Keine Ahnung warum. Die Layout-Algorithmen von PlantUML sind fubar.
' Also fuck it. Ich hasse es, aber es bleibt so.
@enduml
</uml>
{{Lückenhaft|Operation Entfernen}}


[[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“