Wie funktioniert LinkedList arbeiten intern in Java?

Soweit ich weiß, wurde das Konzept einer verketteten Liste, ist ein Bündel von Objekt miteinander verbunden, indem ein 'weiter' und manchmal ein 'vorher' - Attribut, um die traverse Objekte.

Bemerkte ich in Java, können Sie ein LinkedList-Objekt...aber behandeln Sie es wie ein array/Liste/Reihenfolge mit den gleichen Methoden wie .add(), .get(), etc.

So, ist LinkedList intern ein array-like sequence?

InformationsquelleAutor sqram | 2011-11-23
  1. 13

    So, ist LinkedList intern ein array-like sequence?

    Nicht. Es ist eine Reihe von Instanzen von a private geschachtelte Klasse Entry, die next, previous und element Referenzen. Beachten Sie, dass Sie haben gefunden das sich selbst durch einen Blick in den Quelltext, die mit dem JDK.

    Der Grund, warum diese interne Struktur wird nicht ausgesetzt ist, dass es verhindert, dass die Struktur beschädigt werden und z.B. mit einer Schleife. Und der einheitliche Zugang über den List und Deque Schnittstellen erlaubt die polymorphe Verwendung.

    • +1: in Der Liste, die intern ein array-wie die Folge heißt ArrayList. 😉
    • -1: Es hängt davon ab, Ihre Programmierkenntnisse denke ich. Aus dem wikipedia-Artikel Verlinkten Listen: "Es kann auch langsam sein, und mit einer naiven Zuweisung, verschwenderisch, Speicher separat für jedes neue element, ein problem in der Regel gelöst mit Speicher-pools." -- Zur info, Speicher-pools sind die arrays, die Profis verwenden, um intern speichern von verknüpften Listen. Sie sind auch bekannt als slab-allocators.
    • Rache downvote, eh? Get over it. Erfahrene Profis lassen Sie sich nicht in internet-Haaren auf welcher Ebene eine Frage, die beantwortet werden sollten, auf.
    • Absolut nicht. Ich bin damit einverstanden, dass Ihre Antwort "Nein" ist korrekt, in den meisten Anwendungen und-Implementierungen, aber nicht alle. Sie können tatsächlich umzusetzen, verknüpfte Listen mit arrays, da die zugrunde liegenden Daten-Struktur in Fällen, in denen die Leistung sorgen-wie der wikipedia-Artikel sagt.
    • Blake Die Frage ist, über die spezielle Implementierung der LinkedList-Klasse bereitgestellt, die durch das Java-Collection-API. Eine array-basierte Implementierung ist ArrayList wie Peter erwähnt in seinem Kommentar hier.
    • sicher, aber die Frage war über die Java-standard-API-Klasse LinkedList, welche nicht mit arrays. Die JVM kann, aber wenn Sie darauf bestehen, zu "tiefer gehen", kann man genauso gut anfangen zu reden, wie der "zusammenhängenden Speicher" eines array ist wirklich nicht da um die Leistung zu verbessern, es ist interleaved zwischen physischen RAM-Modulen und wieder zwischen den einzelnen chips-
    • Es scheint, Sie sind nicht bewusst, dass es mehr als eine Implementierung des java-Collection-API.. haben Sie von Android gehört? Gehen Sie und überprüfen Sie den Android-Quellcode für die LinkedList gegenüber der source-code weiter oben verlinkt. Also Nein, der OP hat nicht angeben, eine bestimmte Umsetzung. Und Nein, eine array-basierte implementation ist nicht unbedingt eine arraylist-ich werde versuchen, diese ein letztes mal: ob Sie es glauben oder nicht, Sie können eine verknüpfte Liste mit Stücken von arrays. Ich habe dies getan, weil Sie einige der Vorteile von arrays (speed), mit einigen der Vorteile von linked LISTS (willkürliche Einfügungen).
    • Können wir uns darauf einigen, dass es nicht die eine Implementierung von LinkedList der Java-standard-Bibliothek? (wenn nicht, sollten Sie vielleicht rufen Sie Orakel und sagen Sie Ihnen, Sie können aufhören verklagt Google). Ich bin auch damit einverstanden, dass alle java-Implementierungen der Klasse LinkedList wahrscheinlich sind einfach verkettete Listen-aber das bedeutet nicht, dass Sie können nicht Ihre eigenen schreiben, die ein hybrid zwischen einem array und eine linkedlist (oder, dass jemand noch nicht hat..).

    InformationsquelleAutor Michael Borgwardt
  2. 4

    LinkedList ist eine Kette von Entitäten, in der jede Person weiß über die nächsten ein,
    so get(index) Betrieb erfordert das Durchlaufen dieser Kette mit Zähler.
    Aber diese Liste optimiert für das hinzufügen und löschen von der Lage (in dem Fall, wenn ich-element in der Liste oder löschen-element aus der Mitte verkettete Liste besser abschneidet)

    InformationsquelleAutor Stanislav Levental
  3. 4

    Einer LinkedList in Java funktioniert genauso wie man es erwarten würde, es zu tun. Wenn Sie mit den amtlichen Sammlungen LinkedList dann wird es in der Tat eine eine Reihe von Objekt miteinander verbunden, indem ein 'weiter' und manchmal 'Vorherige'.

    Und ja, es hat eine get(int index) Methode ist überraschend, denn es wäre nicht sehr effizient, da müssen Sie am Anfang beginnen und zählen Sie Ihre Weise oben in der Liste zu finden, die index - TEN Eintrag und das ist nicht das, was LinkedLists sind gut. Der Grund, warum es da ist, ist da LinkedList implementiert die Liste - Schnittstelle. Dies ist etwas, das Sie mit ALLEN Listen.

    Jedoch, würden Sie wahrscheinlich versuchen zu vermeiden, mit einer LinkedList, wenn die meisten Ihren Zugriff darauf ist durch die get(int index) Methode, der wäre eindeutig ineffizient. Sie wäre vielleicht noch besser, eine ArrayList.

    InformationsquelleAutor OldCurmudgeon
  4. 2

    ich weiß linkedlist ist wie das, was Sie sagte, im ersten Absatz. jedes Objekt hat zwei Referenzen, rief er in den vorherigen und es geht weiter.
    im Gegensatz zu Arrays, die arbeitet sequentiell (in C ist es genau das, gespeichert in der Reihenfolge. ich denke, dass java einfach nur das gleiche macht, das ist, warum können wir nicht die Größe eines Arrays), - Liste von verweisen. so logisch es funktioniert langsamer als array enthält.

    InformationsquelleAutor simaremare
  5. 1

    Ist es möglich zu implementieren, die ein Objekt, das funktioniert wie ein array, mit einer verlinkten Liste. Im Vergleich zu arrays, einige Operationen schneller und manche langsamer. Zum Beispiel, ruft get() für ein element in der Nähe des Ende sein könnte, sehr viel langsamer mit einer verlinkten Liste als ein array. Aber, es ist immer noch möglich.

    Auf der anderen Seite löschen Sie ein element aus der Mitte einer verknüpften Liste wird schneller sein als die entsprechende operation durchgeführt unter Verwendung von arrays.

    InformationsquelleAutor Greg Hewgill
  6. 1

    Nicht wirklich. Link-Liste wird zur Verfügung gestellt von der Sammlung und durch gutes design können Sie eine double linked list. Jetzt ist es nicht wie bei Arrays, denn diese Objekte werden nicht über Indizes verfügen, und sind nicht die Elemente innerhalb des Containers d.h. Liste. Daher gehen Sie durch die Bestimmung der nächsten und vorherigen und diktieren, was der nächste Schritt ist. Sie alle haben die gleichen Methoden, weil Sie wiederum sind Sammlungen, wie ich sagte.

    InformationsquelleAutor sys_debug
  7. 0

    So, ist LinkedList intern ein array-like sequence?

    KEINE Es ist Doppelt-verkettete Liste-Implementierung.

    InformationsquelleAutor Nisarg Patil
  8. -8

    Intern wird es mit einem sogenannten 'slab allocator' -- dies ist im Grunde eine verknüpfte Liste von kleinen arrays. Jedes mal, wenn Sie ein Objekt, prüft es, ob es Raum in der Platte, und wenn dem so ist, stellt das Objekt dort. Ansonsten weist es eine neue Platte und legt das Objekt in das erste element der Platte.

    Diese Technik minimiert Speicher-Allokation der Gemeinkosten -- wenn Sie fügen Sie eine Menge von Elementen zu einer verknüpften Liste, das wäre eine Menge von kleinen Speicherzuordnungen, die viel Zeit in Anspruch nehmen, und die slab-allocators minimieren, dass

    • Das ist einfach falsch. Ist Java nicht C++. Kleine Zuordnungen sind schnell. Folglich, die API-Implementierung verwendet keine tricks, Sie zu vermeiden.
    • Wo denkst du, dass die JVM wird der Speicher für jedes Objekt weist es? Glaubst du, die JVM aufrufen von malloc (), jedes mal? Garbage-Kollektoren arbeiten mit einem Speicher in Platten. Bitte erläutern Sie, wie Sie denken, Java Speicherzuweisung für verknüpfte Listen, ohne Platten-Speicher.
    • Aus der Dokumentation zu IBM ' s JVM: "Diese Abschnitte sind in der Regel implementiert, die als zusammenhängende Platten von nativen Speicher, der unter der Kontrolle der Java-Speicher-manager (enthält den garbage collector)."
    • lol @ "Kleine Zuordnungen sind schnell" - Sie sind nur schnell in Java wegen der JVM wurde die Zuweisung in Platten der native Speicher.
    • Blake war Die Frage darüber, wie Sie arbeiten intern in Java, nicht wie die JVM Speicher zugewiesen wird. Wie das funktioniert, hängt davon ab, JVM-Implementierung und wird normalerweise nicht der Punkt, der das Interesse der Programmierer, der will, um zu entscheiden, mit LinkedList oder nicht und wollen deshalb verstehen, wie es implementiert ist, mit allen vor-und Nachteilen.
    • Ich erklärte, wie Sie intern arbeiten. Ein Programmierer kennen muss, um über die Kosten und Vorteile, und in diesem Fall können Sie nicht richtig bewerten die Kosten, ohne zu wissen, ein wenig über, wie es funktioniert. Sie sollten nicht behandeln, die JVM als eine Magische black-box, die nur Wissenschaftler im weißen Kittel kennen-wissen, ein wenig über, wie die JVM und dem computer ermöglicht ein Programmierer, um eine Schätzung der Leistung von einem bestimmten Ansatz.
    • Blake, warum Dann nicht noch tiefer gehen und erklären, wie malloc() funktioniert? Was JVM-Implementierung zu tun, die Sie als Referenz verwenden? Es existieren 8 KiB JVMs, zu. Diese implementiert sind, sind SEHR einfach. Du bist einfach stepping zu tief für die Beantwortung der Frage hier. Du hast Recht, wenn du sagst, dass es gut ist zu wissen, wie manche Dinge funktionieren auf den meisten gängigen JVMs, aber es ist nicht von Interesse, für Fragen wie diese hier.
    • Die überwiegende Mehrheit der Menschen sind mit einer JVM die auf desktop - /server-Maschinen, bei denen die Leistung beruht auf der JVM effizient verwalten den Speicher, der in der Größenordnung von MB oder GB. Also ich denke, wir können davon ausgehen, daß die OP war nicht über ein 8 KiB-JVM.
    • Die Tatsache bleibt, dass dies hat nichts zu tun mit der Implementierung von verketteten Listen in Java. JVM-Interna waren nicht Teil der Frage.
    • OK, zugegeben, nicht viel zu tun haben mit den meisten Implementierungen und-Anwendungen. Die Frage war "ist LinkedList intern ein array-like sequence" --, auf die die Antwort ist: es könnte werden, wenn Sie waren über die Leistung besorgt. Der OP wollte eigentlich nicht angeben, eine bestimmte Umsetzung, also denke ich nicht "Nein" die richtige Antwort. Aber ich gebe zu, dass ein "Nein" ist die richtige Antwort in den meisten Fällen.

    InformationsquelleAutor Anthony Blake
Schreibe einen Kommentar