1

Listas Dinámicas

2

Listas Listas ≠ Arrays

Listas son flexibles y permiten cambio de implementación

Operaciones Insertar, Borrar, Modificar, etc.

Tipos de listas Simples Ordenadas Pilas Colas Doblemente enlazadas (LDE) Circulares

3

TAD Lista Simple: operacionesCreación de una lista crearLista (nombreLista)

Comprobación del estado listaLlena (nombreLista) → Booleano listaVacia(nombreLista) → Booleano

listaVacia (referenciaNodo) → Booleano

Inserción de nodos Insertar (nombreLista, valorInfo, posicion)Insertar (nombreLista, valorInfo)

Borrado de nodos Borrar (nombreLista, valorInfo)

Búsqueda de un nodo Buscar (nombreLista, dato) → informacion

Buscar (nombreLista, dato) → referenciaNodo

Pertenece (nombreLista,informacion) → BooleanoRecorrido de la lista recorrer(nombreLista)

Acceso a los nodos Info (referenciaNodo) → Informacion

Siguiente (referenciaNodo) → enlace

Modificación de los nodos asignarInfo (referenciaNodo, valorInformacion)asignarEnlace (referenciaNodo, valorEnlace)

4

Definición de la lista Se compone de nodos enlazados. Se debe hacer en una clase separada. Sólo requiere conocer dó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)

5

¿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 referencia al siguiente nodo de la lista. El último nodo de la lista contiene una referencia siguiente "null".

6

Clase nodopublic 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

t ipos de datos, además que éste puede contener la cantidad de datos que se

ocupen.

7

Listas

sig sig sig

8

Creación de una lista

Lista vacía

9

Inserción de un nodo

CASO 1. Inserción al principio de la lista

10

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

11

Caso 2. Inserción en medio de la lista

Caso 2.1 Insertar antes de

Caso 2.2 Insertar después de

info

Ref

nuevo

inicio aux

12

Caso 2.1 Insertar antes de

InsertAntes (inicio, info, ref)//aux,nuevo,T son variables de tipo inicio. OK es una variable

boolean1- hacer aux = inicio, Ok = verdadero2- mientras (aux.dato != ref) y (Ok == verdadero)

Si aux.sig != nullT = aux, aux = aux.sig.

Sino OK = falso 3- Si Ok = = verdadero //se encontró el dato

Crear (nuevo)nuevo.dato = infonuevo.sig =auxSi aux = = inicio //es el primer nodo

entonces inicio = nuevosi no T.sig = nuevo

13

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.sigsi no OK = Falso

3- Si OK = = verdaderoentonces crear (nuevo)

nuevo.dato = infonuevo.sig = aux.sigaux.sig = nuevo

14

Caso 3. Inserción al final de la lista

Insertafinal (inicio, info)// nuevo y T son del tipo inicio1- Hacer T = inicio2- mientras T.sig != null recorrer la lista hasta llegar al final3- Crear (nuevo)4- nuevo.dato = info nuevo.sig = null T.sig = nuevo

15

Eliminar NodosCasos 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 //que si hay mas de un elemento

Entonces inicio = aux.sig

Sino inicio = null3- aux = null //quita aux

16

Caso 2 Eliminar en medioCaso 2.1 Elimina nodo con X información

EliminaNodoX (inicio, x)//aux y T son variables del mismo tipo de inicio, Ok es boolean

1- Hacer aux = inicio , Ok = verdadero2- Repetir mientras (aux.dato != x) y (Ok) hacer

Si aux.sig != null //hay más nodos entonces T = aux, aux = aux.sig

si no Ok = falso3- Si Ok == falso

entonces //el elemento x no existesi no si inicio == aux //x es el primer elemento de la lista

entonces inicio = aux.sigsi no T.sig = aux.sig

  aux = null

17

Caso 2.2 Elimina nodo antes de X información

Algoritmo EliminaAntesX (inicio, x) //aux , T y R son variables del mismo tipo de inicio (apuntador), Ok es

boolean1- Si inicio.dato == x

entonces //no hay nodo que precede a xsino aux = inicio; T = inicio; Ok = falso;

mientras (( aux.info!=x) y (!Ok)) si aux.sig != null entonces R = T; T = aux;

