Diferencia entre la lista <T> y LinkedList <T>

Question

Utilizamos la lista cada vez que necesitamos una lista. Ahora me doy cuenta de que hay una LinkedList.

Me preguntaba cuál era la diferencia entre estos 2, y cuándo debería usar uno sobre el otro.

Answer 1

Bueno, List<T> está básicamente respaldado por una matriz que generalmente es más grande que la cantidad actual de elementos. Los elementos se colocan en una matriz y se crea una nueva matriz cuando el anterior se queda sin espacio. Esto es rápido para el acceso por índice, pero lento para eliminar o insertar elementos dentro de la lista o al comienzo. Agregar/eliminar entradas al final de la lista es razonablemente barato.

LinkedList<T> es una lista doblemente vinculada: cada nodo conoce su entrada anterior y la siguiente. Esto es rápido para insertar después/antes de un nodo en particular (o la cabeza/cola), pero lento en el acceso por índice.

LinkedList<T>se suele tener más memoria que List<T> porque necesita espacio para todos aquellos próximos referencias anteriores/- y los datos probablemente tendrá menos localidad de referencia, ya que cada nodo es un objeto independiente. Por otro lado, un List<T>puede tener una matriz de respaldo que es mucho más grande que sus necesidades actuales.

Answer 2

A List<T> es en realidad una matriz, lo que significa que su operación Add es O (1) al final y O (n) en la parte delantera, pero puede indexarla en O (1). A LinkedList<T> es, como se dice, una lista vinculada. Dado que está doblemente vinculado, puede agregar elementos al frente o atrás en O (1) pero su indexación es O (n).