3. Verkettete Listen Beispiel, Einsatzgebiet?

Verkettete Listen Beispiel, Einsatzgebiet?

  • A

    Naja, das ist so nicht ganz richtig bzw. missverständlich ausgedrückt!

    Linked Lists sind dann nötig, wenn man Elemente innerhalb des Anfangs und Ende der Liste einfügen oder löschen will! Das ist schon was anderes als ein einfaches ändern. Denn das Ändern eines Elements in einem Vektor/Array ist nicht langsamer, weil da nichts umorganisiert werden muß.

    0
  • ?

    Mal ein praxisnahes Beispiel:

    Du schreibst dein eigenes Strategiespiel. Da kann man natürlich Einheiten bauen, soviele wie man mag (Ja, Ruhe ich hörs schon kommen!).
    Hättest du jetzt nur ein Array wie units[100] dann wäre halt bei Unit100 Schluß, bei den Listen kannst du immer weitere, neue Elemente anhängen und so das Problem lösen.

    0
  • A

    Was ist das denn für ein Schwachsinn? Dein Beispiel ist Praxisfern, ferner geht es nicht. Dafür kann man locker Vector nehmen, wer es will, kann sogar ein Array nehmen, muß nur den Krämpel umkopieren. Dafür _muss_ man _nicht_ Linked Lists nehmen... kann man! Aber man kann vieles wenn man will.

    0
  • ?

    Artchi schrieb:

    Was ist das denn für ein Schwachsinn? Dein Beispiel ist Praxisfern, ferner geht es nicht. Dafür kann man locker Vector nehmen, wer es will, kann sogar ein Array nehmen, muß nur den Krämpel umkopieren. Dafür _muss_ man _nicht_ Linked Lists nehmen... kann man! Aber man kann vieles wenn man will.

    Du bist auch so ein kleiner Erbsenzähler, mehr nicht. Man kann es auch auf 5000 verschiedene Arten lösen, von mir aus kannst du auch freudig ein Array nehmen und rumkopieren wenn du Spaß daran hast, aber eine mehr als gängige Lösung bleibt die doppelt verkettete Liste.

    Hab ich irgendwo geschrieben man muss sie dafür nehmen? Nein? Also lies nächstes Mal richtig oder schreib am besten gar nichts.

    0
  • H

    Hi Artchi, stimmt das habe ich gemeint - wenn auch unglücklich ausgedrückt.

    0
  • P

    @diepraxis: dein Beispiel ist wirklich nicht so toll, weil es den Eindruck erweckt, dass Arrays immer eine feste Größe haben. Kommt zumindest bei mir so rüber wenn ich das les.

    Aber solche Antworten("Was ist das denn für ein Schwachsinn?") müssen auch nicht sein ... .

    0
  • P

    interessiert mich auch, wann man besser linked lists nimmt und wann nicht!
    ich spekulier jetzt mal, dass bei sehr grossen listen, in die oft eingefügt bzw. gelöscht werden muss so ein (dynamisch wachsender) vektor ungünstiger wird, weil bei jeder einfüge- oder lösch-operation alle folgenden elemente um eins rauf- bzw. um eins runtergeschoben werden müssen. bei sehr grossen listen werden das dann ne menge ops, oder? ist das so?

    was mich noch interssieren würde ist ob man mit linked lists eigentlich genauso gut binäres suchen verwenden kann, wie bei arrays?
    ist es so, dass, wenn man bei arrays auf die mitte der liste zugreifen will, nur ein oder zwei ops braucht? (einmal hälfte=grösse/2 und dann array[hälfte] )?
    bei linked lists müsste man sich dagegen doch von element zu element hangeln, bis man in der mitte angekommen wäre, oder? dann wäre binäres suchen nicht mehr so günstig, oder wie?

    mfg
    prokaion

    0
  • F

    Also generell kann man natürlich immer anstatt einer Linked List ein Array nehmen. Da ich in diesem Halbjahr eine billige (deswegen weils eh einfach ist) ZL (= zusätzliche Lernleistung) über diese Geschichte machen muss sag ich mal wie ich es glaube zu wisse:

    Hauptunterschiede:

    ➡ Array:
    - Feste Größe, bei umdimensionierung müssen alle Elemente kopiert werden
    - Schneller Zugriff auf jedes Element
    - Schlecht geeignet für Elemente die sortiert sein sollen, da auch hier eventuell immer viel geändern / verschoben werden muss
    - Kein Overhead

    ➡ (Double- / Multiple-) Linked List:
    - Größe kann während der Laufzeit verändert werden ohne dass Elemente verschoben werden müssen (entfernen, einfügen, Listen zusammenführen etc...)
    - Elemente können nicht direkt angesprochen werden, mann muss sich ständig zum richtigen Element durch-iterieren
    - Gut geeignet für sortierte Elemente, da neue Elemente an der richtige Stelle eingefügt werden können ohne den Rrest zu beeinflussen
    - Produziert Overhead von PointerGröße * Links pro Node

    Hauptkriterien zur Entscheidung:

    - Brauche ich einen direkten Zugriff auf Elemente? -> Array
    - Sollen die Elemente ständig sortiert sein -> List (oder auch ein Baum)
    - Werden oft neue Elemente eingefügt / entfernt? -> List
    - Ist die Größe schon vor dem Erstellen bestimmbar, oder wird nur wenige male umdimensioniert -> Array

    Anmerkung:
    Ich weiß nicht wie std::vector arbeitet, aber std::string reserviert immer ein bishchen SPeicher im voraus. Zusätzlich zu dem std::vector gibts in der STL noch std::deque, das ist ein Container der als ,,Array of Arrays`` implementiert ist.

    Hoffe das ist Ok so.
    Gruß

    0
  • A

    FireFlow schrieb:

    Anmerkung:
    Ich weiß nicht wie std::vector arbeitet,

    Also sowas sollte man wissen. vector hat intern einfach nur einen Array, und wenn der voll ist, wird ein neues Array mit new angefordert und der alte in das neue umkopiert. Damit das nicht überhand nimmt, kann man Speicher vorreservieren.

    Native Arrays sollte man nur benutzen, wenn man sich sicher ist, das sich dieses in der Größe nicht mehr ändern wird. Ansonst: Vector!!! Hab ich schon mal gesagt, in einem der Postings!

    Linked Lists nur dann nötig, wenn zwischen Anfang und Ende des Containers Elemente gelöscht oder eingefügt werden. (ich wiederhole mich, falls ihr es gemerkt habt!)

    Weiß nicht was daran so schwer zu verstehen ist? 😕 🙄

    0
  • ?

    Linked-Lists sind auch nützlich für das Anfügen/Löschen von Elementen am Anfang und/oder am Ende. Habe dazu auch nen Beispiel: in einem Programm musste ich die letzten x Zeichen, die der Benutzer eingegeben hat, speichern und da ist ne Linked-List extrem praktisch, da ich vorne anfügen und hinten löschen kann, ohne die anderen Elemente herumkopieren zu müssen.

    Für diesen Zweck kann man auch eine deque verwenden, aber dies ist nur ein Container-Adapter (verwendet intern einen anderen Container).

    0
  • P

    @FireFlow:
    cool erklärt! prägnant und klar!!

    danke! 👍

    0
  • F

    Artchi schrieb:

    FireFlow schrieb:

    Anmerkung:
    Ich weiß nicht wie std::vector arbeitet,

    Also sowas sollte man wissen. (...)

    Ja ich weiß schon dass es ein Array ist welches dann immer erweitert wird 🙄 Das war im Bezug aufs Vorreservieren von Speicher wie bei std::string.

    Gruß

    0
  • N

    FireFlow schrieb:

    Ich weiß nicht wie std::vector arbeitet

    das ist nur ne verpackung von malloc und realloc. viel mehr steckt nicht dahinter

    0
  • W

    Artchi schrieb:

    (ich wiederhole mich, falls ihr es gemerkt habt!)

    Nicht nur dich, sondern auch andere... warum eigentlich?

    0
Anmelden zum Antworten