aux= aux.sig; si no Ok = verdadero;

 2- Si Ok entonces //el elemento x no existe

si no si inicio.sig = aux//el elemento a eliminar es el primero entonces inicio = aux sino R.sig = aux; T = null;

X

inicio R T aux

18

Caso 3 Elimina ultimo nodo

Elimina ultimo (inicio) //Se pone un null en el campo sig del penúltimo elemento y se quita el ultimo.//aux, T son del mimo tipo que inicio1. Si inicio.sig == null //que la lista tiene un solo elemento Entonces

inicio = null //quita (inicio) Si no aux = inicio

2. Mientras aux.sig != null hacerT = aux

aux = aux.sig 3. T.sig = null //quita T

aux = null //quita aux

19

Recorrido de una lista dinámicaMetodo Correlista (Nodo inicio);//imprime cada dato de la lista { nodo aux = new nodo();

aux = inicio;while (aux.sig != null) {

escribir (aux.dato);aux = aux.sig;

} }

20

Buscar un nodo con alguna característica

Método Busca (Nodo inicio, info){//Devuelve exito con falso o verdadero nodo aux = new nodo();

boolean exito = falsoaux = inicio;while (aux.sig != null && aux.dato != info)

aux = aux.sig;if ( aux.dato = = info ) exito = verdadero; return exito

}

21

Filas Dinámicas

22

Características de una Fila

El primer elemento en llegar es el primero en servir (FIFO Frist In Frist Out).

El ultimo en llegar se agrega al final El apuntador posee la dirección del siguiente nodo El apuntador puede ser null o puede apuntar al

siguiente nodo

Esta estructura se utiliza en : Simulaciones Sistemas operativos etc…

sigdato sigdato sigdato sigdato …

23

Operaciones de una Fila

Crearfila (nodo inicio) Agregarfila (nodo inicio, int dato) QuitarFila (nodo inicio) Vacio (nodo inicio)

24

Clase nodopublic class Nodo {

int dato; // almacena el dato

Nodo sig; //”liga” al próximo nodo

}

El campo data representa los datos que almacena el nodo. Puede ser de diferentes

t ipos de datos, además que éste puede contener la cantidad de datos que se

ocupen.

25

Crea fila

creaFila (nodo i){

nodo inicio = new nodo();

inicio = i;

}

sigincio

26

Agregar a una Fila un nodo

Agrega(nodo inicio, int dato){Si inicio.sig = null

entonces inicio.sig = nuevo;Sino { nodo p = nuevo nodo();

p.sig = inicio.sigmientas(p.sig!= null)

p = p.sig;}}

sigincio sigdato null

27

Eliminar un elemento de la Fila int quitar(nodo inicio){

int d = -1;Si inicio.sig == null;

regresa d;Sino {

d = inicio.sig.dato;inicio.sig = inicio.sis.sig;

}Regresa d;}

null

sigincio sigdato sigdato sigdato

28

Vaciar una fila

Boolean vacia(nodo inicio){Boolean vacia = false;

Si inicio = null

Regresa true

SinoRegresa vacia

}sigincio sigdato sigdato sigdato

null

29

Pilas Dinámicas

30

Características

Se remueve del tope y se agrega en el tope de la pila (LIFO Last In Frist Out).

Operaciones Creapila (nodo inicio)Quitar (nodo inicio) = popAgregar (nodo inicio, int dato) = pushVacia (nodo inicio)

31

Crear una Pila

creaPila (nodo i){

Nodo inicio = new nodo();

inicio = i

}

sigincio null

32

Agregar un nodo a la Pila (push)

agregaNodo (nodo inicio, int dato){

nodo nuevo = new nodo()

nuevo.dato = info

nuevo.sig = inicio.sig;

inicio.sig = nuevo

}

sigincio sigdato sigdato sigdato null

nuevo

33

Quitar elemento de la Pila (pop) int pop (nodo inicio){

int d = -1;Si inicio.sig == null;

regresa d;Sino {

d = inicio.sig.dato;inicio.sig = inicio.sis.sig;

}Regresa d;}

sigincio sigdato sigdato sigdato

34

Para verificar si un apila esta vacía

