Unterschied Arrays, Listen, Mengen

O2016

Bekanntes Mitglied
1. Kann ich die 3 Typen miteinander vergleichen?

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?
 

httpdigest

Top Contributor
Listen:
- Aufwand O(n), muss immer komplett durchiterieren
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.

Siehe z.B. rechts oben bei:
- https://en.wikipedia.org/wiki/Skip_list
- https://en.wikipedia.org/wiki/Hash_table
 

JuKu

Top Contributor
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.

Bezüglich Sets:
Nicht ganz. Lediglich HashSet nutzt eine Hash-Tabelle: https://docs.oracle.com/javase/7/docs/api/java/util/HashSet.html
Manche Implementierungen nutzen auch einen Baum: https://docs.oracle.com/javase/7/docs/api/java/util/TreeSet.html

Naja, das wichtigste hast du bereits abgedeckt.
Du könntest dir aber noch die anderen Java Collections anschauen und vergleichen:
1024px-Java.util.Collection_hierarchy.svg.png

Quelle: https://en.wikipedia.org/wiki/Java_collections_framework

EDIT:
@httpdigest war schneller.^^
 

krgewb

Top Contributor
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.
 

mrBrown

Super-Moderator
Mitarbeiter
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.
Das ist weder für Java richtig, noch generell ;)

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.
Welche Version, welcher JIT und welcher GC? ;)

Magst du bei Zeiten mal den Benchmark zeigen? Würde mich interessieren...
 
X

Xyz1

Gast
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
Der JIT ist eher so die letzte Instanz die etwas machen könnte (kein muss). spezifiziert, wo was (wann) wie liegt (in welcher form) ist es schon....

Aber ich betone auch wieder das es wichtig ist alle Grundlagen begriffen zu haben.:mad:
 

mrBrown

Super-Moderator
Mitarbeiter
Der JIT ist eher so die letzte Instanz die etwas machen könnte (kein muss). spezifiziert, wo was (wann) wie liegt (in welcher form) ist es schon....
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?
 
X

Xyz1

Gast
Mich an der Diskussion beteiligen und den Beitrag von @JuKu (partiell) korrigieren....

Hinaus wollte ich gar nicht. (Dunkel, kalt, nass und windig draußen <- Scherz!)
 

O2016

Bekanntes Mitglied
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?
 

mrBrown

Super-Moderator
Mitarbeiter
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.
Generell ist der Aufwand für einen Zugriff auf ein Element bei verketteten Listen O(n).

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.

EDIT: O(1) zum korrekten O(n) geändert
 
Zuletzt bearbeitet:

httpdigest

Top Contributor
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.
 

httpdigest

