Verkettete Liste: Unterschied zwischen den Versionen
Sn (Diskussion | Beiträge) (more work to do) |
Sn (Diskussion | Beiträge) (Definition und Operationen) |
||
| Zeile 167: | Zeile 167: | ||
</uml> | </uml> | ||
{{Lückenhaft}} | In der Mitte einer Liste kann man einfach ein neues Element anfügen, indem man ein neues Listen-Objekt mit einem Eintrag erzeugt: | ||
<uml> | |||
@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 | |||
} | |||
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. | |||
<uml> | |||
@startuml | |||
hide empty description | |||
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 | |||
} | |||
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]-> newElement | |||
t4 -[bold]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]] | ||
Version vom 23. November 2023, 01:06 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:
- einem Objekt, genannt
head; das ist das erste Element der (Teil-)Liste - 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:
Operationen
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.
In diesem Artikel oder Abschnitt fehlen noch folgende wichtige Informationen:
Hilf dem KGS-Wiki, indem du sie recherchierst und einfügst.