Boolean vacia(nodo inicio){Boolean vacia = false;

Si inicio != null

Regresa true

SinoRegresa vacia

}sigincio sigdato sigdato sigdato

35

Lista doblemente enlazada

36

Nodo

public class Nodo {

private int data; // al macena el dato

private Nodo sig; //”liga” al próximo nodo

private Nodo ant; // ”liga” al anterior nodo

}

ant sig

37

Operaciones de una lista doblemente enlazada

Añadir o insertar elementos. Buscar elementos. Borrar elementos. Moverse a través de la lista, siguiente y anterior.

Inicio fin

sig

ant

38

Añadir elemento a una lista vacía

1-nodo = anterior y nodo=siguiente a NULL.

39

Caso 1 Insertar nodo en la primera posición

insertaNodo( nodo)

1-. Nodo=siguiente // debe apuntar a Lista.

2-. Nodo=anterior y Lista=anterior.

3-. Lista=anterior //debe apuntar a nodo.

Insertar nuevo nodo

Nuevonodo

1…

32

nullDato Dato Dato

40

Caso 2 Insertar un elemento en la última posición

InsertarUltimo(nodo)1-. Nodo=siguiente y Lista=siguiente (NULL). 2-. Lista=siguiente // debe apuntar a nodo. 3-. Nodo=anterior //apuntará a Lista.

Dato Dato Dato

Datonull

2

3

1

41

Caso 3 Insertar un nodo en medio.

InsertarMedio (nodo )

1-. Nodo=siguiente apunte a lista=siguiente.

2-. Lista=siguiente //apunte a nodo.

3-. Nodo=anterior //apunte a lista. 4-. Nodo=siguiente=anterior // apunte a nodo.

Dato Dato Dato

Dato

null

231

4

42

Eliminar

Caso 1 Eliminar el único nodo En este caso, ese nodo será el apuntado por Lista.

1-. Eliminamos el nodo.

2-. Hacemos que Lista apunte a NULL.

43

Caso 2Caso 2.1Eliminar el primer nodo

eliminaPrimer( nodo)1-. Si nodo apunta a Lista // hacemos que Lista apunt

Lista=siguiente. 2-. Hacemos que nodo=siguiente=anterior// apunte a

NULL 3-. Borramos el nodo apuntado por nodo.

44

Caso 2.2 Eliminar un nodo intermedio

eliminaMedio(nodo)

1-. Si nodo apunta a Lista

Lista=siguiente

2-. nodo= siguiente

3-. Nodo = anterior

4-. Borramos el nodo apuntado por nodo

45

Caso 3 Eliminar el último nodo

eliminaUltimo(nodo)

1-. Si nodo apunta a Lista

Lista=anterior.

2-nodo=anterior=siguiente apunte a NULL

3-. Borramos el nodo apuntado por nodo.

46

Lista Circular

47

Circular

Una lista circular es una lista lineal en la que el último nodo a punta al primero.

iniciofin

48

Operaciones de una lista circular

las operaciones que se pueden realizar sobre las listas circulares : Añadir o insertar elementos. Buscar o localizar elementos. Borrar elementos. Moverse a través de la lista

49

Insertar un elemento

Insertar elemento en la lista vacía lista apunta a nodo.

lista->siguiente apunte a nodo.

Insertar elemento en una lista no vacía1. Hacemos que nodo = siguiente apunte a lista = siguiente.

2. Después que lista = siguiente apunte a nodo.

50

Eliminar el único nodo de la lista. 1. lista = siguiente mientras lista = siguiente sea distinto de nodo.

2. Hacemos que lista = siguiente apunte a nodo = siguiente.

3. Eliminamos el nodo.

Eliminar un nodo en una lista circular con más de un elemento

1. Borramos el nodo apuntado por lista.

2. Hacemos que lista valga NULL.

Eliminar un elemento de la lista

51

Eliminar un elemento de la lista

Caso general1. Copiamos el contenido del nodo = siguiente sobre el contenido

de nodo.

2. Hacemos que nodo = siguiente apunte a nodo = siguiente = siguiente.

3. Eliminamos nodo = siguiente.

4. Si lista es el nodo = siguiente, hacemos lista = nodo.