Verkettete Listen

Question 1

Sinn von verketteten Listen

Answer 1

beliebige Speichergröße

Question 2

welche Probleme lösen verkettete Listen (u.a.)

Answer 2

ungenutzter Speicher, fest definierte Feldlänge

Question 3

zwei Arten von verketteten Listen

Answer 3

einfach verkettete und zweifach verkettete Listen

Question 4

Bestandteile einfach verkettete Liste

Answer 4

Listenknoten (mit Nachfolgerlistenknoten)

head

Question 5

Bestandteile Listenknoten (einfach verkettete Liste)

Answer 5

next (Verweis auf nächstes Element)

object (Referenz auf Objekt, das gespeichert werden soll)

Question 6

Was kann “next” enthalten

Answer 6

Verweis auf nächstes Element

null (wenn kein nächstes Element)

Question 7

was kann “prev” enthalten

Answer 7

Verweis auf vorheriges Element

null (wenn kein vorheriges Element)

Question 8

Wie wird ein Listenknoten vorne an eine einfach verkette Liste angehangen

Answer 8

head -> neuer Listenknoten (Referenz auf ehemalig ersten Listenknoten wird ersetzt)
next(neuen Listenknoten) -> ehemalig ersten Listenknoten

Question 9

Wie wird ein Listenknoten vorne an eine zweifach verkettete Liste angehangen

Answer 9

head -> neuer Listenknoten (Referenz auf ehemalig ersten Listenknoten wird ersetzt)
next(neuer Listenknoten) -> ehemalig erster Listenknoten
prev (neuen Listenknoten) -> null
prev (ehemalig erster Listenknoten) -> neuer Listenknoten

Question 10

Wie wird ein Listenknoten hinten an eine einfach verkettete Liste angehangen

Answer 10

next(neuen Listenknoten) -> null

next(ehemalig letzter Listenknoten) -> neuer Listenknoten

Question 11

Wie wird ein Listenknoten hinten an eine zweifach verkettete Liste angehangen

Answer 11

tail -> neuer Listenknoten (Referenz auf ehemalig letzten Listenknoten wird ersetzt)
next(neuen Listenknoten) -> null
next(ehemalig letzten Listenknoten) -> neuer Listenknoten
prev(neuen Listenknoten) -> ehemalig letzter Listenknoten
next(ehemalig letzter Listenknoten) -> neuer Listenknoten

Question 12

Wie wird ein Listenknoten an einer bestimmten Stelle eingefügt (einfach verkettete Liste)

Answer 12

next(vorausgehender Listenknoten) -> neuer Listenknoten (ersetz die vorherige Referenz auf den Listenknoten, der nun dem neuen Listenknoten folgt)
next(neuen Listenknoten) -> nachfolgender Listenknoten

Question 13

Wie wird ein Listenknoten an einer bestimmten Stelle eingefügt (zweifach verkettete Liste)

Answer 13

next(vorausgehender Listenknoten) -> neuen Listenknoten (ersetz die vorherige Referenz auf den Listenknoten, der nun dem neuen Listenknoten folgt)
next(neuer Listenknoten) -> nachfolgender Listenknoten
prev(neuer Listenknoten) -> vorausgehender Listenknoten
prev(dem neuen Listenknoten folgenden Listenknoten) -> neuer Listenknoten (ersetz die vorherige Referenz auf den Listenknoten, der nun dem neuen Listenknoten vorausgeht)

Question 14

Wie wird der erste Listenknoten einer einfach verketteten Liste gelöscht

Answer 14

head -> “next” des zu löschenden Listenknoten (zeigt auf ehemalig zweiten Listenknoten)

Question 15

Wie wird der erste Listenknoten einer zweifach verketteten Liste gelöscht

Answer 15

head -> “next” des zu löschenden Listenknoten (zeigt auf ehemalig zweiten Listenknoten)
prev(“next” des zu löschenden Listenknoten) -> null (ehemalig zweiter Listenknoten hat keinen Vorgänger mehr)

Question 16

Wie wird der letzte Listenknoten einer einfach verketteten Liste gelöscht

Answer 16

Absuchen aller “next” Werte bis Referenz auf letzten Knoten gefunden wird (mit Hilfe einer temp Variable)
next(gefundener Knotenpunkt) -> null

Question 17

Wie wird der letzte Listenknoten einer zweifach verketteten Liste gelöscht

Answer 17

tail -> “prev” des zu löschendne Listenknoten

next(“prev” des zu löschenden Listenknoten) -> null (ehemalig vorletztes Element hat keinen Nachfolger mehr)

Question 18

Wie wird ein beliebiger Listenknoten einer einfach verketteten Liste gelöscht

Answer 18

Absuchen aller “next” Werte bis Referenz auf letzten Knoten gefunden wird (mit Hilfe einer temp Variable)
next(gefundener Knotenpunkt) -> “next” des zu löschenden Listenknoten(ersetzt die vorherige Referenz auf das zu löschende Listenknoten)

Question 19

Wie wird ein beliebiger Listenknoten einer zweifach verketteten Liste gelöscht

Answer 19

next(“prev” des zu löschenden Listenknoten) -> “next” des zu löschenden Listenknoten(ersetzt die vorherige Referenz auf das zu löschende Element)