Kurs:Algorithmen und Datenstrukturen (hsrw)/Vorlesung/Einfach verkettete Listen
Einfach verkettete Listen Bearbeiten
ADT Liste: Ggfs. leere Sequenz von Elementen
Die Elemente einer Liste bezeichnet man häufig als Knoten. Jedes Element zeigt dabei auf das ihm nachfolgende Element. Der Zeiger im letzten Element zeigt auf null. Die folgende Abbildung illustriert diese Verkettung. Ein Element besteht demnach aus einem Feld data, welches die Nutzdaten (in unserem Falle Integer) enthält und einem Feld next, welches einen Zeiger auf das folgende Element enthält. Um die Datenstruktur verwenden zu können, gibt es noch einen Zeiger auf das erste Element der Liste, welcher üblicherweise mit head bezeichnet wird.
Hinweis für die Übungsaufgaben: Es empfiehlt sich immer, die betrachtete Situation als Bild zu zeichnen und sich anhand dessen zu überlegen, welche Fälle und Sonderfälle auftreten können und in welcher Reihenfolge welche Operationen nun notwendig sind.
Durch Zuweisungen an den Zeiger next wird die innere Struktur der Liste geändert. Falls dies in der falschen Reihenfolge geschieht, werden Teile der Liste "abgehängt" und sind nicht mehr erreichbar.
Operationen auf Listen Bearbeiten
Auf einfach Listen haben wir folgenden Operationen:
- isEmpty(L)
- size(L)
- find(x, L)
- get(pos, L)
- insert(x, L)
- insertPos(x, pos, l)
- append(x, L)
- remove(x, L)
Ist die Liste leer ? Bearbeiten
Die Operation isEmpty ist sehr leicht zu implementieren, da wir lediglich prüfen müssen, ob der head Zeiger null ist. Diese Operation hat eine Laufzeit von .
isEmpty(L)
return L.head = null
Größe bestimmen Bearbeiten
Um für eine beliebige Liste die Länge der Liste zu bestimmen, müssen wir einmal durch die komplette Liste laufen. Wir benötigen eine Variable count, welche wir mit 0 initialisieren. Weiterhin brauchen wir einen Zeiger tmp auf das Element der Liste, welches wir gerade bearbeiten. Dieser verweist zum Programmstart auf das Element head der Liste. Der Algorithmus ended, sobald wir mit dem Zeiger tmp auf null zeigen. Im Rumpf der Schleife müssen wir den tmp Zeiger immer um einen Konten weiterrücken (tmp = tmp.next) und außerdem die Variable count um eins nach oben Zählen. Schließlich geben wir den Wert von count zurück.
size(L)
count := 0
tmp := L.head
while tmp ≠ null
tmp := tmp.next
count := count + 1
return count
Element suchen Bearbeiten
find liefert entweder den Knoten, bei dem das Feld data den Wert x hat oder falls kein solcher Knoten vorhanden ist, den Wert null zurück. Für die leere Liste ist der Rückgabewert null. Andernfalls müssen wir wieder die Liste mit einem Zeiger tmp durchlaufen, welchen wir am Anfang auf den Wert von head setzen. Solange das data Feld des Zeigers tmp nicht den Wert x enthält und wir noch nicht am Ende der Liste angekommen sind gehen wir die Liste durch tmp := tmp.next. Anschließend prüfen wir, ob das data Feld des Zeigers tmp den Wert x hat und geben in diesem Fall tmp zurück, andernfalls geben wir null zurück.
find(x, L)
if not isEmpty(L)
tmp := L.head
while tmp.next ≠ null and tmp.data ≠ x
tmp := tmp.next
if tmp.data = x
return tmp
return null
Wir nehmen an, x liege auf dem dritten Knoten. Wir stellen fest, dass die Liste nicht leer ist und setzten daher den Zeiger tmp auf den Wert von head. Somit zeigt tmp nun auf das erste Element. Nun prüfen wir, ob wir weiterrücken dürfen und stellen fest, dass der next Zeiger einen von null verschiedenen Wert hat und das Feld data einen Wert ungleich x aufweist. Somit rücken wir, wie im Körper der while Schleife vorgesehen, weiter zum zweiten Element der Liste. Dort führen wir selbige zwei Prüfungen erneut durch. Wieder stellen wir fest, dass sowohl der next Zeiger einen Wert ungleich null besitzt, als auch das im Feld data ein von x verschiedener Wert vorhanden ist und rücken erneutet den Zeiger tmp um ein Element vor, so dass er nun auf das dritte Element der Liste verweist. Hier stellen wir fest, dass im Feld data nun der Wert x vorhanden ist und verlassen daher die Schleife. Nun überprüfen wir entsprechend der if Bedingung, ob wir das Element x gefunden haben und geben somit den gefundenen Knoten tmp als Ergebnis zurück.
Element einfügen Bearbeiten
In der folgenden Abbildung sehen wir ein neues Element x, welches wir in eines Liste einfügen wollen.
Wir fügen das Element am Anfang der Liste ein, da wir dann keinen Aufwand zum Suchen der Einfügestelle haben und die Aufgabe in lösen können. Zunächst setzen wir den Zeiger für den Nachfolger im Knoten des neu einzufügenden Elements auf den derzeitigen Wert von head. Anschließend sorgen wir dafür, dass head auf den neu eingefügten Knoten zeigt.
insert(x, L)
node := newNode(x)
if not isEmpty(L)
node.next = head
L.head := node
Bei der leeren Liste müssen wir lediglich den Zeiger head auf den neu anzulegenden Knoten verbiegen. Legen wir also zunächst einen neuen Knoten an node := newNode(x). Nun müssen wir schauen, ob die Liste nicht leer ist: not isEmpty(L). In diesem Fall (Liste ist nicht leer) müssen wir zunächst dem Nachfolgerzeiger des neu angelegten Knotens den Wert von head zuweisen: node.next = head. Anschließend müssen wir unabhängig davon, ob die Liste ursprünglich leer war, den head Zeiger der Liste auf den neu angelegten Knoten verbiegen: L.head := node.
Element an bestimmter Postion einfügen Bearbeiten
Wir wollen nun ein neues Element x an Position zwei einfügen. Daher verbiegen wir zunächst den Nachfolgerzeiger des neuen Knotens auf den bisherigen zweiten Knoten und erst anschließend im zweiten Schritt den Nachfolgerzeiger des ersten Knotens auf den neu eingefügten Knoten.
insertPos(x, pos, L)
if isEmpty(L)
insert(x, L)
else
tmp := L.head
i := 0
while tmp.next ≠ null and i < pos - 1
tmp := tmp.next
i := i + 1
node := newNode(x)
node.next := tmp.next
tmp.next := node
Im Falle der nicht leeren Liste müssen wir die Liste auf der Suche nach der gewünschten Einfügeposition durchsuchen. Wir benötigen also einen temporären Zeiger tmp, welchen wir zuerst auf den Anfang der Liste setzten tmp := L.head. Weiterhin benötigen wir einen Integer i, um die Position in der Liste, an der wir uns aktuell befinden, zu verwalten. Wir initialisieren i mit dem Wert 0, da das Element am Kopf der Liste der Position 0 entspricht. Nun durchlaufen wir die Liste mit einer while Schleife. Haben wir das Ende der Liste noch nicht erreicht, hat entsprechend der next Zeiger des Knotens tmp einen von null verschiedenen Wert (tmp.next ≠ null), so können wir weiterrücken, sofern wir die gewünschte Einfügeposition noch nicht erreicht haben. Die folgende Abbildung illustriert die Situation beim Erreichen der gewünschten Einfügeposition während des Durchlaufs der while Schleife:
In der Abbildung zeigt der Zeiger tmp auf das erste Element. Hier können wir die Einfügeoperation vornehmen, weil wir hier Zugriff auf den next Zeiger des ersten Knotens haben, welchen wir auf das neu einzufügende Element verbiegen müssen. In diesem Fall gilt gerade i = pos - 1. Somit dürfen wir, um den Fall des Erreichens der Einfügeposition zu berücksichtigen, in der while Schleife nur vorrücken, falls zusätzlich die Bedingung i < pos - 1 gilt. Im Körper der while Schleife müssen wir nun den tmp Zeiger auf das folgende Element vorrücken tmp := tmp.next. Außerdem müssen wir den Zähler i im Körper der while Schleife inkrementieren i := i + 1. Nach Durchlauf dieser Schleife wurde entweder die korrekte Einfügeposition gefunden und tmp zeigt auf das Element, dessen next Zeiger wir auf das neue Element verbiegen wollen, oder der Zeiger tmp zeigt auf den letzten Knoten der Liste. Wir müssen also in beiden Fällen einen Knoten für das neue Element anlegen node := newNode(x) und den Nachfolgerzeiger next des Knotens tmp auf den Knoten des neu einzufügenden Elements verbiegen: tmp.next := node. Außerdem müssen wir den Nachfolgerzeiger des neu erstellten Knotens festlegen. Somit können wir in beiden Fällen dem Nachfolgerzeiger des neu einzufügenden Knotens den Wert des Nachfolgerzeigers des Knotens tmp zuweisen node.next := tmp.next.
Element nach Index suchen Bearbeiten
Wir initialisierten zunächst den Positionszähler i mit 0. Weiterhin setzen wir den Zeiger zum Durchlauf der Elemente tmp auf den Anfang der Liste tmp := L.head. Nun müssen wir die Schleifenbedingung der while Schleife festlegen. Hierzu stellen wir die Situation in der folgenden Abbildung graphisch dar.
Nehmen wir an, wir wollten das zweite Element der Liste bestimmen. Da wir tmp zurückliefern wollen, müssen wir in der Schleifenbedingung, im Unterschied zum oben beim Einfügen behandelten Fall, prüfen, ob der Zeiger tmp nicht den Wert null hat tmp ≠ null und ob wir den gewünschten Index bereits erreicht haben i < pos. Im Körper der Schleife müssen wir genauso wie vom oben beschriebenen Einfügen her bekannt, den Zeiger auf das nächste Element weiterrücken tmp := tmp.next und den Elementzähler um eins erhöhen i := i + 1. Im Falle i = pos haben wir entweder das gesuchte Element gefunden oder wir haben das Ende der Liste erreicht und tmp verweist auf null. In beiden Fällen erreichen wir durch Rückgabe von tmp das gewünschte Ergebnis.
get(pos , L)
if not isEmpty(L)
tmp := L.head
i := 0
while tmp ≠ null and i < pos
tmp := tmp.next
i := i + 1
if i = pos
return tmp
return null
Element hinten anfügen Bearbeiten
Mit size können wir die Länge der Liste bestimmen und mit insertPos an einer frei wählbaren Stelle in die Liste einfügen. Wir wählen size(L) als Einfügepositon und fügen somit am Ende der Liste ein. Die Funktion size benötigt Schritte. Die Funktion insertPos benötigt ebenfalls Schritte. Somit benötigen wir insgesamt Schritte. Unser Verfahren hat demnach eine Laufzeit von .
append(x, L)
insertPos(x, size(L), L)
Es gibt eine alternative Implementierung, welche das Problem in Schritten löst:
append2(x, L)
tmp := L.head
while tmp.next ≠ null
tmp := tmp.next
tmp.next = newNode(x)
Element entfernen Bearbeiten
Wir müssen den Zeiger tmp bis auf das Element vor dem gesuchten Element vorrücken und können anschließend dessen Nachfolgerzeiger next wie in der Abbildung dargestellt auf das Element verbiegen, welches dem gesuchten Element nachfolgt. Wir müssen noch zwei weitere Spezialfälle behandeln. Zum einen kann die Liste ausschließlich aus einem einzigen Element bestehen.
In diesem Fall genügt es, dem Kopfzeiger der Liste head den Wert null zuzuweisen. Zum anderen kann es passieren, dass die Liste mindestens zwei Elemente enthält und wir das erste Element der Liste (das ist das Element auf den der Kopfzeiger head verweist) aus der Liste entfernen wollen. Die folgende Abbildung zeigt diese Situation.
In diesem Fall müssen wir den Kopfzeiger head um eine Position weiterrücken, so dass er dann auf den Nachfolger des zu entfernenden Elementes verweist head := head.next. Wir schreiben somit diese Anweisung in den Rumpf der Bedingung if L.head.data = x. Andernfalls müssen wir den Standardfall behandeln und die Liste mit einer while Schleife durchsuchen. Wir wollen die while Schleife solange durchlaufen, wie wir entweder das gesuchte Element noch nicht erreicht haben tmp.next.data ≠ x, oder noch nicht am Ende der Liste angekommen sind tmp.next ≠ null. Im Rumpf der while Schleife rücken wir den Zeiger tmp auf das jeweils folgende Element vor tmp := tmp.next.
Entsprechend prüfen wir, ob wir das gesuchte Element gefunden haben if tmp.data = x. In diesem Fall müssen wir den Nachfolgerzeiger des Elements auf das tmp zeigt um ein Element auf den Übernächsten weiterrücken tmp.next = tmp.next.next.
remove(x, L)
if not isEmpty(L)
if L.head.data = x
L.head:=L.head.next
else
tmp:=L.head
while tmp.next ≠ null and tmp.next.data ≠ x
tmp := tmp.next
if tmp.next.data != null
tmp.next := tmp.next.next
Kreis finden Bearbeiten
In der folgenden Abbildung sehen wir eine Liste, in der der Nachfolgerzeiger des letzten Elementes nicht den Wert null hat, sondern auf ein Element der Liste verweist. Wir sagen in diesem Falle auch: Die Liste enthält einen Kreis.
Daher ist es sinnvoll ein Verfahren zu haben, mit dem man feststellen kann, ob eine Liste einen Kreis enthält. Eine gute Lösung bietet hier der Hase und Igel Algorithmus. Hierfür setzen wir einen Zeiger auf das erste Element der Liste, welchen wir als Igel bezeichnen. Weiterhin setzen wir einen Zeiger auf das zweite Element der Liste, welchen wir als Hasen bezeichnen. Wir lassen in jedem Schritt den Igel um ein Element vorrücken, jedoch gleichzeitig den Hasen um zwei Elemente. Enthält die Liste keinen Kreis, so erreicht der Hase nach endlich vielen Schritten das Ende der Liste. Enthält die Liste jedoch einen Kreis, so holt der Hase irgendwann den Igel ein. Man sieht, dass der Algorithmus nach bereits zwei Schritten terminiert, weil dann sowohl der Hase als auch der Igel auf das Element, welches die Zahl 3 enthält, verweisen.
hasCircle(L):
if isEmpty(L) or L.head.next = null
return false
igel := L.head
hase := L.head.next
while hase.next ≠ null
if hase = igel
return true
if hase.next.next = null
return false
hase := hase.next.next
igel := igel.next
return false
Im Falle der leeren Liste isEmpty(L), sowie im Falle der einelementigen Liste, deren einziges Element einen Nachfolgerzeiger mit dem Wert null enthält (L.head.next = null), gibt es keinen Kreis. In diesem Falle geben wir false zurück. Andernfalls setzten wir den Igel auf das erste Element der Liste igel := L.head und den Hasen auf das zweite Element der Liste hase := L.head.next. Nun müssen wir eine while Schleife durchlaufen, solange der Nachfolgezeiger des Hasen einen Wert ungleich null besitzt hase.next ≠ null. Im Rumpf der while Schleife prüfen wir mit einer if Bedingung, ob wir einen Kreis gefunden haben hase = igel und geben in diesem Fall dies als Ergebnis zurück return true.
Es kann jedoch auch vorkommen, dass der Hase nicht sinnvoll weiterspringen kann, weil der übernächste Nachfolger des Hasen den Wert null besitzt. Daher müssen wir diesen Fall ebenfalls im Rumpf der while Schleife mit einer if Bedingung behandeln hase.next.next = null. In diesem Falle geben wir zurück, dass die Liste keinen Kreis besitzt return false. Schließlich müssen wir ebenfalls noch im Rumpf der while Schleife den Sprung des Hasen hase := hase.next.next sowie den Sprung des Igels igel := igel.next ausführen.
Schließlich geben wir, sofern die Schleife verlassen wurde, zurück, dass die Liste keinen Kreis enthält return false.