ArrayList oder LinkedList

[Mariexshhx]

was von beidem benötigt mehr Speicher ?

 

[KonradN]

was von beidem benötigt mehr Speicher ?

Spielt das eine Rolle?

Aber da es vermutlich eine Frage aus Studium oder Schule ist: Was für Gedanken hast Du Dir dazu gemacht? hast Du Dir schon überlegt, was die beiden Klassen genau wie implementieren?

Daraus kannst Du dann ggf. ableiten, unter welche Umständen welche Implementation günstiger ist.

 

[Mariexshhx]

Spielt das eine Rolle?

Aber da es vermutlich eine Frage aus Studium oder Schule ist: Was für Gedanken hast Du Dir dazu gemacht? hast Du Dir schon überlegt, was die beiden Klassen genau wie implementieren?

Daraus kannst Du dann ggf. ableiten, unter welche Umständen welche Implementation günstiger ist.

Ich möchte 1000 alte Dokumente, die ich im Archiv der Universität verstaut
habe, digital speichern und niemals wieder anrühren, dabei aber trotzdem
möglichst wenig Speicherplatz verbrauchen.


ich habe das Szenario und eine LinkedList besteht aus Listobjekten und eine Arraylist intern aus einem Array und wenn nicht mehr genug Platz im Array ist wird ein neues Array angelget welches doppelt so viel Platz hat wie das alte und es wird vom alten rüberkopiert ... also würde ich sagen, weil man ja möglichst geringen Speicherverbrauch haben will und bei der verdopplung des Arrays möglichweise nicht den ganzen Platz nutze wäre die LinkedList besser ....

 

[Jw456]

Und wenn du den Rechner neu starten musst erstellst du deine Liste neu.
Da wäre wohl eine DB besser geeignet.

 

[Mariexshhx]

Und wenn du den Rechner neu starten musst erstellst du deine Liste neu.
Da wäre wohl eine DB besser geeignet.

es ist nur nach ArrayList oder LinkedList gefragt

 

[KonradN]

ich habe das Szenario und eine LinkedList besteht aus Listobjekten und eine Arraylist intern aus einem Array und wenn nicht mehr genug Platz im Array ist wird ein neues Array angelget welches doppelt so viel Platz hat wie das alte und es wird vom alten rüberkopiert ... also würde ich sagen, weil man ja möglichst geringen Speicherverbrauch haben will und bei der verdopplung des Arrays möglichweise nicht den ganzen Platz nutze wäre die LinkedList besser ....

Das ist doch viel zu ungenau.

Beschreibe einmal, was für Platz für eine LinkedList brauchst. Was wird da gespeichert?
Und auch bei der ArrayList - da hast du wenigstens schon etwas an Informationen aber noch viel zu ungenau.

Du meinst wohl, dass man da einen "worst case" betrachten kann und dann hat man ein doppelt so großes Array wie notwendig, so dass man bei n Elementen 2*n an Platz (für Referenzen) braucht.

Jetzt musst Du nur noch eine ähnlich genaue Angabe zu der LinkedList aufstellen.

 

[Neumi5694]

In anbetracht der Tatsache, dass jedes deiner Dokumente bei weitem größer ist als ein Array, ist die Frage eigentlich obsolet.
Jedes Feld in deinem Array beinhaltet nichts weiter als eine Speicheradresse. Sagen wir mal, das Array hat eine Größe von 2000 (1000 Dokumente x 2). Dann hast du im schlimmsten Fall (noch gar kein Dokument in der Liste) einen Verlust von du hast 2000*8 Byte = 16000 Byte Verlust, das ist weniger als ein Cluster auf den meisten Festplatten.

Mit einer Linkedlist hast du so gesehen gar keinen Verlust. Anstatt eines Arrays von Speicheradressen hat jedes Element deiner Liste genau eine Folgespeicheradresse (und gegebenenfalls eine auf das vorige Element).

Du kannst schon mit dem Konstruktor von Anfang an oder zu einem beliebigen Zeitpunkt mit ensureCapacity festlegen, wie groß das Array in deiner ArrayList sein soll. Wenn du die Anzahl an Dokumenten kennst, sparst du so das umkopieren, was aber vernachlässigbar kurz ist (System.arraycopy ist ein sehr schnell ausgeführter Befehl).
Außerdem bietet ArrayList eine Methode, um das Array auf die tatsächlich genutzte Anzahl von Einträgen zu verkleinern.