Top Contributor
Generell ist der Aufwand für einen Zugriff auf ein Element bei verketteten Listen O(1).
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.
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
H Arrays: Größten Zahlen Unterschied herausfinden Java Basics - Anfänger-Themen 20
D Unterschied == und equals in Arrays Java Basics - Anfänger-Themen 2
tanja Der Unterschied Zwischen Arrays in Java und ADA Java Basics - Anfänger-Themen 11
L Unterschied zwischen Objekten, Arrays und Strings Java Basics - Anfänger-Themen 2
MoxMorris Integer.MAX_VALUE und Double.MAX_VALUE Unterschied Java Basics - Anfänger-Themen 3
R Java boolean Unterschied " == " und " = " Java Basics - Anfänger-Themen 3
berserkerdq2 Größter unterschied von extends thread und implements runnable? Java Basics - Anfänger-Themen 2
P Unterschied Installation von zipped JDK vs Installer-JDK (auf Windows)? Java Basics - Anfänger-Themen 2
S Unterschied zwischen Denkweisen Java Basics - Anfänger-Themen 13
M Unterschied Integer.toString(x) und x.toString() Java Basics - Anfänger-Themen 22
Ras Unterschied zwischen parser xml and api xml Java Basics - Anfänger-Themen 7
K Unterschied Information Hiding und Kapselung? Java Basics - Anfänger-Themen 2
X Was ist der Unterschied zwischen materialisierten und nichtmaterialisierten Attributen einer Klasse? Java Basics - Anfänger-Themen 1
jhCDtGVjcZGcfzug Was ist der Unterschied zwischen diesen Quellcodes? Java Basics - Anfänger-Themen 3
G Methoden wo ist der Unterschied?? Java Basics - Anfänger-Themen 11
D Unterschied charAt() substr() Java Basics - Anfänger-Themen 3
Y Unterschied zwischen WindowBuilder und herkömmlichen erstellen des GUI´s? Java Basics - Anfänger-Themen 9
U Worin besteht der Unterschied zwischen call by reference und call by value? Java Basics - Anfänger-Themen 14
H Unterschied Konstruktor und Klassenname x = new Klassenname; Java Basics - Anfänger-Themen 3
H .jar unterschied .class Java Basics - Anfänger-Themen 3
E Unterschied zwischen new und import Java Basics - Anfänger-Themen 5
K Unterschied for-Schleife Java Basics - Anfänger-Themen 14
B Unterschied zwischen (List<T> a) und (T[] a) Java Basics - Anfänger-Themen 7
M Schlüsselworte Unterschied: String.matches und Pattern.compile Java Basics - Anfänger-Themen 2
G Unterschied Instanz- Klassenvariable Java Basics - Anfänger-Themen 11
C Methoden Unterschied zwichen public int, public static int und public static void Java Basics - Anfänger-Themen 2
Aprendiendo Unterschied zwischen Referenzvariable und Instanzvariable. Java Basics - Anfänger-Themen 2
H Unterschied BufferedReader und BufferedInputStream Java Basics - Anfänger-Themen 4
N Unterschied von Post- und Preinkrement Java Basics - Anfänger-Themen 3
N Unterschied zwischen Checked und Unchecked Exceptions Java Basics - Anfänger-Themen 12
T Unterschied dynamischer und statischer Laufzeittyp Java Basics - Anfänger-Themen 1
schoenosrockos Unterschied zwischen Objekten und vererbungen Java Basics - Anfänger-Themen 1
D Unterschied Date - Calendar Java Basics - Anfänger-Themen 1
J Variablen Unterschied zwischen lokalen-, Instanz-, Klassenvariablen Java Basics - Anfänger-Themen 6
J Warum ist das ein Unterschied (Integer / int) Java Basics - Anfänger-Themen 2
S Erste Schritte Unterschied "if" und "else if" Java Basics - Anfänger-Themen 27
F Erste Schritte Unterschied: Array "leer" / "null" Java Basics - Anfänger-Themen 3
V Unterschied x++ und x=x++ Java Basics - Anfänger-Themen 6
O Unterschied Baum <-> Automat Java Basics - Anfänger-Themen 2
A Klassen Unterschied Warteschlange, Stapel und Liste Java Basics - Anfänger-Themen 3
L Unterschied zwischen Klassen - und Instanzvarbiablen Java Basics - Anfänger-Themen 1
M Wo liegt der Unterschied? Deklaration Klasse oder Konstruktur Java Basics - Anfänger-Themen 3
S Unterschied print() und println() Java Basics - Anfänger-Themen 3
S Unterschied .jar Datei ausführen und junit Testfall... Java Basics - Anfänger-Themen 3
S Datentypen Unterschied elementare und zusammengesetzte/strukturierte Datentypen Java Basics - Anfänger-Themen 5
M Unterschied zwischen Classpath eines Eclipse Projektes und dem CLASSPATH? Java Basics - Anfänger-Themen 3
S Unterschied Ausführung in IDE <-> Befehlszeile Java Basics - Anfänger-Themen 0
C Unterschied Objekte! Java Basics - Anfänger-Themen 13
D Unterschied zwischen double und Double Java Basics - Anfänger-Themen 4
Q Unterschied zwischen static und keinem Modifier Java Basics - Anfänger-Themen 15
A Unterschied Textdatei und Quelltextdatei Java Basics - Anfänger-Themen 5
K Unterschied zwischen Jar, war und ear Dateien Java Basics - Anfänger-Themen 3
R Erste Schritte Unterschied Array-Parameter zu Array als Parameter? Java Basics - Anfänger-Themen 7
V Unterschied Array & ArrayList Java Basics - Anfänger-Themen 13
D Geschwindigkeits unterschied bei import? Java Basics - Anfänger-Themen 13
T Unterschied zwischen Integrationstest und JUnit test? Java Basics - Anfänger-Themen 12
L Unterschied zu C++ Java Basics - Anfänger-Themen 6
A Unterschied JDK SDK Java Basics - Anfänger-Themen 4
L Objekterzeugung Unterschied..? Java Basics - Anfänger-Themen 6
K Unterschied zwischen break und continue in einer Schleife Java Basics - Anfänger-Themen 14
B Klassen Unterschied Konstruktoren. Java Basics - Anfänger-Themen 3
A Exakte Unterschied zwischen Java EE und Java SE? Java Basics - Anfänger-Themen 4
J Unterschied zwischen statische und nicht statische Methoden? Java Basics - Anfänger-Themen 14
S Interface Unterschied: setContentPane() & getContentPane().add Java Basics - Anfänger-Themen 5
Helgon Unterschied runnable und normale jar Java Basics - Anfänger-Themen 6
D Unterschied bidirectional unidirectional Java Basics - Anfänger-Themen 10
F Interface Unterschied von Attributen und Methoden bei abstrakten Klassen und Interfaces Java Basics - Anfänger-Themen 5
O Java unterschied zwischen Interface und Interface_Referenzen!!?? Java Basics - Anfänger-Themen 7
I Unterschied Lizenz EPL und LGPL Java Basics - Anfänger-Themen 7
P Unterschied Windowclosed / WindowClosing Java Basics - Anfänger-Themen 10
J scheduleAtFixedRate scheduleWithFixedDelay Unterschied? Java Basics - Anfänger-Themen 17
S Erste Schritte Grundsatzfragen Unterschied Java / PHP Java Basics - Anfänger-Themen 6
P Unterschied JRE innerhalb/ außerhalb des JDK Verzeichnisses? Java Basics - Anfänger-Themen 5
H printf: Unterschied %f und %g Java Basics - Anfänger-Themen 5
M Unterschied SDK 1.4 und 1.6 Java Basics - Anfänger-Themen 5
S Unterschied java.util.prefs / java.util.Properties Java Basics - Anfänger-Themen 3
J unterschied zwischen awt und swing Java Basics - Anfänger-Themen 6
T Unterschied in Zahlendarstellungen Java Basics - Anfänger-Themen 2
F Unterschied JPanel und JFrame Java Basics - Anfänger-Themen 5
K Unterschied Klassen- und Instanzattribute Java Basics - Anfänger-Themen 4
L Unterschied Konstruktor / Getter Setter Java Basics - Anfänger-Themen 13
S Unterschied Comparable und Comparator Java Basics - Anfänger-Themen 2
C unterschied generische typen und supertypen als methodenparameter Java Basics - Anfänger-Themen 3
J Instanzvariablen - Lokale Variablen - warum der Unterschied? Java Basics - Anfänger-Themen 5
P Unterschied dieser 2 code Zeilen Java Basics - Anfänger-Themen 12
I Datentypen Unterschied in Deklaration von ArrayList Java Basics - Anfänger-Themen 26
G Unterschied e extends y vs ? extends y Java Basics - Anfänger-Themen 5
M Unterschied append / write aus der Klasse Writer Java Basics - Anfänger-Themen 2
M unterschied OutpuStreamWriter und BufferedWriter Java Basics - Anfänger-Themen 5
B Unterschied zwischen String & char Array? Java Basics - Anfänger-Themen 5
J Unterschied Instanzattribut und Referenzvariable Java Basics - Anfänger-Themen 4
J Unterschied bei Schleifen Java Basics - Anfänger-Themen 2
B Was ist der unterschied zwischen Singleton und Strategy? Java Basics - Anfänger-Themen 6
B Variablen: unterschied zwischen Klassen und Instanzvariable Java Basics - Anfänger-Themen 2
W Unterschied JFrame und JLabel bezüglich Layout? Java Basics - Anfänger-Themen 2
B Generische Vererbung was ist der Unterschied? Java Basics - Anfänger-Themen 4
B ArrayList generisch? was ist der Unterschied? Java Basics - Anfänger-Themen 4
H Unterschied zwischen 2 Date in Sekunden am einfachsten? Java Basics - Anfänger-Themen 5
ModellbahnerTT Unterschied zwischen zwei Frame close Varianten Java Basics - Anfänger-Themen 3
D Unterschied innere Klasse/ anonyme innere Klasse Java Basics - Anfänger-Themen 7

Ähnliche Java Themen

Neue Themen


Oben