Array:
- nicht erweiterbar (nur schwer mit Aufwand)
+ schnelle Zugriffszeit -> Aufwand O(1)
+/- ein Element kann mehrmals vorkommen
Listen:
- Aufwand O(n), muss immer komplett durchiterieren
+ kann beliebig erweitert werden
(ist sie doppelt verkettet, hat sie einen geringeren Aufwand, aber immer noch schlechter als Array)
+/- ein Element kann mehrmals vorkommen
Mengen: (Sets)
werden in einer Tabelle gespeichert. (Hash-Tabelle? oder auch andere Tabellen?)
+ ein Element kann nur einmal vorkommen
- fällt mir nichts ein
Falls das so richtig ist, was für Sachen gibt es noch die man miteinander mit denen vergleichen kann?
Aufwand wofür denn? Normalerweise vergleicht man konkrete Datenstrukturen anhand ihrer Speicherplatzkomplexität und der Laufzeitkomplexitäten der auf ihnen definierten Operationen. Üblich sind Operationen wie etwa Einfügen, Entfernen und Suchen. Eine Liste ist allerdings noch keine konkrete Datenstruktur, sondern eine abstrakte Datenstruktur. Man kann Listen auf soooo vielen unterschiedlichen Weisen implementieren (ArrayList, LinkedList, SkipList, ...) und daraus ergeben sich dann die konkreten Speicherplatz- und Laufzeit-Komplexitäten.
Ein Array ist normalerweise eine Aneinanderreihung von Objekten im Stack (Java ist hier eine Ausnahme, da liegen die meines Wissens auch im HEAP), während Listen prinzipiell im Heap liegen.
Die Arraygröße ist fest, allerdings kann man ein Array schon vergrößern, meistens indem man das Array in ein neues Array kopiert, z.B. mit System.arraycopy(), siehe https://www.tutorialspoint.com/java/lang/system_arraycopy.htm . Nutzt allerdings beides eig. (fast) keiner - mal abgesehen von der Spieleindustrie, wo du jede ns wegoptimieren willst.
Listen:
"Aufwand O(n), muss immer komplett durchiterieren"
Wie kommst du darauf? Wenn du ein list.get(0) aufrufst, erhälst du das erste Element. Listen sind unter der Haube auch nur Arrays in Java --> müsste wahrscheinlich auch O(1) sein. Lediglich das Iterieren über Listen ist Performance-lastiger, da hier die Verkettung zum Tragen kommt. Auch erzeugt das Iterieren (anscheinend durch den Iterator) mehr GC-Pressure (zumindest ergeben das meine eigenen Messungen), weshalb ich immer ein Array verwende, wenn es denn möglich ist.
Wenn du einer ArrayList ein paar Elemente hinzufüge und sie dir ausgeben lässt, dann siehst du, dass die Reihenfolge dieselbe ist. Bei einem HashSet hingegen kann keine Aussage über die Reihenfolge gemacht werden. Bei dem Hinzufügen eines Elementes ändert sich die Reihenfolge.
Ein Array ist normalerweise eine Aneinanderreihung von Objekten im Stack (Java ist hier eine Ausnahme, da liegen die meines Wissens auch im HEAP), während Listen prinzipiell im Heap liegen.
Der JIT kann sowohl mit Arrays als auch mit Listen machen, was er will, und theoretisch (und zT praktisch) können die nachher auf'm Stack, im Heap oder auch nur in Registern existieren.
Und in allen anderen Sprachen kommt es jeweils auf die Sprache an, wie und wi Listen und Arrays da liegen
Auch erzeugt das Iterieren (anscheinend durch den Iterator) mehr GC-Pressure (zumindest ergeben das meine eigenen Messungen), weshalb ich immer ein Array verwende, wenn es denn möglich ist.
Der JIT kann sowohl mit Arrays als auch mit Listen machen, was er will, und theoretisch (und zT praktisch) können die nachher auf'm Stack, im Heap oder auch nur in Registern existieren
Welche Instanzen gibts denn da sonst noch so, außer des JIT, welche entscheiden, wo welcher Speicher alloziert wird?
Wo ist definiert, wo ein lokales Array oder Listen liegen müssen?
Was ich bei Liste von O(n) meinte war eine verkettete Liste. Da muss ich ja komplett durch iterieren um auf den letzten Eintrag zu kommen. Ist eine ArrayListe auch eine verkettet Liste wenn ich mit get(i) zugreifen kann? Eigentlich doch nicht oder?
Nein, eine ArrayList ist keine verkettete Liste, sondern nutzt intern ein Array. Ist aber auch kein Array, sondern eben eine Liste.
Wenn es dir um abstrakte Datentypen geht, solltest du das deshalb aus der Betrachtung rausnehmen.
ArrayList ist keine verkettete Liste, weil es intern mit einem Array zum Halten/Speichern der Listenelemente implementiert ist. Das hat nichts mit der get(int) Operation zu tun, die ja auf dem abstrakten Datentyp (bzw. dem Interface java.util.List) definiert ist.
Somit wird get(int) also von jeder Klasse (direkt oder indirekt) implementiert, die auch das List Interface implementiert. Das hat nichts damit zu tun, ob es sich bei der Implementierungsklasse nun um eine verkettete Liste oder nicht handelt.
Nur wird die get(int) Methode dann halt unterschiedlich implementiert. Im Falle von ArrayList ist es eben eine einfache Array-Indexierung und im Falle der linked List dann eben ein Durchlaufen der Listenelemente.
Du solltest eigentlich wissen, dass das nicht korrekt ist.
Wenn wir mit "Zugriff auf ein Element" meinen: Gib mir das 'i'-te Element der Liste (bzw. gib mir das Element in der Liste, welches ein bestimmtes Prädikat erfüllt), dann ist der Aufwand O(n), denn im schlimmsten Fall (und das sagt das 'O' in O(n)) ist i=n (bzw. das Prädikat wird vom letzten Listenelement erfüllt) und die ganze Liste muss von Anfang bis Ende durchtraversiert werden.
Wenn wir natürlich bereits eine Referenz auf das Element, welches auch in der Liste gespeichert ist, haben, ist es natürlich O(1), aber das gilt natürlich für jede Datenstruktur und wir müssen dann ja überhaupt nichts mit der Liste machen.
