listas enlazadas
TRANSCRIPT
UNIVERSDAD FERMÍN TORO VICERECTORADO ACADÉMICO
DECANATO DE INGENIERÍA ESCUELA DE COMPUTACIÓN
SEDE CABUDARE
LISTAS ENLAZADAS
Shearly Achji Estructura de Datos I
Saia
LISTAS ENLAZADAS
Estructuras de datos fundamentales, que puede ser usada para implementar otras estructuras de datos.
Son un conjunto de elementos llamados nodos en los que cada uno de ellos contiene un dato y también la dirección del siguiente nodo, donde el orden de los mismos se establece mediante punteros.
CARACTERÍSTICASLOS ELEMENTOS SE DISTRIBUYEN DE FORMA DISPERSA POR LA MEMORIA: Los bloques de información no ocupan posiciones consecutivas en la memoria. El orden de la lista la establecen los enlaces entre bloques de información.
ACCESO A LOS ELEMENTOS ALEATORIO: Puede extraerse información de cualquier elemento o insertar un bloque en cualquier posición.
ACCESO A LOS ELEMENTOS NO DESTRUCTIVO: Al contrario que en colas y pilas, la extracción de un bloque no implica su eliminación.
EL TAMAÑO DE LA LISTA PUEDE MODIFICARSE DE FORMA DINÁMICA: Al contrario que en colas y pilas, no hay un número máximo de elementos de la lista (salvo limitaciones de la capacidad de almacenamiento de la máquina).
TIPOS
LISTAS SIMPLESENLAZADAS
La lista enlazada básica es la lista enlazada simple la cual tiene un enlace por nodo.
Una lista enlazada simple contiene dos valores:
Este enlace apunta al siguiente nodo en la lista, o al valor NULL o a la lista vacía, si es el último nodo.
El valor actual del nodo.
un enlace al siguiente nodo.
LISTAS DOBLEMENTEENLAZADAS
Un tipo de lista enlazada más sofisticado es la lista doblemente enlazada o lista enlazadas de dos vías. Cada nodo tiene dos enlaces: uno apunta al nodo anterior, o apunta al valor NULL si es el primer nodo; y otro que apunta al nodo siguiente, o apunta al valor NULL si es el último nodo.
Una lista doblemente enlazada contiene tres valores:
En algún lenguaje de muy bajo nivel, XOR-Linking ofrece una vía para implementar listas doblemente enlazadas, usando una sola palabra para ambos enlaces, aunque el uso de esta técnica no se suele utilizar.
El valor.
El link al nodo siguiente.
El link al anterior.
LISTAS ENLAZADAS CIRCULARES
En una lista enlazada circular, el primer y el último nodo están unidos juntos. Esto se puede hacer tanto para listas enlazadas simples como para las doblemente enlazadas.
Una lista enlazada circular que contiene tres valores enteros
Para recorrer una lista enlazada circular podemos empezar por cualquier nodo y seguir la lista en cualquier dirección hasta que se regrese hasta el nodo original.
Desde otro punto de vista, las listas enlazadas circulares pueden ser vistas como listas sin comienzo ni fin.
Este tipo de listas es el más usado para dirigir buffers para “ingerir” datos, y para visitar todos los nodos de una lista a partir de uno dado.
LISTAS ENLAZADAS CIRCULARES SIMPLES
Cada nodo tiene un enlace, similar al de las listas enlazadas simples, excepto que el siguiente nodo del último apunta al primero. Como en una lista enlazada simple, los nuevos nodos pueden ser solo eficientemente insertados después de uno que ya tengamos referenciado.
Por esta razón, es usual quedarse con una referencia solamente al último elemento en una lista enlazada circular simple, esto nos permite rápidas inserciones al principio, y también permite accesos al primer nodo desde el puntero del último nodo.
LISTAS ENLAZADAS DOBLEMENTE CIRCULAR
En una lista enlazada doblemente circular, cada nodo tiene dos enlaces, similares a los de la lista doblemente enlazada, excepto que el enlace anterior del primer nodo apunta al último y el enlace siguiente del último nodo, apunta al primero.
Como en una lista doblemente enlazada, las inserciones y eliminaciones pueden ser hechas desde cualquier punto con acceso a algún nodo cercano.
Aunque estructuralmente una lista circular doblemente enlazada no tiene ni principio ni fin, un puntero de acceso externo puede establecer el nodo apuntado que está en la cabeza o al nodo cola, y así mantener el orden tan bien como en una lista doblemente enlazada.
VENTAJASTamaño dinámico.
Optimización de la memoria.
Con esta disposición se puede acceder a cualquier elemento de la estructura de datos en tiempo constante.
Siempre se puede llegar a cualquier nodo siguiendo los enlaces
Las búsquedas son algo mas rápidas puesto que no hace falta hacer referencia al elemento anterior.
Pueden recorrerse en ambos sentidos, ya sea para efectuar una operacion con cada elemento o para insertar/actualizar y borrar.
DESVENTAJAS
Al asignar el arreglo en tiempo de compilación debe establecerse un límite a priori sobre el número de elementos que pueden ser almacenados en las listas.
Para inserciones y eliminaciones frecuente hay que hacer corrimientos costosos.
El acceso es secuencial (para llegar a una posición deberemos pasar por todas las anteriores).
El código se complica.
UTILIDAD Las listas enlazadas son usadas como módulos para otras muchas estructuras de datos, tales como pilas, colas y sus variaciones.
A veces, las listas enlazadas son usadas para implementar arrays asociativos, y estas en el contexto de las llamadas listas asociativas.
En ocasiones una lista enlazada es dinámicamente creada fuera de un subconjunto propio de nodos semejante a un árbol, y son usadas más eficientemente para recorrer ésta serie de datos.
El campo de datos de un nodo puede ser otra lista enlazada. Mediante este mecanismo, podemos construir muchas estructuras de datos enlazadas con listas; esta práctica tiene su origen en el lenguaje de programación Lisp, donde las listas enlazadas son una estructura de datos, y ahora es una característica común en el estilo de programación funcional.
¡¡GRACIAS!!