Listas Enlazadas
Listas Enlazadas
Listas Enlazadas
Enlazadas
Shantal Tavares 2018-0110
2
Historia
Muchos sistemas operativos desarrollados por la empresa
Technical Systems Consultants usaron listas enlazadas simples
como estructuras de ficheros. Un directorio de entrada apuntaba
al primer sector de un fichero y daba como resultado porciones
de la localización del fichero mediante punteros.
3
Concepto
⬡ Una lista es una estructura de datos que nos permite
agrupar elementos de una manera organizada.
4
Características
⬡ Las listas están compuestas por nodos, estos
nodos tienen un dato o valor y un puntero a
otro(s) nodo(s).
5
Nodos
Un nodo es un registro que contiene un dato de interés y al menos
un puntero para referenciar (apuntar) a otro nodo. Si la estructura
tiene sólo un puntero, la única estructura que se puede construir
con él es una lista, si el nodo tiene más de un puntero ya se
pueden construir estructuras más complejas
como árboles o grafos.
6
Como funciona
En una lista enlazada, cada elemento apunta al siguiente excepto el último
que no tiene sucesor y el valor del enlace es null. Por ello los elementos son
registros que contienen el dato a almacenar y un enlace al siguiente
elemento. Los elementos de una lista, suelen recibir también el nombre de
nodos de la lista.
7
Como funciona
⬡ 1. Representa el dato a almacenar. Puede ser
de cualquier tipo; en este ejemplo se trata de
una lista de enteros. 1.
8
Como funciona
Para que esta estructura sea un TDA lista enlazada,
debe tener unos operadores asociados que permitan la
manipulación de los datos que contiene. Los operadores
básicos de una lista enlazada son:
9
Como funciona
⬡ Eliminar: elimina un nodo de la lista, puede ser según
la posición o por el dato.
10
Tipos de listas
enlazadas
11
Tipos de listas
enlazadas
⬡ Listas simples enlazadas
Es una lista enlazada de nodos, donde cada nodo tiene un único campo de
enlace Una variable de referencia contiene una referencia al primer nodo,
cada nodo (excepto el último) enlaza con el nodo siguiente, y el enlace del
último nodo contiene NULL para indicar el final de la lista.
12
Tipos de listas
enlazadas
⬡ Listas doblemente enlazadas
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.
13
Tipos de listas
enlazadas
⬡ 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. 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.
14
Tipos de listas
enlazadas
⬡ Listas enlazadas simples circulares
16
Tipos de listas
enlazadas
⬡ Multilistas
Las multilistas permiten llegar a un registro por diferentes caminos.
El camino lo determina el campo clave sobre el cual se haga la
búsqueda. En general las multilistas son recomendables cuando la
búsqueda se hace sobre un solo atributo.
17
Aplicaciones de las listas
enlazadas
⬡ Las listas enlazadas son usadas como módulos para otras muchas
estructuras de datos, tales como pilas, colas y sus variaciones.
20
Agilización de la búsqueda
21
Agilización de la búsqueda
Otro enfoque común es indizar una lista enlazada
usando una estructura de datos externa más eficiente.
Por ejemplo, podemos construir un árbol rojo-negro
cuyos elementos están referenciados por los nodos de
las listas enlazadas. Pueden ser construidos múltiples
índices en una lista simple. La desventaja es que estos
índices puede necesitar ser actualizados cada vez que
un nodo es añadido o eliminado (o al menos, antes
que el índice sea utilizado otra vez).
22
GRACIAS POR SU ATENCION
23