2010-04-20 31 views

Respuesta

9

No utilizar ninguno de los dos. Use System.Collections.Generic.List<T>.

Esa es realmente mi recomendación. Probablemente, independientemente de cuál sea tu aplicación, pero aquí hay un poco más de color por si acaso estás haciendo algo que necesita una elección finamente ajustada aquí.

ArrayList y LinkedList son implementaciones diferentes del mecanismo de almacenamiento para List. ArrayList usa una matriz que debe cambiar de tamaño si su colección supera su tamaño de almacenamiento actual. LinkedList, por otro lado, utiliza la estructura de datos de la lista vinculada de CS 201. LinkedList es mejor para algunas cargas de trabajo pesadas de inserción frontal o posterior, pero ArrayList es mejor para cargas de trabajo de acceso aleatorio.

+0

¿Por qué recomendaría siempre utilizar una lista basada en arreglos cuando explícitamente preguntó cuándo cada (matriz v. Enlace) es mejor? –

+1

Mi punto es que generalmente no tienes que agonizar sobre la elección aquí. Hay un montón de lugares en las bibliotecas de la clase base en los que obtienes una lista independientemente de si eso es lo que deseas o no. ('* .ToList()') 'LinkedList' ni siquiera implementa' IList', por lo que no se puede utilizar automáticamente en muchos contextos de 'List'. Si necesita utilizar una 'LinkedList' por razones de rendimiento, está completamente bien, pero en promedio está perdiendo más de lo que gana. – sblom

+0

Nadie dijo que debería agonizar. Por lo general, es una decisión relativamente simple. No entiendo por qué piensas que debes usar 'List' solo porque ciertas partes de la biblioteca estándar sí lo hacen. 'LinkedList' deliberadamente no implementa' IList' para minimizar el uso indebido por parte de las personas. Incluso si fuera cierto que "en promedio estás perdiendo", el OP no preguntó sobre el promedio. Preguntó sobre * cuándo * usar cada uno. –

4

La diferencia radica en la semántica de cómo se implementa el List interfaz *:

http://en.wikipedia.org/wiki/Arraylist y http://en.wikipedia.org/wiki/LinkedList


* Significado la basic list operations

+1

Puede verificar la complejidad algorítmica de cada operación en estos artículos de wikipedia. – pgb

+0

La interfaz es 'IList ', pero 'LinkedList ' no lo implementa (probablemente deliberadamente, para desalentar los algoritmos pobres). –

+1

'List ' no es una interfaz, y ni 'ArrayList' ni' LinkedList 'implementan' IList '. – Lee

11

La diferencia es la estructura de datos interna utilizada para almacenar los objetos.

Un ArrayList usará una matriz de sistema (como Object[]) y lo redimensionará cuando sea necesario. Por otro lado, un LinkedList utilizará un objeto que contiene los datos y un puntero a los objetos siguientes y anteriores en la lista.

Diferentes operaciones tendrán diferente complejidad algorítmica debido a esta diferencia en la representación interna.

2

Tienen un rendimiento diferente en "insertos" (agregando elementos nuevos) y búsquedas. Para inserciones, ArrayLists mantiene una matriz internamente (inicialmente, 16 elementos) y cuando alcanza la capacidad máxima, duplica el tamaño de la matriz. Una LinkedList se inicia vacía y agrega un elemento (nodo) cuando sea necesario.

Creo que también con ArrayList puedes indexar los elementos, mientras que con LinkedList tienes que "visitar" el artículo desde la cabeza (o LinkedList lo hace automáticamente).

+0

LinkedList también tiene O (1) elimina, mientras que 'List ' y 'ArrayList' son O (n) en promedio (se requiere una copia a menos que la eliminación esté en la cola). –

3

La principal diferencia entre ArrayList y List<T>, LinkedList<T>, y otros similares es que los genéricos ArrayList sostiene Object s, mientras que los otros tienen un tipo que se especifica (es decir. List<Point> sostiene únicos puntos).

Debido a esto, debe convertir cualquier objeto que saque de un ArrayList en su tipo real. Esto puede tomar mucho espacio en la pantalla si tiene nombres de clase largos.

En general, es mucho mejor usar List<T> y otros genéricos tipados a menos que realmente necesite tener una lista con varios tipos diferentes de objetos en ella.

7

ArrayList tiene un buen reemplazo que es List<T>.

En general, List<T> es un contenedor de gama - Permite la indexación y artículos acceso en O (1), pero, cada vez que se excede la capacidad de un O (n) debe ser pagado.

LinkedList<T> no le permitirá acceder a elementos utilizando el índice, pero se puede contar que siempre tendrá un costo de inserción O (1). Además, puede insertar elementos al principio de la lista y entre los elementos existentes en O (1).

Creo que en la mayoría de los casos List<T> es la opción predeterminada. Muchos de los escenarios comunes no requieren un orden especial y no tienen restricciones estrictas de complejidad, por lo tanto, se prefiere List<T> debido a su simplicidad de uso.

2

Como @sblom ha declarado, use las contrapartes genéricas de LinkedList y ArrayList. Realmente no hay razón para no hacerlo, y hay muchas razones para hacerlo.

La implementación de la lista <T> está envolviendo efectivamente una matriz. Si el usuario intenta insertar elementos más allá de los límites de la matriz de soporte, se puede copiar a un conjunto más amplio (con un gasto considerable, pero sobrevalorado de forma transparente para los usuarios de la Lista <T>)

Un LinkedList <T> tiene una implementación completamente diferente en la que los datos se almacenan en LinkedListNode <T> instancias, que llevan la referencia a otras dos instancias de LinkedListNode <T> (o solo una en el caso de la cabecera o la cola de la lista). No se crea ninguna referencia externa a los elementos de la lista intermedia. Esto significa que la iteración de la lista es rápida, pero el acceso aleatorio es lento, porque uno debe iterar los nodos desde un extremo u otro. La mejor razón para usar LinkedList es permitir inserciones rápidas, que implican simplemente cambiar las referencias almacenadas por los nodos, en lugar de reescribir toda la lista para insertar un elemento (como es el caso de la lista))

Cuestiones relacionadas