Listas Enlazadas

Descargar como pdf o txt
Descargar como pdf o txt
Está en la página 1de 23

Listas

Enlazadas
 Shantal Tavares 2018-0110

 Adam Mejia 2018-0273

 Felix Mena 2018-0744


Historia
Las listas enlazadas fueron desarrolladas en 1955-56
por Cliff Shaw y Herbert Simón en RAND Corporación,
como la principal estructura de datos para su Lenguaje
de Procesamiento de la información (IPL). IPL fue usado
por los autores para desarrollar varios programas
relacionados con la inteligencia artificial, incluida la
Máquina de la Teoría General, el Solucionador de
Problemas Generales, y un programa informático de
ajedrez.

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.

⬡ La lista enlazada es un TDA que nos permite


almacenar datos de una forma organizada, al igual
que los vectores pero, a diferencia de estos, esta
estructura es dinámica, por lo que no tenemos que
saber "a priori" los elementos que puede contener.

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).

⬡ Las listas enlazadas pueden ser implementadas


en muchos lenguajes. Lenguajes tales como
Lisp, Scheme y Haskell tienen estructuras de
datos ya construidas, junto con operaciones
para acceder a las listas enlazadas.

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.

⬡ 2. Es un puntero al siguiente elemento de la 2.


lista; con este puntero enlazamos con el
sucesor, de forma que podamos construir la
lista.

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:

⬡ Insertar: inserta un nodo con dato x en la lista,


pudiendo realizarse esta inserción al principio o final
de la lista o bien en orden.

9
Como funciona
⬡ Eliminar: elimina un nodo de la lista, puede ser según
la posición o por el dato.

⬡ Buscar: busca un elemento en la lista.

⬡ Localizar: obtiene la posición del nodo en la lista.

⬡ Vaciar: borra todos los elementos de la lista

10
Tipos de listas
enlazadas

⬡ Listas simples enlazadas


⬡ Listas doblemente enlazadas
⬡ Listas enlazadas circulares
⬡ Listas enlazadas simples circulares
⬡ Listas enlazadas doblemente circulares
⬡ Multilistas

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

 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.
15
Tipos de listas
enlazadas
⬡ Listas enlazadas doblemente
circulares
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.

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.

⬡ 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 practica tiene su origen en el lenguaje de
programación Lisp, (es una familia de lenguajes de programación de
computadora de tipo multiparadigma y con sintaxis basada en la
notación polaca). donde las listas enlazadas son una estructura de
datos primaria y ahora es una característica común en el estilo de
programación funcional. 18
Aplicaciones de las listas
enlazadas
⬡ A veces, las listas enlazadas son usadas para
implementar vectores asociativos, y estas en el
contexto de las llamadas listas asociativas. Hay
pocas ventajas en este uso de las listas enlazadas;
hay mejores formas de implementar éstas
estructuras, por ejemplo con árboles binarios de
búsqueda equilibrados. Sin embargo, a veces 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.
19
Agilización de la búsqueda
Buscando un elemento específico en una
lista enlazada, incluso si esta es ordenada,
normalmente requieren tiempo . Esta es
una de las principales desventajas de
listas enlazadas respecto a otras
estructuras. Hay numerosas vías simples
para mejorar el tiempo de búsqueda.

20
Agilización de la búsqueda

En una lista desordenada, una forma simple para decrementar el


tiempo de búsqueda medio es el mover al frente de forma
heurística, que simplemente mueve un elemento al principio de la
lista una vez que es encontrado. Esta idea, útil para crear cachés
simples, asegura que el ítem usado más recientemente es también
el más rápido en ser encontrado otra vez.

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

También podría gustarte