Verkettete Liste: Unterschied zwischen den Versionen

Aus KGS-Wiki
(→‎Suchen: Laufzeit)
(Umstellung auf GraphViz begonnen)
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></TR><TR><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></TR><TR><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
    subgraph cluster_node {
state "tail" as t1
        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!"];
t1: null
        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!"];
h1 -[hidden]right-> t1
    }
}
}
@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
        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!"];
        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!"];
    }
    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!"];
        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!"];
    }
    tail1:ptr -> head2 [lhead="cluster_node2"];
}
}
state List2 {
</graphviz>
state "head" as h2
 
h2: 23
<graphviz format="svg">
state "tail" as t2
digraph ListTwoElements {
t2: null
    compound="true"
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 {
        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!"];
        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!"];
    }
    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!"];
        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!"];
    }
    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!"];
        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!"];
    }
    tail1:ptr -> head2 [lhead="cluster_node2"];
    tail2:ptr -> head3 [lhead="cluster_node3"];
}
}
t1 --[bold]right--> List2
</graphviz>
@enduml
</uml>


<uml>
{{Todo|Sn}}
@startuml
hide empty description
skinparam linetype ortho
state List1 {
state "head" as h1
h1: 42
state "tail" as t1
h1 -[hidden]right-> t1
}
state List2 {
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
}
t1 --[bold]right-> List2
t2 --[bold]right-> List3
@enduml
</uml>


== Operationen ==
== Operationen ==
Zeile 101: Zeile 97:
hide empty description
hide empty description
skinparam linetype ortho
skinparam linetype ortho
state List1 {
state Node1 {
  state "head" as h1
  state "head" as h1
  h1: 42
  h1: 42
Zeile 107: Zeile 103:
  h1 -[hidden]right-> t1
  h1 -[hidden]right-> t1
}
}
state List2 {
state Node2 {
  state "head" as h2
  state "head" as h2
  h2: 23
  h2: 23
Zeile 113: Zeile 109:
  h2 -[hidden]right-> t2
  h2 -[hidden]right-> t2
}
}
state List3 {
state Node3 {
  state "head" as h3
  state "head" as h3
  h3: 69
  h3: 69
Zeile 127: Zeile 123:
  t4: null
  t4: null
}
}
t1 --[bold]right-> List2
state List
t2 --[bold]right-> List3
List -[bold]right-> Node1
t1 --[bold]right-> Node2
t2 --[bold]right-> Node3
t3 --[hidden]right-> newElement
t3 --[hidden]right-> newElement
@enduml
@enduml
Zeile 139: Zeile 137:
hide empty description
hide empty description
skinparam linetype ortho
skinparam linetype ortho
state List1 {
state Node1 {
  state "head" as h1
  state "head" as h1
  h1: 42
  h1: 42
Zeile 145: Zeile 143:
  h1 -[hidden]right-> t1
  h1 -[hidden]right-> t1
}
}
state List2 {
state Node2 {
  state "head" as h2
  state "head" as h2
  h2: 23
  h2: 23
Zeile 151: Zeile 149:
  h2 -[hidden]right-> t2
  h2 -[hidden]right-> t2
}
}
state List3 {
state Node3 {
  state "head" as h3
  state "head" as h3
  h3: 69
  h3: 69
Zeile 164: Zeile 162:
  t4: null
  t4: null
}
}
t1 --[bold]right-> List2
state List
t2 --[bold]right-> List3
List -[bold]right-> Node1
t1 --[bold]right-> Node2
t2 --[bold]right-> Node3
t3 --[bold,#00B169]right-> newElement
t3 --[bold,#00B169]right-> newElement
@enduml
@enduml
Zeile 176: Zeile 176:
hide empty description
hide empty description
skinparam linetype ortho
skinparam linetype ortho
state List1 {
state Node1 {
  state "head" as h1
  state "head" as h1
  h1: 42
  h1: 42
Zeile 182: Zeile 182:
  h1 -[hidden]right-> t1
  h1 -[hidden]right-> t1
}
}
state List2 {
state Node2 {
  state "head" as h2
  state "head" as h2
  h2: 23
  h2: 23
Zeile 188: Zeile 188:
  h2 -[hidden]right-> t2
  h2 -[hidden]right-> t2
}
}
state List3 {
state Node3 {
  state "head" as h3
  state "head" as h3
  h3: 69
  h3: 69
Zeile 202: Zeile 202:
  t4: null
  t4: null
}
}
t1 -[bold]right-> List2
state List
List -[bold]right-> Node1
t1 -[bold]right-> Node2
t1 -[hidden]down-> newElement
t1 -[hidden]down-> newElement
newElement -[hidden]up-> List2
newElement -[hidden]up-> Node2
t2 -[bold]right-> List3
t2 -[bold]right-> Node3
@enduml
@enduml
</uml>
</uml>
Zeile 214: Zeile 216:
@startuml
@startuml
hide empty description
hide empty description
state List1 {
state Node1 {
  state "head" as h1
  state "head" as h1
  h1: 42
  h1: 42
Zeile 221: Zeile 223:
}
}


state List2 {
state Node2 {
  state "head" as h2
  state "head" as h2
  h2: 23
  h2: 23
Zeile 227: Zeile 229:
  h2 -[hidden]right-> t2
  h2 -[hidden]right-> t2
}
}
state List3 {
state Node3 {
  state "head" as h3
  state "head" as h3
  h3: 69
  h3: 69
Zeile 241: Zeile 243:
  t4: null
  t4: null
}
}
t1 -[#lightgray]right> List2
t1 -[#lightgray]right> Node2
t1 -[bold,#00B169]-> newElement
t1 -[bold,#00B169]-> newElement
t4 -[bold,#00B169]down-> List2
t4 -[bold,#00B169]down-> Node2
t2 -[bold]right> List3
t2 -[bold]right> Node3
List1 -[hidden]up-> List2
Node1 -[hidden]up-> Node2
' Diese Kombination von Befehlen ergibt das gewünschte Layout.
' Diese Kombination von Befehlen ergibt das gewünschte Layout.
' Keine Ahnung warum. Die Layout-Algorithmen von PlantUML sind fubar.
' Keine Ahnung warum. Die Layout-Algorithmen von PlantUML sind fubar.
' Also fuck it. Ich hasse es, aber es bleibt so.
' Also fuck it. Ich hasse es, aber es bleibt so.
state List
List -[bold]right-> Node1
@enduml
@enduml
</uml>
</uml>

Version vom 24. September 2024, 06:18 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:

🏗
Baustelle

Dieser Abschnitt wird gerade von Sn überarbeitet


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.

🕳
Lückenhaft

In diesem Artikel oder Abschnitt fehlen noch folgende wichtige Informationen:

Operation Entfernen

Hilf dem KGS-Wiki, indem du sie recherchierst und einfügst.

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