Verkettete Liste: Unterschied zwischen den Versionen

Aus KGS-Wiki
(Umstellung auf GraphViz begonnen)
(Endlich nicht mehr lückenhaft.)
 
(Eine dazwischenliegende Version desselben Benutzers wird nicht angezeigt)
Zeile 15: Zeile 15:
     layout="neato";
     layout="neato";
     subgraph cluster_empty {
     subgraph cluster_empty {
         head [label=<<TABLE BORDER="0" CELLSPACING="0" CELLBORDER="1"><TR><TD>head</TD></TR><TR><TD>null</TD></TR></TABLE>>, shape="none", pos="0,0!"];
         head [label=<<TABLE BORDER="0" CELLSPACING="0" CELLBORDER="1"><TR><TD>head</TD><TD>null</TD></TR></TABLE>>, shape="none", pos="0,0!"];
         tail [label=<<TABLE BORDER="0" CELLSPACING="0" CELLBORDER="1"><TR><TD>tail</TD></TR><TR><TD>null</TD></TR></TABLE>>, shape="none", pos="1,0!"];
         tail [label=<<TABLE BORDER="0" CELLSPACING="0" CELLBORDER="1"><TR><TD>tail</TD><TD>null</TD></TR></TABLE>>, shape="none", pos="1,0!"];
     }
     }
}
}
</graphviz>
</graphviz>


... und eine einelementige Liste:
... und eine einelementige Liste:
Zeile 30: Zeile 29:
edge [fontname="Source Sans Pro,Linux Biolinum,Helvetica,Arial,sans-serif"]
edge [fontname="Source Sans Pro,Linux Biolinum,Helvetica,Arial,sans-serif"]
     layout="neato";
     layout="neato";
    compound="true";
     subgraph cluster_node {
     subgraph cluster_node {
         head [label=<<TABLE BORDER="0" CELLSPACING="0" CELLBORDER="1"><TR><TD>head</TD></TR><TR><TD>42</TD></TR></TABLE>>, shape="none", pos="0,0!"];
        nodeLabel [label="Element 1", shape="plaintext", pos="0.5,0.5!"];
         tail [label=<<TABLE BORDER="0" CELLSPACING="0" CELLBORDER="1"><TR><TD>tail</TD></TR><TR><TD>null</TD></TR></TABLE>>, shape="none", pos="1,0!"];
         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!"];
     }
     }
}
}
Zeile 47: Zeile 48:
     layout="neato";
     layout="neato";
     subgraph cluster_node1 {
     subgraph cluster_node1 {
         head1 [label=<<TABLE BORDER="0" CELLSPACING="0" CELLBORDER="1"><TR><TD>head</TD></TR><TR><TD>42</TD></TR></TABLE>>, shape="none", pos="0,0!"];
        nodeLabel1 [label="Element 1", shape="plaintext", pos="0.5,0.5!"];
         tail1 [label=<<TABLE BORDER="0" CELLSPACING="0" CELLBORDER="1"><TR><TD>tail</TD></TR><TR><TD PORT="ptr">&nbsp;</TD></TR></TABLE>>, shape="none", pos="1,0!"];
         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 {
     subgraph cluster_node2 {
         head2 [label=<<TABLE BORDER="0" CELLSPACING="0" CELLBORDER="1"><TR><TD>head</TD></TR><TR><TD>23</TD></TR></TABLE>>, shape="none", pos="3,0!"];
        nodeLabel2 [label="Element 2", shape="plaintext", pos="3.5,0.5!"];
         tail2 [label=<<TABLE BORDER="0" CELLSPACING="0" CELLBORDER="1"><TR><TD>tail</TD></TR><TR><TD>null</TD></TR></TABLE>>, shape="none", pos="4,0!"];
         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"];
     tail1:ptr -> head2 [lhead="cluster_node2"];
}
}
</graphviz>
</graphviz>
Ein Element nach dem anderen:


<graphviz format="svg">
<graphviz format="svg">
digraph ListTwoElements {
digraph ListThreeElements {
     compound="true"
     compound="true"
fontname="Source Sans Pro,Linux Biolinum,Helvetica,Arial,sans-serif"
fontname="Source Sans Pro,Linux Biolinum,Helvetica,Arial,sans-serif"
Zeile 66: Zeile 71:
     layout="neato";
     layout="neato";
     subgraph cluster_node1 {
     subgraph cluster_node1 {
         head1 [label=<<TABLE BORDER="0" CELLSPACING="0" CELLBORDER="1"><TR><TD>head</TD></TR><TR><TD>42</TD></TR></TABLE>>, shape="none", pos="0,0!"];
        nodeLabel1 [label="Element 1", shape="plaintext", pos="0.5,0.5!"];
         tail1 [label=<<TABLE BORDER="0" CELLSPACING="0" CELLBORDER="1"><TR><TD>tail</TD></TR><TR><TD PORT="ptr">&nbsp;</TD></TR></TABLE>>, shape="none", pos="1,0!"];
         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 {
     subgraph cluster_node2 {
         head2 [label=<<TABLE BORDER="0" CELLSPACING="0" CELLBORDER="1"><TR><TD>head</TD></TR><TR><TD>23</TD></TR></TABLE>>, shape="none", pos="3,0!"];
        nodeLabel2 [label="Element 2", shape="plaintext", pos="3.5,0.5!"];
         tail2 [label=<<TABLE BORDER="0" CELLSPACING="0" CELLBORDER="1"><TR><TD>tail</TD></TR><TR><TD PORT="ptr">&nbsp;</TD></TR></TABLE>>, shape="none", pos="4,0!"];
         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 {
     subgraph cluster_node3 {
         head3 [label=<<TABLE BORDER="0" CELLSPACING="0" CELLBORDER="1"><TR><TD>head</TD></TR><TR><TD>69</TD></TR></TABLE>>, shape="none", pos="6,0!"];
        nodeLabel3 [label="Element 3", shape="plaintext", pos="6.5,0.5!"];
         tail3 [label=<<TABLE BORDER="0" CELLSPACING="0" CELLBORDER="1"><TR><TD>tail</TD></TR><TR><TD>null</TD></TR></TABLE>>, shape="none", pos="7,0!"];
         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"];
     tail1:ptr -> head2 [lhead="cluster_node2"];
Zeile 81: Zeile 89:
}
}
</graphviz>
</graphviz>
{{Todo|Sn}}


== Operationen ==
== Operationen ==
Zeile 93: 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 Node1 {
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 Node2 {
</graphviz>
state "head" as h2
h2: 23
state "tail" as t2
h2 -[hidden]right-> t2
}
state Node3 {
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
}
state List
List -[bold]right-> Node1
t1 --[bold]right-> Node2
t2 --[bold]right-> Node3
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 Node1 {
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 Node2 {
</graphviz>
state "head" as h2
 
h2: 23
state "tail" as t2
h2 -[hidden]right-> t2
}
state Node3 {
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
}
state List
List -[bold]right-> Node1
t1 --[bold]right-> Node2
t2 --[bold]right-> Node3
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 Node1 {
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 Node2 {
</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 Node3 {
</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
}
state List
List -[bold]right-> Node1
t1 -[bold]right-> Node2
t1 -[hidden]down-> newElement
newElement -[hidden]up-> Node2
t2 -[bold]right-> Node3
@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 Node1 {
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 Node2 {
<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 Node3 {
</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> Node2
t1 -[bold,#00B169]-> newElement
t4 -[bold,#00B169]down-> Node2
t2 -[bold]right> Node3
Node1 -[hidden]up-> Node2
' 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.
state List
List -[bold]right-> Node1
@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“