043_-_diapos_lista

Vista previa del material en texto

Listas
75.41 - Algoritmos y Programación II
1° Cuatrimestre 2022
1
● Agrupa elementos
¿Qué es una lista?
Primero
2
● Cada uno tiene:
○ Sucesor (menos el último)
○ Predecesor (menos el primero)
5 8 6 2
Operaciones
3
● Crear (create)
● Insertar (insertAt)
● Vacía (isEmpty)
● Destruir (destroy)
● Eliminar (deleteAt)
● Ver elemento (find)
Operaciones
4
● Vector estático
● Vector dinámico
● Lista de nodos
Implementaciones
5
Tipos de Listas
● Simplemente enlazada
● Doblemente enlazada
● Circular
6
7
Lista Simplemente 
Enlazada
Simplemente enlazada
● Implementación con nodos
● Cada uno con referencia al nodo siguiente
● Lista mantiene referencia al primer nodo
¿Cuándo reservo / libero memoria?
● Reservo memoria para cada nodo 
● Libero memoria para cada nodo 
Ventaja:
● Memoria no debe ser contigua 8
NULL4
LISTA: NULL
9
Referencia a nodo_primero 
es NULL
Inserto un elementoLISTA:
Referencia al 
nodo siguiente
Lista de nodos simplemente enlazada
LISTA:
NULL106
10
4
Inserto elementos al final
Lista de nodos simplemente enlazada
(inserto el 10)
NULL106
LISTA:
11
4
Inserto un elemento en posición i
Lista de nodos simplemente enlazada
NULL22
¡Perdí la referencia a los otros nodos!
NULL106
LISTA:
12
4
Inserto un elemento
Lista de nodos simplemente enlazada
22 1.
2.
(Los números en rojo son el orden de asignación de los punteros)
NULL106
LISTA:
13
4
Elimino un elemento
Lista de nodos simplemente enlazada
¡Perdí la referencia a los otros nodos!
NULL106
LISTA:
14
4
22
¡Perdí la referencia al nodo a eliminar!
Elimino un elemento
Lista de nodos simplemente enlazada
NULL106
LISTA:
15
4
Eliminar un elemento
Solución: variable auxiliar
22
AUXILIAR
1.
2.
3.
1. Apuntamos con el auxiliar
2. Redireccionamos el nodo anterior
3. Borramos el nodo
16
Lista Doblemente 
Enlazada
NULL106
LISTA:
17
4
Lista de nodos doblemente enlazada
Referencia al sucesor y predecesor
NULL
NULL106
LISTA:
18
4
Inserto elemento
Cuidado al insertar...
NULL
22
¡No puedo recorrer la lista!
NULL106
LISTA:
19
4
Inserto elemento
Cuidado al insertar...
NULL
22
1. Apuntamos con el nuevo nodo al anterior y al siguiente [flechas azules]
2. El nodo siguiente (6) apunta al nuevo nodo (22) [flecha naranja]
3. El nodo anterior (4) apunta al nuevo nodo (22) [flecha violeta]
22
NULL106
LISTA:
20
4
¡Y más cuidado al borrar!
NULL
AUXILIAR
1. Usamos un puntero auxiliar llamado nodo_a_borrar, y apuntamos al nodo a borrar
2. El nodo anterior de nodo_a_borrar (4) apuntará al nodo siguiente de nodo_a_borrar (6) [flecha azul]
3. El nodo siguiente de nodo_a_borrar (6) apuntará al nodo anterior de nodo_a_borrar (4) [flecha violeta]
4. Borramos nodo_a_borrar
21
Lista Circular
22
Lista circular
106
LISTA:
4
23
Iniciando la Lista...
LISTA:
4
La lista inicia vacia
Cuando se agrega el primer nodo, 
este apunta al ultimo elemento
Primer elemento == último 
elemento ⇒ apunta a el mismo!
24
Insertando un elemento
106
LISTA:
4 8
Misma lógica de inserción que en una lista simplemente enlazada! :D
25
Lista circular doblemente enlazada
106
LISTA:
4
26
Moraleja!
Para Listas Circulares y Circulares DE: 
¿Que diferencia hay entre estas estructuras?
27