ArrayList, LinkedList oder Set

[redbomber]

Hi zusammen, ich habe mal wieder eine Frage:

Momentan versuche ich den passenden Datentyp zu finden, der meinen Anforderungen gerecht wird.

Angenommen mir stehen eine ArrayList<Objekt>, LinkedList<Objekt> oder Set<Objekt> zur Verfügung.
Ich muss immer über die komplette Collection iterieren.
Ebenso muss oft Elemente hinzufügen.
Weiter muss ich oft contains(Objekt) aufrufen.

welche Datentyp ist hier der passende?

Wenn die Methode --> contains(Objekt) oft aufgerufen wird, vermute ich Set<Objekt>
Da ich die Collection oft erweitern muss würde ich sagen LinkedList oder Set
Da ich keinen Index Zugriff benötige ist eine ArrayList nicht unbedingt besser hier oder?

 

[Wildcard]

contains wäre bei LinkedList langsam. Wahlfreies einfügen ist bei ArrayList sehr langsam. HashSet wäre wohl das günstigste, aber du hast und nicht verraten, ob du eine Liste, oder eine Menge benötigst.

 

[L-ectron-X]

Ein Set ist sehr sehr schnell beim Einfügen von Daten
Ich würde jetzt eher zu einem Set tendieren.

 

[redbomber]

äh wie meinst du das genau mit Liste oder Menge?

Also meine Liste wird zu Beginn schon nach einer gewissen Eigenschaft sortiert und diese Ordnung sollte die Liste beibehalten.

Ich denke dieses Problem habe ich dann sobald ich ein Set verwende...

 

[Ark]

Ich hoffe, es hier anständig erklärt zu haben: http://www.java-forum.org/java-basics-anfaenger-themen/80467-hashmap-mit-filo.html#post497400

Ark

 

[diggaa1984]

hm ists denn ein zeitkritischer Vorgang der alle x Millisekunden Daten manipuliert? Oder ist häufig nur im Sinne von "der nutzer wird diese Art Manipulation am meisten durchführen" .. zB .. ewig viel in Tabellen eintragen und ändern etc. Da ists ja relativ egal welche Datenstruktur rumliegt, da der Nutzer hier die langsamste Einheit darstellt. Und eh der von einer Zellen zur nächsten kommt und was neues einträgt kannst deine Daten zich-mal kopieren, umsortiern, iteriern ^^

Vielleicht könnte hier das Szenario mehr Aufschluss über die korrekte Struktur liefern

 

[Wildcard]

äh wie meinst du das genau mit Liste oder Menge?

Also meine Liste wird zu Beginn schon nach einer gewissen Eigenschaft sortiert und diese Ordnung sollte die Liste beibehalten.

Allgemein sind Sets Mengen und Mengen haben keine Ordnung und es gibt jedes Element nur einmal (anders als bei Listen).
Wenn alle Elemente bei dir einzigartig sind, scheidet Set allerdings noch nicht ganz aus. Es gibt da zB noch TreeSet, das sortiert anhand der natural order (Elemente implementieren Comparable), oder anhand eines von dir gesetzten Comparators.
Also die Hauptfrage: sind deine Elemente nur einmal in der Collection?

 

[0x7F800000]

Hi zusammen, ich habe mal wieder eine Frage:

Momentan versuche ich den passenden Datentyp zu finden, der meinen Anforderungen gerecht wird.

Angenommen mir stehen eine ArrayList<Objekt>, LinkedList<Objekt> oder Set<Objekt> zur Verfügung.
Ich muss immer über die komplette Collection iterieren.
Ebenso muss oft Elemente hinzufügen.
Weiter muss ich oft contains(Objekt) aufrufen.

welche Datentyp ist hier der passende?

Wenn die Methode --> contains(Objekt) oft aufgerufen wird, vermute ich Set<Objekt>
Da ich die Collection oft erweitern muss würde ich sagen LinkedList oder Set
Da ich keinen Index Zugriff benötige ist eine ArrayList nicht unbedingt besser hier oder?

Über alles iterieren ist überall O(n) denke ich mal.
Insert ist bei ArrayList sterbenslangsam, bei LinkedList & HashSets in konstanter Zeit machbar, bei Bäumen wie ThreeSet etwa in O(ln(n)) machbar, evtl. schneller.
Contains ist bei Listen immer vergleichsweise lahm, linear. Bei HashSet dagegen konstant, bei Bäumen wieder O(ln(n)).
Aber du willst es dauernd im sortierten Zustand halten...
Also kommen eigentlich nur diese Beiden Implementierungen in Frage:
SortedSet (Java Platform SE 6)
Wenn du mehrfach vorkommende elemente drin haben willst, dann musst du einfach auf diesen Strukturen basierende SortedMaps nehmen:
SortedMap (Java Platform SE 6)
Dann nimmst du das eigentlich zu speichernde Objekt als schlüssel, und die Anzahl speicherst du als Wert. (Witzigerweise ist es intern grad andersherum: die sets basieren auf Maps, aber diese Unstimmigkeit kehren wir mal zugunsten von DRY unter den Teppich )

 

[Ebenius]

Also kommen eigentlich nur diese Beiden Implementierungen in Frage:
SortedSet (Java Platform SE 6) [...]

*hust* sehr implementationsarme Implementierungen...

Ebenius

 

[0x7F800000]

All Known Implementing Classes: ConcurrentSkipListSet, TreeSet