verkettete Liste oder Array



  • Ich habe mal gelesen, dass in der Praxis kaum einer verkettete Listen einsetzt, sondern anstelle dessen ein Array. Wie soll das gehen? Ein Array ist doch statisch in seiner Größe und eine Linked List nicht.



  • Du musst kein echtes Array nehmen.
    Du kannst auch mit einem Pointer und malloc/realloc arbeiten.



  • Ok danke, vielleicht kann mit noch einer erklären, was es mit der Aussage "Linked List schlechter als Array" auf sich hat?



  • Wobei der Initial-Bereich der (realloc)-Liste "ausreichend" groß dimensioniert werden kann, ebenso wie die anschließend evtl. notwendigen reallocs, was dazu führt, dass beim Einfügen eben nicht (wie bei einer verk.Liste) jedesmal ein malloc(realloc) notwendig ist.
    Natürlich könnte man dieses Block-Verhalten auch bei einer verk.Liste einsetzen, aber weitere Unsinns-Eigenschaften der verk.Liste sprechen dagegen wie unnötiger Speicherplatzbedarf (für next/before), kein wahlfreier Zugriff, demzufolge keine vernünftige Sortierbarkeit und Redundanz bei der Persistierung (weil next/before-Zeiger nach Speichern und Lesen jedesmal neu initialisiert werden müssten).



  • movem.l schrieb:

    Ok danke, vielleicht kann mit noch einer erklären, was es mit der Aussage "Linked List schlechter als Array" auf sich hat?

    Nix. Wer sowas sagt, hat zu 10% Unrecht.

    Array bzw Vector ist durchschnittliche einfach viel schneller. Sagen wir mal 30-mal so schnell bei kleinen Sachen wie double oder Point3D. Aaaber Array ruckelt gerne auch mal beim vergrößern, kann beim Zocken kein Ruckeln von einem Sekündchen gebrauchen, sonst bin ich gefraggt. Kauf mir lieber nen fetteren Rechner, damit er auch mit verketteter Liste geht.

    Und am Ende benutzt man eh keine reinen verketten Listen, sondern verkettet kleine Arrays (mit sagen wir mal e 100 Elementen), ist damit in allen Belangen quasi so schnell wie das Array und ruckelt nicht.

    (Die Ausnahmen wo reine verkette Listen verwendet werden wie Verkettungen im Überlaufbereich von Hashtables oder intrusive Ringe oder Move-To-Front-Listen verschweige ich mal.)



  • Wutz schrieb:

    kein wahlfreier Zugriff, demzufolge keine vernünftige Sortierbarkeit

    Einspruch. Die schnellsten Verfahren Mergesort und Quicksort brauchen keinen wahlfreien Zugriff. Sie lassen sich leicht für verkettet Listen bauen, der Code spiegelt die Idee des Algos sogar besser wider als die Array-Lösungen.

    Prof84 schrieb:

    und Redundanz bei der Persistierung (weil next/before-Zeiger nach Speichern und Lesen jedesmal neu initialisiert werden müssten).

    Da widerspreche ich mal pauschal.



  • Danke für die Erklärungen. Wie sieht es eigentlich bei Bäumen, Tries und Graphen aus, ist da auch die Tendenz in Richtung Array?



  • Klick. Suche nach malloc_chunk . Die verwenden selbst verkettete Listen, selbst beim berühmten realloc kommt man nicht drum rum.

    Meine Arbeit hier ist getan.



  • movem.l schrieb:

    Danke für die Erklärungen. Wie sieht es eigentlich bei Bäumen, Tries und Graphen aus, ist da auch die Tendenz in Richtung Array?

    Ja sicher, warum nicht.

    Mal eine leicht OT-Frage an die Runde: Würde man das (eine Baumklasse, deren Knoten in einem Array abgelegt sind) in C++ über einen Allokator regeln?



  • movem.l schrieb:

    Danke für die Erklärungen. Wie sieht es eigentlich bei Bäumen, Tries und Graphen aus, ist da auch die Tendenz in Richtung Array?

    Eigentlich nicht, weil das Rumsuchen oder Einfügen im Array bzw 100 Elemente großen Mini-Array sauteuer wäre. Ausnahmen gibt es, wie B-Bäume (weil eh jeder Plattenzugriff als Einheit kostet) und Heaps in Arrays.



  • Bashar schrieb:

    Mal eine leicht OT-Frage an die Runde: Würde man das (eine Baumklasse, deren Knoten in einem Array abgelegt sind) in C++ über einen Allokator regeln?

    Ich würde es nicht in einem Array tun. Könnte gewohnte Garantien wie Gültigkeit von Iteratoren nicht halten, wenn der Speicher wächst. Aber ein Allokator könnte 100-er-Blöcke holen…
    Naja, das normale new macht das gut genug, fürchte ich.


Anmelden zum Antworten