Hasta donde yo sé, el concepto de una lista vinculada es un grupo de objetos conectados entre sí al tener un atributo 'siguiente' ya veces 'anterior' para atravesar los objetos.¿Cómo funciona LinkedList internamente en Java?
Noté en Java, puede crear un objeto LinkedList ... pero tratarlo como una matriz/lista/secuencia usando los mismos métodos como .add(), .get(), etc.
Entonces, ¿LinkedList es internamente una secuencia tipo array?
Entonces, ¿LinkedList es internamente una secuencia tipo array?
No. Es una serie de instancias de una clase anidada privada Entry, que tiene next, previous y element referencias. Tenga en cuenta que podría haberlo descubierto mirando el código fuente, que viene con el JDK.
La razón por la cual esta estructura interna no está expuesta es porque impide que la estructura se corrompa y p. Ej. que contiene un bucle Y el acceso uniforme a través de las interfaces List y Deque permite el uso polimórfico.
+1: La lista que es internamente una secuencia tipo array se llama ArrayList. ;) –
-1: Depende de tu habilidad de programación, supongo. Del artículo de wikipedia en Linked Lists: "También puede ser lento, y con un asignador ingenuo, inútil, asignar memoria por separado para cada elemento nuevo, un problema generalmente resuelto usando pools de memoria". - Para tu información, las agrupaciones de memoria son las matrices que los profesionales usan para almacenar internamente listas vinculadas. También se conocen como asignadores de losas. –
@Anthony: venganza downvote, ¿eh? Superalo. Los profesionales expertos no se meten en Internet: critican el nivel al que se debe responder una pregunta. –
Es posible implementar un objeto que funciona como una matriz, utilizando una lista vinculada. En comparación con las matrices, algunas operaciones serán más rápidas y otras más lentas. Por ejemplo, llamar a get() para un elemento cerca del final puede ser bastante más lento con una lista vinculada que con una matriz. Pero, aún es posible.
Por otro lado, eliminar un elemento del medio de una lista vinculada será más rápido que la operación correspondiente realizada mediante matrices.
LinkedList es una cadena de entidades en la que cada entidad conoce la siguiente, , por lo que la operación get (index) requiere iterar sobre esta cadena con el contador. Pero esta lista optimizada para agregar y eliminar por posición (en caso de que necesite poner el elemento dentro de la lista o eliminar elemento de la lista de enlaces medios funciona mejor)
Realmente no. La colección proporciona una lista enlazada y, mediante un buen diseño, puede crear una lista de doble enlace. Ahora no es como una matriz porque estos objetos no tendrán índices y no son elementos dentro del contenedor, es decir, la lista. Por lo tanto, debes definir el siguiente y el anterior y dictar cuál es el próximo movimiento. Todos tienen los mismos métodos porque nuevamente son colecciones como dije.
Internamente utilizará lo que se denomina 'asignador de placa' - básicamente es una lista vinculada de arreglos pequeños. Cada vez que agrega un objeto, verifica si hay espacio en la losa y, de ser así, coloca el objeto allí. De lo contrario, asigna una nueva losa y coloca el objeto en el primer elemento de la losa.
Esta técnica minimiza los gastos generales de asignación de memoria - si se agrega una gran cantidad de elementos a una lista enlazada, que habría una gran cantidad de pequeñas asignaciones de memoria que tienen una gran cantidad de tiempo, y los asignadores de losa minimizar ese
Esto es simplemente incorrecto. Java no es C++. Las pequeñas asignaciones son rápidas. En consecuencia, la implementación de API no utiliza ningún truco para evitarlo. –
@MichaelBorgwardt ¿Dónde crees que la JVM obtiene la memoria para cada objeto que asigna? ¿Crees que la JVM está llamando malloc() todo el tiempo? Los recolectores de basura trabajan con la memoria en las losas. Explique cómo cree que Java está asignando memoria para listas vinculadas sin losas de memoria. –
@MichaelBorgwardt De la documentación sobre JVM de IBM: "Estas secciones se implementan típicamente como losas contiguas de memoria nativa que están bajo el control del administrador de memoria de Java (que incluye el recolector de basura)". –
como sé Linkedlist es como lo que dijiste en el primer párrafo. cada objeto tiene dos referencias, llamado anterior y siguiente. a diferencia de la matriz que funciona de forma secuencial (en C se almacena exactamente en secuencia. Creo que Java hace lo mismo, es por eso que no podemos cambiar el tamaño de una matriz), la lista funciona haciendo referencia. así que lógicamente funciona más lento que array.
Una LinkedList en Java funciona tal como cabría esperar. Si usa las colecciones oficiales LinkedList, entonces será un un montón de objetos conectados entre sí al tener un 'siguiente' y algunas veces 'anterior'.
Y sí, tiene un método get(int index) lo cual es sorprendente, ya que no sería muy eficiente ya que tendría que empezar por el principio y contar su camino hasta la lista para encontrar el ª entrada index y esto no lo LinkedLists es son buenos en. La razón por la que está allí es porque LinkedList implementa la interfaz List. Esto es algo que puedes hacer con TODAS las listas.
Sin embargo, probablemente intente evitar el uso de LinkedList cuando la mayoría de su acceso se realice a través del método get(int index), ya que es claramente ineficaz. Quizás sería mejor utilizar un ArrayList.
Si desea ver la implementación, busque el código fuente de 'java.util.LinkedList' que puede encontrar en el archivo' src.zip' en su directorio de instalación JDK. – Jesper
O consulte la fuente: http://www.docjar.com/html/api/java/util/LinkedList.java.html –
Puede que le interese mi [Vida interna de LinkedList en java] (http: // volodial.blogspot.com/2013/05/internal-life-of-linkedlist-in-java.html) tutorial. –