Doppelt verkettete Liste < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
| |
|
Hallo Back-Up,
> Was kann ich mit einer doppelt verketten Liste machen? Ich
> kann ja zusätzlich "rückwärtsgehen"... welche Vorteile habe
> ich dadurch?
Auf einer einfach verketteten Liste ist, soweit ich weiß, nur lineare Suche möglich. Stell' dir mal vor, Du speicherst n Zahlen in absteigender Reihenfolge in einer einfach verketteten Liste ab. Jetzt möchtest Du die kleinste Zahl aus diesen Zahlen bestimmen. Weil alle Knoten einer solchen Liste nur einen Zeiger zum Nachfolger besitzen, mußt Du in diesem schlimmsten Fall zwangsläufig alle n Knoten durchlaufen um gerade beim n-ten Mal deine Zahl zu finden. Das bezeichnet man auch als lineare Laufzeit. Hättest Du die Zahlen in einem Array abgespeichert, könntest Du hingegen binäre Suche anwenden, indem Du das mittlere Element der Folge bestimmst und mit dem Element vergleichst den Du im Array suchst. Je nachdem, ob das Element größer-gleich oder kleiner ist als das Gesuchte, gehst Du entweder nach rechts oder nach links und betrachtest ab diesem Zeitpunkt nur noch diese Elemente der Folge. Dein Problem hat sich folglich halbiert. Da dies in jedem Suchschritt so ist, erhälst Du eine logarithmische Laufzeit.
Auf einer einfach verketteten Liste kannst Du so etwas aber nicht implementieren, da Du nur in eine Richtung gehen kannst. Bei einer doppelt verketteten Liste kannst Du das. Allerdings benötigst Du für solche Listen auch mehr Speicherplatz (welcher von den "zweiten" Zeigern beansprucht wird.)
Wenn Du willst, kannst Du ja jetzt mal die binäre Suche auf einer doppelt verketteten Liste implementieren.
Meine Antwort basierte leider auf einem Irrtum, der mir gerade beim nochmaligen Durchlesen meiner Antworten bewußt geworden ist. Die binäre Suche auf einer solchen Liste zu implementieren, ist natürlich unmöglich! Eine doppelt verkettete Liste ähnelt schon sehr einem Array, aber man kann mit ihr nicht in konstanter Zeit auf ein beliebiges Element zugreifen. Auch bei einer doppelt verketteten Liste mußt Du einige Elemente der Liste (entweder rückwärts oder vorwärts) durchlaufen, um zu einem beliebigen "weiter entfernten" Element zu gelangen, denn Du hast keinen direkten Zeiger zu diesem beliebigen Element, sondern nur Zeiger für die Nachbar-Elemente des Knotens, auf den Du gerade zugreifst. binarySearch() benötigt jedoch konstanten Zugriff auf beliebige Elemente eines zu sortierenden Feldes, um in logarithmischer Zeit zu suchen.
(Meine andere Antwort beschreibt quasi den binarySearch(). Aus dem Kontext deiner Frage gegriffen ist die Beschreibung wohl korrekt.)
Viele Grüße
Karl
|
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 20:13 Mo 13.06.2005 | | Autor: | Back-Up |
Müssen die Werte in meiner Liste dafür sortiert sein?
Kannst du mir nochmal anschaulich erklären, wie diese Suche funktionieren müsste? Ich wäre Dir sehr dankbar :).
Wenn ich in der Mitte anfange und feststelle, das ich z.B. nach links laufen muss, was passiert dann, wenn der gesuchte Wert auf der rechten Seite liegt?
Wie du siehst, fehlt es mir grad am Vorstellungsvermögen  .
Gruß
|
|
|
| |
|
> Müssen die Werte in meiner Liste dafür sortiert sein?
>
> Kannst du mir nochmal anschaulich erklären, wie diese Suche
> funktionieren müsste? Ich wäre Dir sehr dankbar :).
>
> Wenn ich in der Mitte anfange und feststelle, das ich z.B.
> nach links laufen muss, was passiert dann, wenn der
> gesuchte Wert auf der rechten Seite liegt?
> Wie du siehst, fehlt es mir grad am Vorstellungsvermögen
> .
Der folgende Text ist nur richtig, wenn es sich um ein Array und nicht um eine Liste handelt!
Ich bin mir ziemlich sicher, daß Du hier Recht hast, und die Liste (das Array) sortiert sein muß damit es funktioniert. Man kann ja die Einfüge-Operation bei der Liste (dem Array) entsprechend komplizierter machen, damit die Liste (das Array) ständig sortiert bleibt. (Die Einfüge-Operation kann ja auch auf binärer Suche aufgebaut werden. Aber nur, wenn es sich um ein Array handelt!)
Ok, im folgenden ersetze ich 'Liste' durch 'Array':
Vorrausgesetzt das Array ist sortiert, greifst Du also auf die Mitte des Arrays zu, weil sich dort dann wegen der Sortierung das mittlere Element befindet und vergleichst dieses Element mit dem, den Du in dem Array finden willst. Ist das mittlere Element größer, befindet sich dein Element im linken Teil des Arrays, ansonsten im rechten Teil des Arrays. Solange Du das Element nicht gefunden hast, halbierst Du nun das neue "Teilarray", indem Du dort wieder das mittlere Element bestimmst und die Obige vorgehensweise wiederholst.
Viele Grüße
Karl
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 12:17 Di 14.06.2005 | | Autor: | Back-Up |
Das habe ich verstanden :).
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 20:40 Mo 13.06.2005 | | Autor: | iftpr |
Hi.
Eine doppelt verkettete Liste hat mehrere Vorteile.
Stell dir einmal vor, du hast einen Zeiger auf ein beliebiges Element in der Mitte der Liste und du willst es löschen. Bei einer einfach verketteten Liste musst du nun die Liste ab Start so lange durchlaufen bis du das Element und dessen Vorgänger gefunden hast. Erst dann kannst du es löschen. Das ist in vielen Fällen einfach viel zu langsam! Wenn man die Elemente in einer doppelt verketteten Liste speichert (also zu einem Element den Vorgänger und Nachfolger), so kann man es ganz leicht löschen - in konstanter Zeit.
Das gleiche passiert, wenn du einen Zeiger auf ein beliebiges Element hast und möchtest direkt davor ein neues Element einfügen - das geht wieder in konstanter Zeit.
Grüße
Till
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:46 Mo 13.06.2005 | | Autor: | Back-Up |
Hallo,
wie kann man denn in einer doppelt verketteten Liste "ganz leicht löschen"? Wie findet man so schnell das zu löschende Element?
Gruß
|
|
|
| |
|
Hallo Back-Up,
> wie kann man denn in einer doppelt verketteten Liste "ganz
> leicht löschen"? Wie findet man so schnell das zu löschende
> Element?
Hmm, ich denke Till hat hier vorrausgesetzt, daß Du bereits einen Zeiger auf das zu löschende Element hast(, denn sonst müßtest Du es ja trotzdem finden (und das geht nicht in konstanter Zeit.) Aber Till schreibt dann ja auch, daß das Einfügen auch in konstanter Zeit möglich ist, vorrausgesetzt man hat die Einfügestelle bereits gefunden.
Grüße
Karl
|
|
|
|