Eine LinkedList würde ich wirklich nur dann verwenden, wenn sie zwingend notwendig ist und wo es garantier auch keine Nullelemente geben kann. Früher zu meinen Java-Anfangszeiten hab ich damit gearbeitet, aber der Aufwand ist so ungeheuer viel größer ... der einzige Vorteil, den sie hat, ist von einem Element auf das nächste zugreifen zu können. Ich hab gelernt, ohne diese Funktion leben zu können. Für alles andere ist eine ArrayList besser geeignet.

Dehalb mein Tip: Wähl die Listenart, die dir das Arbeiten vereinfacht. Pfeif auf den Speicher.

 

[KonradN]

Mit einer Linkedlist hast du so gesehen gar keinen Verlust. Anstatt eines Arrays von Speicheradressen hat jedes Element deiner Liste genau eine Folgespeicheradresse (und gegebenenfalls eine auf das vorige Element).

Das mit dem Verlust sehe ich etwas anders. Die Frage ist ja ganz deutlich gewesen und ich ärgere mich, dass da vom TE nichts konkretes gekommen ist - trotz allem nachhaken.

Was man z.B. auch Laienhaft ohne tiefen Einblick sehen sollte:
- Die ArrayList hast eine Instanz für die ArrayList und dann eine Referenz auf das Array. Man kann dann noch schauen, was für Variablen noch benötigt werden, aber man will den Speicherverbrauch für n Elemente haben und da kann man einzelne Variablen ignorieren - zumindest beim ersten Blick. Das Array hat eine Größe von n (Arraygröße passt genau) bis 2*(n-1) (Beim vorletzten Element war das Array voll und wurde daher verdoppelt für das letzte Element) - einzelne Variablen ignorieren wird gerade, also aus dem 2n-2 machen wir ein 2n. (z.B. an Referenzen - wir betrachten einfach ein Referenz-Datentyp.)

- Die LinkedList wird deutlich komplexer:
a) Wir haben wieder die Instanz der eigentlichen LinkedList. Mit paar einzelnen Variablen die wir hier auch nicht im Detail betrachten.
b) Für jedes der n Elemente haben wir nun eine zusätzliche Instanz. Damit kommt direkt der Overhead der Instanz - und das n mal! Wie hoch der Speicherverbrauch genau ist, ist etwas komplexer. Vereinfachen wir es massiv: Dann haben wir in der Instanz aber 3 Referenzen: Vorgänger / Nachfolger Node und dann die Referenz zu dem Wert. Mit dieser vereinfachten Variante wären wir also schon bei 3n an Anzahl Referenzen. Und das ist extrem niedrig geschätzt!

Somit haben wir in der LinkedList deutlich mehr Speicherbedarf als in der ArrayList. Da ist also ein deutlicher Faktor zu sehen (Wenn man bei jeder Instanz nur noch eine Referenz auf die Klasse hinzu nehmen würde, wären wir schon beim Faktor 2 zum worst Case. Zum Best Case der ArrayList wäre es damit Faktor 4! - Aber nicht vergessen: ist eigentlich noch viel Schlimmer )

Das wäre aus meiner Sicht die Antwort auf die Frage, um die es in diesem Thread ging:

was von beidem benötigt mehr Speicher ?

Wann was genutzt werden sollte ist dabei einfach uninteressant. Aber ja - das würde ich ebenso sehen wie @Neumi5694

 

[temi]

Hier ist ein Beitrag zu diesem Thema mit hübschen Grafiken und so

https://medium.com/metrosystemsro/java-memory-footprint-part-2-8791679178e2

 

[berndoa]

Und wenn wir noch wissen dass es genau 1000 Einträge sind, kann man auch einfach ein Array mit Länge 1000 nehmen dessen Einträge halt von einem sinnvollen Datentyp sind. Just saying

 

[Neumi5694]

Und wenn wir noch wissen dass es genau 1000 Einträge sind, kann man auch einfach ein Array mit Länge 1000 nehmen dessen Einträge halt von einem sinnvollen Datentyp sind. Just saying

Was genau das gleiche bieten würde wie eine entsprechend befüllte ArrayList, nur eben ohne Collections-Zugriffsmethoden