Las listas vinculadas son excelentes cuando necesita insertar un elemento o eliminar un elemento del medio de una colección ordenada en tiempo constante. Una matriz / vector requeriría que “desplazaras” cada elemento después del elemento que eliminaste una posición, lo que sería lento y horrible si la colección fuera grande. Por el contrario, eliminar un elemento de una lista vinculada solo implica reescribir algunos punteros, lo que es prácticamente instantáneo.
Un ejemplo podría ser una aplicación que lee múltiples registros ordenados de un archivo o base de datos y luego los muestra al usuario en una lista editable. El usuario desliza un elemento para eliminarlo; La estructura de datos subyacente en la memoria es una lista vinculada, y el nodo que representa el elemento se elimina de ella.
Incluso si hubiera un millón de entradas, el elemento se eliminaría al instante. Pero, si los millones de elementos se mantuvieron en una matriz / vector, por otro lado, la aplicación podría parecer que se bloquea por un momento ya que todos los elementos después del que el usuario eliminó se copiaron hacia arriba para llenar el vacío.
- ¿Cuándo debo usar un árbol de sufijos sobre una matriz de sufijos?
- ¿Cuál es el algoritmo más difícil que has implementado? ¿Por qué fue difícil? ¿Cuánto tiempo te llevó?
- ¿Cuál es la forma más eficiente de implementar la unión en varias tablas (> 5 tablas) usando SQL / ANSI SQL?
- ¿Cuál es la diferencia entre los algoritmos de programación de tareas y los algoritmos de equilibrio de carga (estáticos y dinámicos)?
- Si llamo k veces getSuccessor () de un nodo con altura h en una búsqueda de árbol binario. ¿Cómo pruebo que el tiempo de ejecución tomará solo O (k + h)?
También se pueden unir dos listas vinculadas, de nuevo, casi al instante. Esto es mucho más rápido que copiar elementos uno por uno de una colección a otra.
Al igual que hay ventajas, también hay desventajas. Las listas vinculadas generan una sobrecarga de memoria alta. Volviendo al ejemplo que di, esos millones de elementos en la lista consumirían mucha más memoria que si estuvieran almacenados consecutivamente, o incluso si estuvieran almacenados como una matriz de punteros a objetos.
Si hubiéramos usado una lista doblemente vinculada, eso habría significado 2 o 3 punteros para cada elemento (anterior, siguiente y opcionalmente el objeto al que hace referencia el nodo), que en un sistema de 64 bits consumiría 16-24 bytes adicionales. por elemento en comparación con una secuencia de objetos almacenada de forma contigua (no en una lista vinculada). Para un millón de entradas, eso es 16 a 24 millones de bytes adicionales que necesitaría nuestro programa.
Una implementación simple de una lista vinculada también podría ralentizar nuestra aplicación porque habría tantos objetos asignados en el montón, incluidos los nodos dentro de la propia lista vinculada.
Finalmente, las listas vinculadas no son excelentes cuando se trata de buscar cosas dentro de la lista. Tienes que hacer un escaneo de fuerza bruta a través de cada elemento de la lista para encontrar lo que buscas.
