Aplicaciones de la estructura de datos de lista enlazada

Una lista enlazada es una estructura de datos lineal, en la que los elementos no se almacenan en ubicaciones de memoria contiguas. Los elementos de una lista enlazada se enlazan mediante punteros como se muestra en la siguiente imagen: Aplicaciones de la lista enlazada en informática :

1. Implementación de pilas y colas
2. Implementación de gráficos: la representación de gráficos de listas de adyacencia es la más popular, que utiliza una lista vinculada para almacenar vértices adyacentes.
3. Asignación de memoria dinámica: utilizamos una lista enlazada de bloques libres.
4. Mantenimiento del directorio de nombres.
5. Realización de operaciones aritméticas con números enteros largos
6. Manipulación de polinomios almacenando constantes en el Node de la lista enlazada
7. representando arrays dispersas

Aplicaciones de la lista enlazada en el mundo real-

1. Visor de imágenes: las imágenes anterior y siguiente están vinculadas, por lo que se puede acceder a ellas mediante el botón siguiente y anterior.
2. Página anterior y siguiente en el navegador web : podemos acceder a la URL anterior y siguiente buscada en el navegador web presionando el botón Atrás y Siguiente, ya que están vinculados como una lista vinculada.
3. Reproductor de música : las canciones en el reproductor de música están vinculadas a la canción anterior y siguiente. puede reproducir canciones desde el principio o el final de la lista.

Aplicaciones de las listas enlazadas circulares:

1. Útil para la implementación de la cola. A diferencia de esta implementación, no necesitamos mantener dos punteros para adelante y atrás si usamos una lista enlazada circular. Podemos mantener un puntero al último Node insertado y el frente siempre se puede obtener como penúltimo.
2. Las listas circulares son útiles en aplicaciones para recorrer repetidamente la lista. Por ejemplo, cuando se ejecutan múltiples aplicaciones en una PC, es común que el sistema operativo coloque las aplicaciones en ejecución en una lista y luego las recorra, dándoles a cada una una porción de tiempo para ejecutarse y luego haciéndolas esperar. mientras que la CPU se le da a otra aplicación. Es conveniente que el sistema operativo use una lista circular para que cuando llegue al final de la lista pueda pasar al principio de la lista.
3. Las listas circulares doblemente enlazadas se utilizan para la implementación de estructuras de datos avanzadas como Fibonacci Heap .

Aplicación de Listas Doblemente Vinculadas:

• Funcionalidad de rehacer y deshacer.
• Uso del botón Atrás y Adelante en un navegador.
• La sección utilizada más recientemente está representada por la lista de enlaces dobles.
• Otras estructuras de datos como Stack, HashTable, BinaryTree también se pueden aplicar mediante la lista doblemente enlazada.

Un problema de ejemplo: diseñe una estructura de datos que admita las siguientes operaciones de manera eficiente.

1. getMin : Obtiene el mínimo
2. extractMin : elimina el mínimo
3. getMax : Obtiene el máximo
4. extractMax: elimina el máximo
5. insertar: inserta un elemento. Se puede suponer que el elemento insertado siempre es mayor que el máximo hasta el momento. Por ejemplo, un pedido de inserción válido es 10, 12, 13, 20, 50.

La lista doblemente enlazada es la mejor solución aquí. Mantenemos los punteros de cabeza y cola, dado que el elemento insertado siempre es el mayor, lo insertamos en la cola. La eliminación de un elemento de la cabeza o la cola se puede hacer en tiempo O (1). Entonces todas las operaciones toman tiempo O(1). 

Artículos recientes en la lista enlazada