S4_PV_2.4

2.4. Lista simplemente ligada

Para ver la información, da clic en la imagen.

Una lista simplemente ligada, o lista enlazada simple, es una estructura de datos lineal compuesta por una secuencia de nodos. Cada nodo en la lista contiene dos elementos:

• Datos: el valor o información que el nodo almacena.
• Apuntador (o Enlace): un enlace al siguiente nodo en la lista.

A diferencia de los arrays o vectores, los elementos en una lista simplemente ligada no están almacenados en posiciones contiguas en la memoria. En cambio, cada nodo apunta al siguiente, formando una cadena de nodos conectados. La lista comienza con un nodo cabeza (head), que es el punto de entrada a la lista. El último nodo de la lista apunta a NULL, indicando el final de la lista.

Unidad 2. Estructuras de datos

2.4.1 Operaciones y aplicaciones

2.4. Lista simplemente ligada

Para ver la información, da clic en las imágenes.

Unidad 2. Estructuras de datos

Aplicaciones

• Implementación de pilas y colas: pueden usarse para implementar otras estructuras de datos como pilas y colas de manera eficiente.
• Gestión de memoria en sistemas operativos: utilizadas para gestionar la memoria disponible o procesos en ejecución.
• Manejo de listas de espera y colas de tareas: ideal para aplicaciones que requieren mantener un conjunto de tareas o procesos a ejecutar en secuencia.
• Aplicaciones de reproductor de música: para gestionar listas de reproducción, donde las canciones pueden ser añadidas, eliminadas o reordenadas.
• Gestión de documentos en editores de texto: para mantener un historial de cambios o implementar funcionalidades de deshacer/rehacer.
• Implementación de gráficos y juegos: en el desarrollo de videojuegos y gráficos, las listas simplemente ligadas pueden ser utilizadas para gestionar diversos elementos dinámicos.
• Aplicaciones en redes: para mantener listas de conexiones, rutas o paquetes en aplicaciones de red.

Características

• Dinámica: su tamaño puede variar durante la ejecución del programa.
• Eficiencia en inserciones/eliminaciones: pueden insertar o eliminar nodos de manera eficiente, sin necesidad de reorganizar toda la estructura.
• Uso de memoria: utilizan memoria de manera más eficiente que los arrays en situaciones donde el tamaño de la lista varía frecuentemente.
• Secuencial: el acceso a los elementos es secuencial, comenzando desde el nodo cabeza y siguiendo los enlaces hasta llegar al nodo deseado.

Operaciones 1. Inserción: añadir un nuevo nodo en la lista.

• Al inicio: insertar un nodo al principio de la lista, que se convierte en la nueva cabeza.
• Al final: añadir un nodo al final de la lista.
• En medio: insertar un nodo entre dos nodos existentes.

2. Eliminación: quitar un nodo de la lista.

• Eliminar por valor: buscar y eliminar un nodo basado en su valor.
• Eliminar por posición: eliminar un nodo en una posición específica.

3. Búsqueda: encontrar un nodo por su valor o posición.

• Buscar por valor: recorrer la lista hasta encontrar el nodo con el valor especificado.
• Buscar por posición: recorrer la lista hasta llegar a la posición deseada.

4. Travesía o Recorrido: pasar por cada nodo de la lista para realizar alguna operación, como mostrar sus valores. 5. Actualización: cambiar el valor de un nodo existente. 6. Inversión: invertir el orden de los nodos en la lista.