Informatica

Listas Dinámicas
1

Listas


Listas
 Listas

Arrays

son flexibles y permiten cambio de implementación Borrar, Modificar, etc.

 

Operaciones
 Insertar,

Tipos de listas
 Simples
 Ordenadas  Pilas

 Colas
 Doblemente  Circulares

enlazadas (LDE)
2

TAD Lista Simple: operaciones
Creación de una lista
Comprobación del estado
crearLista (nombreLista)listaLlena (nombreLista) Booleano listaVacia(nombreLista) Booleano listaVacia (referenciaNodo) Booleano Insertar (nombreLista, valorInfo, posicion) Insertar (nombreLista, valorInfo) Borrar (nombreLista, valorInfo)

Inserción de nodos Borrado de nodos

Búsqueda de un nodo

Buscar (nombreLista, dato) informacion Buscar (nombreLista, dato) referenciaNodo Pertenece (nombreLista,informacion)Booleano
recorrer(nombreLista)

Recorrido de la lista

Acceso a los nodos Modificación de los nodos

Info (referenciaNodo) Informacion Siguiente (referenciaNodo) enlace asignarInfo (referenciaNodo, valorInformacion) asignarEnlace (referenciaNodo, valorEnlace)

3

Definición de la lista

   

Se compone de nodos enlazados. Se debe hacer en una clase separada. Sólo requiere conocerdónde se encuentra el primer nodo de la lista. Para el nombre de la referencia al primer nodo se hace uso de la metáfora: “cabeza de la lista” o “inicio”. Una lista vacía comenzaría con un valor null en el campo sig (siguiente)

4

¿Qué es un Nodo?


Un nodo es un registro con varios campos: unos campos de datos y un campo apuntador. Los primeros son información y el último es una referenciaal siguiente nodo de la lista. El último nodo de la lista contiene una referencia siguiente "null".

5

Clase nodo
public class Nodo { int data; // almacena el dato Nodo sig; //”liga” al próximo nodo }
El campo data representa los datos que almacena el nodo. Puede ser de diferentes tipos de datos, además que éste puede contener la cantidad de datos que se ocupen.
6

Listas

sig

sigsig

7

Creación de una lista


Lista vacía

8

Inserción de un nodo
CASO 1. Inserción al principio de la lista

9

Caso 1.

Inserción al principio

Insertarinicio (inicio, info) //este algoritmo inserta un nodo al inicio de la lista// (nuevo: del tipo inicio) 1- crear (nuevo); 2- hacer nuevo.dato = info nuevo.sig = inicio inicio = nuevo
10

Caso 2.

Inserción enmedio de la lista

Caso 2.1 Insertar antes de

Caso 2.2 Insertar después de

inicio

aux
Ref

nuevo

info
11

Caso 2.1

Insertar antes de

InsertAntes (inicio, info, ref) //aux,nuevo,T son variables de tipo inicio. OK es una variable boolean 1- hacer aux = inicio, Ok = verdadero 2- mientras (aux.dato != ref) y (Ok == verdadero) Si aux.sig != null T = aux, aux = aux.sig. SinoOK = falso 3- Si Ok = = verdadero //se encontró el dato Crear (nuevo) nuevo.dato = info nuevo.sig =aux Si aux = = inicio //es el primer nodo entonces inicio = nuevo si no T.sig = nuevo

12

Caso 2.2

InsertDespues

InsertDespues (inicio, info, Ref) //nuevo y aux so n variables del tipo de inicio, OK es boolean 1- aux = inicio, OK = verdadero 2- Mientras (aux.dato != ref) y (OK ==verdadero) hacer si aux.sig != null entonces aux = aux.sig si no OK = Falso 3- Si OK = = verdadero entonces crear (nuevo) nuevo.dato = info nuevo.sig = aux.sig aux.sig = nuevo
13

Caso 3. Inserción al final de la lista

Insertafinal (inicio, info) // nuevo y T son del tipo inicio
1- Hacer T = inicio 2- mientras T.sig != null recorrer la lista hasta llegar al final 3- Crear (nuevo) 4- nuevo.dato =info nuevo.sig = null T.sig = nuevo
14

Eliminar Nodos
Casos 1 Eliminar el primer nodo

Elimina primero (inicio)
// Se redefine el apuntador inicio. //aux es del tipo inicio

1- hacer Q = inicio; 2- Si aux.sig != null Entonces inicio = aux.sig Sino inicio = null 3- aux = null //quita aux
//que si hay mas de un elemento

15

Caso 2 Eliminar en medio
Caso 2.1 Elimina nodo con X...