Variante
|
von einfach verketteten Listen
|
Ziele |
|
1.
|
nicht nur der Zugriff auf das erste, sondern auch auf das letzte Element einer Liste in konstanter Zeit
|
2.
|
Konkatenation von Listen in konstanter Zeit
|
| |
Idee
|
einfach verketteter Ring
|
|
zyklische Struktur
|
|---|
|
Listenreferenz zeigt auf den letzten Knoten
|
|---|
|
im letzten Knoten steht eine Referenz auf den ersten Knoten
|
|---|
|
leere Liste bildet immer einen Sonderfall
|
|---|
|
nur destruktiver Ansatz möglich,
sharing von Teillisten ist nicht möglich
|
|---|
Einsatz |
als FIFO-Warteschlange
|
Klassenstruktur |
wie bei einfach verketteten Listen
|
|
public abstract
class LinkedRing
implements List {
...
private static final
class Empty
extends LinkedRing {
...
}
private static final
class Node
extends LinkedRing {
E info;
Node next;
...
}
...
}
|
|---|
| |
Inhalt
|
wird in der Vorlesung entwickelt
|
Algorithmen & Datenstrukturen mit Java: Listen mit einfach verketteten Ringen
