ArrayList
-
Als C++ Programmierer kenne ich nur ein Array und eine List, kann mir jemand erlären was eine ArrayList ist, wie sie intern aufgebaut ist, und warum man dafür einen Namen vergibt, der eine unmögliche Mischung zweier Datenstrukturen beschreibt? Aus der Java API werde ich nicht wirklich schlau.
Besten Dank
PI
-
List ist ein Interface, siehe dazu auch hier:
http://download.oracle.com/javase/tutorial/collections/interfaces/list.htmlNun kann man die Constraints die dieses Interface vorgibt mit mehreren Techniken implementieren:
http://download.oracle.com/javase/6/docs/api/java/util/List.html (siehe All Known Implementing Classes)Eine ArrayList ist dementsprechend das List-Interface implementiert mit Hilfe eines "normalen" Arrays (entspricht quasi std::vector). Die Java-Klasse Vector ist thread-safe, aber kaum mehr in neuen Projekten im Einsatz. Wenn ich etwas thread-safe haben will dann nehm ich Collections.synchronizedList()
MfG SideWinder
-
Ist eigentlich das gleiche wie std::vector. Es ist ein Array, dessen Grösse sich dynamisch ändern kann.
Ich denke sie heisst ArrayList, weil die Klasse das Interface List implementiert.
-
Und wieso implementiert ein Array(Vector) ein Interface, das List heißt?
-
314159265358979 schrieb:
Und wieso implementiert ein Array(Vector) ein Interface, das List heißt?
Weil http://en.wikipedia.org/wiki/List_(computing) nicht unbedingt http://en.wikipedia.org/wiki/Linked_list sein muss und erstmal auch nichts miteinander zu tun hat.
Das hat sich nur in C so eingebürgert, in C++ wurde das leider übernommen. Das wundert mich heute noch etwas, dass es in der STL keine klare Unterscheidung zwischen Interface und Implementierung von Containern gibt. In den meisten anderen Programmiersprachen hat eine Liste nicht unbedingt etwas mit verketteten Listen zu tun - auch wenn, wie auch in Java die LinkedList, eine verkettete Liste eine oft auftauchende Implementierung davon ist.
MfG SideWinder
-
Man könnte die Java Container auch nach Zugriffsart, sprich Random Acces, Forward Access, etc einteilen, anstatt sowas ähnliches wie einen "operator []" für jeden Container bereitzustellen. Der Sinn davon erschließt sich mir eh nicht.
-
Wohldefiniertes Interface geht da als Abstraktionselement wohl vor Zugriffsart auf einzelne Elemente. Vor allem weil sich Zweites durch Ersteres ja mitbestimmen ließe.
Falls sich dir tatsächlich der Sinn von Interfaces und dem Konzept eines ADT http://en.wikipedia.org/wiki/Abstract_data_type nicht erschließt solltest du dringend Programmiergrundlagenlektüre zur Hand ziehen (und zwar zu OO-Konzepten und nicht zu "Beginning Java" oder "Beginning C/C++").
MfG SideWinder
-
Ich weiß schon, wozu ein Interface gut ist, aber es hat keinen Sinn, einer LinkedList Pseudo-Random-Access zu verpassen, nämlich in O(n). Random Access läuft in O(1), bei einer Liste ist das einfach nicht möglich.
-
314159265358979 schrieb:
Ich weiß schon, wozu ein Interface gut ist, aber es hat keinen Sinn, einer LinkedList Pseudo-Random-Access zu verpassen, nämlich in O(n). Random Access läuft in O(1), bei einer Liste ist das einfach nicht möglich.
Trotzdem hat man sich in den meisten Programmiersprachen dafür entschieden einen direkten Zugriff auf das i. Element zu ermöglichen. Mir fallen da ganz schnell Java und Haskell ein. Natürlich ist es nicht empfehlenswert, und deshalb nehme ich natürlich eine passende Datenstruktur. Warum mich aber das System an sich davon abhalten muss auf das i. Element einer LinkedList zuzugreifen. Da lieber ein gemeinsames List-Interface.
MfG SideWinder
-
Ups, habe meinen Thread ganz vergessen.
Wenn ich dem Programmierer nicht bei jeder Datenstruktur RandomAccess erlaube,
ist er gezwungen, sich mit den Unterschieden auseinanderzusetzen, was man sowieso tun sollte.
Weiters werden dadurch viele Algorithmen schneller,
da man z.B. an bestimmte Funktionen nur Container mit RandomAccess übergeben kann (bzw Random-Access-Iteratoren).
-
314159265358979 schrieb:
Wenn ich dem Programmierer nicht bei jeder Datenstruktur RandomAccess erlaube,
ist er gezwungen, sich mit den Unterschieden auseinanderzusetzen, was man sowieso tun sollte.
Weiters werden dadurch viele Algorithmen schneller,
da man z.B. an bestimmte Funktionen nur Container mit RandomAccess übergeben kann (bzw Random-Access-Iteratoren).Warum sollte man random access nicht anbieten, wenn es technisch doch möglich ist? Vielleicht ergibt sich ja ein Anwendungsfall, bei denen man an vielen Stellen von einer LinkedList profitiert, an einer bestimmten Stelle jedoch random acces benötigt. Da ist es doch schön, dass man sich das nicht selber basteln muss.
Dein Argument mag ja stimmen, aber die Java-Philosophie ist eben nicht so sehr auf maximale Geschwindigkeit bedacht.
-
Dafür würde ich dann Iterator-Interfaces einführen, die jeweils eine Methode wie z.b. advance(int) haben. Damit kann man dann beliebig bewegen. Jeder muss sich damit außeinandersetzen und wenn man es trotzdem benötigt, kann man das dann explizit machen.