Exakte Unterschied zwischen diesen Elementen?

[DennisXX]

Es gibt ja eine ArrayList und eine LinkList. Beides kann glaube ich dazu verwendet werden, um Objekte in diesen Listen in einer Art Datenstruktur zu speichern. Worin besteht eigentlich der exakte Unterschied zwischen diesen beiden Dingen?

 

[Final_Striker]

Die Operationen wie einfügen oder suchen werde unterschiedlich schnell ausgeführt.

 

[eRaaaa]

"Eine ArrayList (das Gleiche gilt für Vector) speichert Elemente in einem internen Array. LinkedList dagegen speichert die Elemente in einer verketteten Liste und realisiert die Verkettung mit einem eigenen Hilfsobjekt für jedes Listenelement. Es ergeben sich Einsatzgebiete, die einmal für LinkedList und einmal für ArrayList sprechen.

• 
  Da ArrayList intern ein Array benutzt, ist der Zugriff auf ein spezielles Element über die Position in der Liste sehr schnell. Eine LinkedList muss aufwändiger durchsucht werden, und dies kostet Zeit.
• Die verkettete Liste ist aber deutlich im Vorteil, wenn Elemente mitten in der Liste gelöscht oder eingefügt werden; hier muss einfach nur die Verkettung der Hilfsobjekte an einer Stelle verändert werden. Bei einer ArrayList bedeutet dies viel Arbeit, es sei denn, das Element kann am Ende gelöscht oder – bei ausreichender Puffergröße – eingefügt werden. Soll ein Element nicht am Ende eingefügt
  oder gelöscht werden, müssen alle nachfolgenden Listenelemente verschoben werden.
• Bei einer ArrayList kann die Größe des internen Feldes zu klein werden. Dann bleibt der Laufzeitumgebung nichts anderes übrig, als ein neues größeres Feld-Objekt anzulegen und alle Elemente zu kopieren."

Quelle:
Galileo Computing :: Java ist auch eine Insel (8. Auflage) – 12.3 Listen

 

[DennisXX]

Ok danke. Und wie genau verhält sich eine Hashmap oder allgemein eine Map? Was genau hat diese für Vor- und Nachteile?

 

[Gast2]

Galileo Computing :: Java ist auch eine Insel (8. Auflage) – 12.8 Assoziative Speicher

 

[Wortraum]

[*]Die verkettete Liste ist aber deutlich im Vorteil, wenn Elemente mitten in der Liste gelöscht oder eingefügt werden; hier muss einfach nur die Verkettung der Hilfsobjekte an einer Stelle verändert werden. Bei einer ArrayList bedeutet dies viel Arbeit, es sei denn, das Element kann am Ende gelöscht oder – bei ausreichender Puffergröße – eingefügt werden. Soll ein Element nicht am Ende eingefügt oder gelöscht werden, müssen alle nachfolgenden Listenelemente verschoben werden.

Das wird zwar oft behauptet, ist aber falsch– oder, genauer gesagt, man muß hier differenzieren: Das eigentliche Einfügen ist schneller, aber um überhaupt erst einmal zur Mitte zu gelangen, müssen die Elemente bis dahin durchlaufen werden, und das kostet Zeit, so daß der komplette Vorgang recht lange dauert. ArrayList ist in der Regel auch hierbei schneller.

Interessant wird es hingegen, wenn häufig am Anfang Elemente eingefügt werden. Eventuell gibt es auch noch Unterschiede bei der Speicherplatzbelegung und der ‐fragmentierung, da für ArrayList ein großes Feld benötigt wird. Um das beurteilen zu können, fehlt mir aber das Wissen über die Interna der VM.

@DennisXX:
> Ok danke. Und wie genau verhält sich eine Hashmap oder
> allgemein eine Map? Was genau hat diese für Vor- und Nachteile?
Map ist eine Schnittstelle, HashMap eine implementierende Klasse; von Map kann man keine Objekte erzeugen, von HashMap schon.

Falls Du Dich nun fragst, wofür die Schnittstelle dient: Sie ist eine Art Vorlage, die angibt, über welche Methoden Maps anbieten müssen. Es gibt auch eine Schnittstelle List, die von ArrayList und LinkedList implementiert wird. Deswegen haben beide Methoden zum Einfügen und Löschen von Elementen, die die gleichen Siganturen haben (gleichen Namen und gleiche Parameter), so daß sie austauschbar sind. Lediglich die Interna, wie die Daten verwaltet werden, unterscheiden sich.