Listas simplemente enlazadas

Comienza Ya. Es Gratis
ó regístrate con tu dirección de correo electrónico
Listas simplemente enlazadas por Mind Map: Listas simplemente enlazadas

1. Operaciones básicas

1.1. Inserción

1.1.1. La inserción es una operación medianamente sencilla, ya que se puede entender como un ajuste de punteros que permite guardar información en la posición deseada del usuario, creando métodos respectivos para llevar dicha tarea

1.1.1.1. Inicio

1.1.1.1.1. El elemento se crea con su dato y un puntero apuntando al primer nodo de la lista, después automáticamente el inicio de la lista apunta a ese nuevo nodo, indicando así el nuevo inicio de la fila

1.1.1.2. Medio

1.1.1.2.1. Para ingresar un elemento al medio de 2 nodos, se hace un recorrido de la lista hasta la posición indicada del usuario, luego se crea el elemento con sus datos pero con un ajuste en sus punteros, donde el nuevo nodo apunta al nodo que estaba en esa posición, y el anterior al mismo apunta al que se creó

1.1.1.3. Final

1.1.1.3.1. Similar al caso de la inserción en medio, la inserción al final hace un recorrido hasta detectar el final de la lista, se crea el nodo con sus datos respectivos, el ultimo nodo actual de la lista se enlaza al nuevo, y por último este nuevo se enlaza al final, indicando así que este es el nuevo final de la lista

1.2. Eliminación

1.2.1. Esta operación es similar a la inserción, sin embargo, esta generaliza la posición del nodo que se está buscando

1.2.1.1. En este proceso se crean 2 punteros para llevar a cabo la búsqueda y eliminación correcta del nodo sin afectar los datos o punteros de los demás, además de también recibir el valor o dato que el usuario está buscando eliminar. Los 2 punteros se llamarían actual y anterior, siendo "actual" el nodo que se evalúa en la búsqueda y recorrido de la fila, y "anterior" sería un espacio donde guarda el nodo anteriormente evaluado para así no perder el orden y reajustar los punteros correctamente. La busqueda se lleva a cabo con un bucle que hace el recorrido el cual termina si la fila termina o encuentra el dato, luego se evalúa si el nodo donde terminó el recorrido es el dato solicitado o no. Si el dato encontrado es el solicitado, se procede a hacer un reajuste de punteros dependiendo de si el nodo se encuentra en el inicio, medio o final. Una vez ajustados los punteros, se elimina el nodo solicitado.

1.2.1.1.1. Ejemplo: Antes de eliminar 5 Inicio → [ 3 | P ] → [ 5 | P ] → [ 10 | P ] → Final Despues de eliminar 5 Inicio → [ 3 | P ] → [ 10 | P ] → Final

1.3. Recorrido

1.3.1. Como se puede evidenciar en los casos de inserción y eliminación, el recorrido en este tipo de lista se refiere a pasar por cada nodo existente de la lista, hasta llegar e un punto deseado o directamente al final, esto es útil cuando se quiere imprimir los datos de la lista, contar cuantos datos hay, o aplicar una misma operación a cada nodo de toda la lista

1.3.1.1. Ejemplo: Impresión de datos Lista: Inicio → [ 3 | P ] → [ 5 | P ] → [ 8 | P ] → Final Impresión: 3 5 8

1.4. Búsqueda

1.4.1. Similar al recorrido, la búsqueda es un tipo de operación que recorre toda la lista hasta encontrar el nodo con el valor solicitado por el usuario, ya sea para imprimirlo, cambiarlo o directamente eliminarlo

1.4.1.1. Ejemplo: Retorno de true/false Lista: Inicio → [ 3 | P ] → [ 5 | P ] → [ 8 | P ] → Final Retorno: Si el número solicitado es encontrado, se retorna true, sino, se retorna false

2. Qué es?

2.1. Es un tipo de estructura de datos flexible y dinámica, conformada por un elemento llamado nodos, que contienen un dato y un puntero al siguiente de estos, formando una secuencia lineal de datos.

2.1.1. Caracteristicas

2.1.1.1. *Cada nodo apunta al siguiente *Las listas de tipo simplemente enlazadas solo se recorren en una dirección (de inicio a final) *Son dinamicas (no tienen tamaño fijo) *En la codificacion, el inicio se representa como head y el final como NULL

3. Importancia

3.1. Son creadas para la correcta, eficiente y organizada gestión de datos dinámicos de un programa

4. Ventajas con respecto a los arreglos

4.1. Tamaño

4.1.1. No necesita un tamaño fijo a comparación de los arreglos

4.2. Insercion/eliminacion

4.2.1. El usuario o programa puede manipular las posiciónes con rapidez, sin necesidad de desplazar grandes cantidades de datos

4.3. Estructura

4.3.1. Se pueden crear varias listas con distintos nodos, o conectar los nodos a otras estructuras

4.4. Uso de memoria

4.4.1. El uso de memoria dinámica abre la posibilidad de crear una cantidad de datos ilimitada sin preocuparse del espacio reservado en memoria, ya que el espacio en memoria solo se utiliza cuando se crea o borra el nodo

5. Estructura

5.1. La estructura de las listas enlazadas se ve de la siguiente forma: Inicio → [10 | P] → [20 | P] → [30 | P] → Final. Donde: *[dato | P] representa un nodo. * *dato es la informacion que contiene el nodo * *P es el puntero que apunta al siguiente nodo. *

5.1.1. El funcionamiento de las listas y en general los nodos, sigue el algoritmo LIFO (Last Input - First Output), donde el ultimo dato ingresado, es el primero en mostrarse o salir. Este se usa para las pilas. Siguiendo el ejemplo de la estructura, el orden de ingreso de los datos es 30, 20 y 10, pero bajo el algoritmo LIFO, este saldría en su inverso, o sea, 10, 20 y 30. También puede usar el algoritmo FIFO (First Input, First output) en el caso de las colas, donde el primer ingresado es el primero en mostrarse o salir

6. Aplicaciónes - Ejemplos

6.1. Implementación de Pilas y Colas

6.1.1. Se pueden crear programas que dependiendo del caso o la acción que se realice, se tenga una pila donde el ultimo dato ingresado sea el primero en salir. O se puede crear una cola donde el primero ingresado es el primero que sale. La pila se evidencia más en un navegador web donde la ultima página ingresada es la primera de la lista. La cola se evidencia en el sistema de una impresora cuando se solicitan varios documentos, donde el primer documento será el primero en imprimirse

6.2. Gestion de memoria y almacenamiento dinámico

6.2.1. Se tiene un manejo más preciso sobre grandes cantidades de datos, donde la cantidad de estos no tiene límite y se puede manejar a la necesidad del usuario Ejemplo: Una playlist musical, estas no tienen un límite definido y tienen X cantidad de canciones agregadas dependiendo del usuario, las cuales el mismo puede quitar o agregar más

6.3. Manejo de datos en sistemas empresariales

6.3.1. Las empresas según la necesidad gestionan inventarios de distintos objetos, con una cantidad indefinida de los mismos Ejemplo: Un supermercado con un inventario de los artículos que venden, donde si uno de estos se agota, se elimina de la lista.

6.4. Deshacer y rehacer en aplicaciones

6.4.1. Muchos programas utilizan listas para mantener un registro de los cambios que se haga en un documento o archivo, haciendo uso de los recorridos para volver a un estado sin desperdiciar memoria en cambios innecesarios Ejemplo: Las apps de Microsoft Office guardan los cambios hechos en un documento para volver atrás las veces deseadas o rehacer las acciones igualmente las veces deseadas