4

Tengo problemas para diferenciar cuándo usar uno u otro.. Por ejemplo en una agenda en la que añades contactos y los borras creo que seria LinkedList.

Me gustaria una respuesta para entender facilmente cuándo usar una u otra. Un link a una fuente que lo explique bien tambien me valdría.

  1. Se desea organizar una agenda con los datos de los clientes de una empresa (nombre que se supondrá que contiene los apellidos y nombre en este orden y teléfono). Como la empresa es muy desordenada, todas las tarjetas de visitas están en un tarjetero colocadas unas encima de otras. Se desea vaciar este tarjetero y colocar todas las tarjetas en una agenda de forma que estén juntas todas aquellas cuyo apellido empieza por la misma letra (por ejemplo, todas las que empiecen por A estarán en la primera página, todas las que empiecen por B en la segunda, etc.)

    Se pide:

    Establecer qué tipo de estructura de datos se usaría para representar la información necesaria: tarjeta, tarjetero, agenda y páginas de la agenda.

    Escribir un programa Java que implemente las estructuras descritas y realice las siguientes operaciones:

    • Crear el tarjetero: se introducirán varias tarjetas desordenadas en el tarjetero (procurad que haya varias tarjetas con la misma inicial en el nombre para que se guarden en la misma página)

    • Crear la agenda: se extraerán todas las tarjetas del tarjetero y se guardarán en la agenda en la página que le corresponda según la inicial del nombre.

    • Ver la agenda: listará todas sus- páginas, usando la interfaz Iterable que deben implementar Agenda y Página

    • Ordenar cada página de la agenda por el nombre, mediante la interfaz ((Comparable)) que debe implementar Tarjeta. Se deberá mostrar de nuevo la agenda ordenada.**

En ese ejercicio quise usar un arrayList para las tarjetas de la pagina pero se me recomendo que en este caso usara Linkedlist.

4

1 respuesta 1

7

Resumen ArrayList es lo que quieres LinkedList casi siempre es un error (de rendimiento).


LinkedList y ArrayList son dos implementaciones diferentes de la interfaz de la Lista. LinkedList lo implementa con una lista doblemente vinculada. ArrayList lo implementa con una matriz de redimensionamiento dinámico.

Al igual que con la lista enlazada estándar y las operaciones de matriz, los diversos métodos tendrán diferentes tiempos de ejecución algorítmicos.

  • LinkedList permite inserciones o eliminaciones de tiempo constante utilizando iteradores , pero solo acceso secuencial de elementos. En otras palabras, puede recorrer la lista hacia adelante o hacia atrás, pero encontrar un puesto en la lista lleva tiempo proporcional al tamaño de la lista. Javadoc dice que "las operaciones que indexan en la lista atravesarán la lista desde el principio o el final, lo que esté más cerca" , por lo que esos métodos son O (n) ( n/4 pasos) en promedio, aunque O (1) para index = 0.

  • ArrayList por otro lado, permite un acceso de lectura aleatorio rápido, para que puedas agarrar cualquier elemento en tiempo constante. Pero agregar o eliminar desde cualquier lugar menos el final requiere desplazar todos los últimos elementos, ya sea para abrir o llenar el espacio. Además, si agrega más elementos que la capacidad de la matriz subyacente, se asigna una nueva matriz (1.5 veces el tamaño), y la matriz anterior se copia a la nueva, por lo que agregar a un ArrayList es O (n) en el peor caso pero constante en promedio.

Entonces, dependiendo de las operaciones que pretenda hacer, debe elegir las implementaciones en consecuencia. Iterar sobre cualquiera de los tipos de listas es prácticamente igual de barato. (La iteración sobre un ArrayList es técnicamente más rápida, pero a menos que esté haciendo algo realmente sensible al rendimiento, no debe preocuparse por esto; ambas son constantes).

Los principales beneficios de usar a LinkedList surgen cuando reutiliza iteradores existentes para insertar y eliminar elementos. Estas operaciones se pueden realizar en O (1) cambiando solo la lista localmente. En una lista de matriz, el resto de la matriz debe moverse (es decir, copiarse). Por otro lado, buscar en un LinkedList medio siguiendo los enlaces en O (n) ( n/2 pasos) para el peor de los casos, mientras que en un `ArrayList posición deseada se puede calcular matemáticamente y acceder en O (1) .

Otro beneficio de usar a LinkedList surge cuando se agrega o quita del encabezado de la lista, ya que esas operaciones son O (1) , mientras que son O (n) para ArrayList. Tenga en cuenta que ArrayDeque puede ser una buena alternativa LinkedList para agregar y quitar de la cabeza, pero no es una List.

Además, si tiene listas grandes, tenga en cuenta que el uso de la memoria también es diferente. Cada elemento de a LinkedList tiene más sobrecarga, ya que los punteros a los elementos siguiente y anterior también se almacenan. ArrayLists no tengas esta sobrecarga. Sin embargo, ArrayLists tome tanta memoria asignada para la capacidad, independientemente de si los elementos se han agregado realmente.

La capacidad inicial predeterminada de un ArrayList es bastante pequeña (10 desde Java 1.4 - 1.8). Pero dado que la implementación subyacente es una matriz, la matriz debe redimensionarse si agrega muchos elementos. Para evitar el alto costo de cambiar el tamaño cuando sabe que va a agregar muchos elementos, construya `ArrayList con una capacidad inicial más alta.

Para mas información, Fuente SO: When to use LinkedList over ArrayList?


Otras fuentes interesantes (Traducir del ingles):

4
  • En definitiva si hay inserciones y borrados constantemente es mejor LinkedList y en los demas casos ArrayList ¿¿es correcto?? el 13 jun. 2018 a las 19:21
  • @DavidPalanco hay muy pocas razones para utilizar LinkedList de Java. Además del mal funcionamiento, también usa mucha más memoria que las otras clases concretas de la Lista (cada nodo tiene dos punteros adicionales y cada nodo es un objeto envoltorio separado con los bytes adicionales de sobrecarga que van con ellos) el 13 jun. 2018 a las 19:28
  • 1
    @DavidPalanco Si tiene que realizar muchas inserciones y búsquedas no tan frecuentes, use a LinkedList. Y use ArrayList si realiza más búsquedas que inserciones. Casi no hay un solo caso en el que ArrayList o ArrayDeque sean peores en cuanto a rendimiento. el 13 jun. 2018 a las 19:35
  • 1
    @DavidPalanco y respondiendo a esto si hay inserciones y borrados constantemente es mejor LinkedList Cuál de los dos es más rápido para insertar y eliminar? depende de dónde ocurre. Si estamos más cerca del comienzo, LinkedList será más rápido, porque tenemos que pasar por relativamente pocos elementos. Si estamos más cerca del final, ArrayList será más rápido, porque llegamos allí en un tiempo constante y solo tenemos que cambiar los pocos elementos restantes que lo siguen. el 13 jun. 2018 a las 19:43

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.