igor santos grueiro. ya conocemos las listas listas de amigos
TRANSCRIPT
![Page 1: Igor Santos Grueiro. Ya conocemos las listas Listas de amigos](https://reader034.vdocumento.com/reader034/viewer/2022051615/5531517b55034681568b4861/html5/thumbnails/1.jpg)
Programación IIListas
Igor Santos Grueiro
![Page 2: Igor Santos Grueiro. Ya conocemos las listas Listas de amigos](https://reader034.vdocumento.com/reader034/viewer/2022051615/5531517b55034681568b4861/html5/thumbnails/2.jpg)
Ya conocemos las
listas
![Page 3: Igor Santos Grueiro. Ya conocemos las listas Listas de amigos](https://reader034.vdocumento.com/reader034/viewer/2022051615/5531517b55034681568b4861/html5/thumbnails/3.jpg)
Listas de amigos
![Page 4: Igor Santos Grueiro. Ya conocemos las listas Listas de amigos](https://reader034.vdocumento.com/reader034/viewer/2022051615/5531517b55034681568b4861/html5/thumbnails/4.jpg)
Listas de compras
![Page 5: Igor Santos Grueiro. Ya conocemos las listas Listas de amigos](https://reader034.vdocumento.com/reader034/viewer/2022051615/5531517b55034681568b4861/html5/thumbnails/5.jpg)
¿Qué es una lista?
![Page 6: Igor Santos Grueiro. Ya conocemos las listas Listas de amigos](https://reader034.vdocumento.com/reader034/viewer/2022051615/5531517b55034681568b4861/html5/thumbnails/6.jpg)
Una lista es un conjunto de elementos homogéneo que cumple:
![Page 7: Igor Santos Grueiro. Ya conocemos las listas Listas de amigos](https://reader034.vdocumento.com/reader034/viewer/2022051615/5531517b55034681568b4861/html5/thumbnails/7.jpg)
El orden relativo de estos elementos es significativo
(1,2,3) (1,3,2)!=
![Page 8: Igor Santos Grueiro. Ya conocemos las listas Listas de amigos](https://reader034.vdocumento.com/reader034/viewer/2022051615/5531517b55034681568b4861/html5/thumbnails/8.jpg)
Pueden haber elementos repetidos
(1,2,2,2,2,2,2,3)
![Page 9: Igor Santos Grueiro. Ya conocemos las listas Listas de amigos](https://reader034.vdocumento.com/reader034/viewer/2022051615/5531517b55034681568b4861/html5/thumbnails/9.jpg)
Ya sabemos utilizar la
lista enlazada
![Page 10: Igor Santos Grueiro. Ya conocemos las listas Listas de amigos](https://reader034.vdocumento.com/reader034/viewer/2022051615/5531517b55034681568b4861/html5/thumbnails/10.jpg)
Pero, ¿cómo se implementa por dentro?
![Page 11: Igor Santos Grueiro. Ya conocemos las listas Listas de amigos](https://reader034.vdocumento.com/reader034/viewer/2022051615/5531517b55034681568b4861/html5/thumbnails/11.jpg)
Una lista se puede construir:
De forma estática De forma dinámica
![Page 12: Igor Santos Grueiro. Ya conocemos las listas Listas de amigos](https://reader034.vdocumento.com/reader034/viewer/2022051615/5531517b55034681568b4861/html5/thumbnails/12.jpg)
Una lista se puede implementar de forma estática mediante un array
![Page 13: Igor Santos Grueiro. Ya conocemos las listas Listas de amigos](https://reader034.vdocumento.com/reader034/viewer/2022051615/5531517b55034681568b4861/html5/thumbnails/13.jpg)
Tiene una única ventaja:permite el acceso directo a un
elemento
![Page 14: Igor Santos Grueiro. Ya conocemos las listas Listas de amigos](https://reader034.vdocumento.com/reader034/viewer/2022051615/5531517b55034681568b4861/html5/thumbnails/14.jpg)
Tiene múltiples desventajas
![Page 15: Igor Santos Grueiro. Ya conocemos las listas Listas de amigos](https://reader034.vdocumento.com/reader034/viewer/2022051615/5531517b55034681568b4861/html5/thumbnails/15.jpg)
El tamaño de la lista tiene que ser fijo y conocido en
tiempo de compilación 1
![Page 16: Igor Santos Grueiro. Ya conocemos las listas Listas de amigos](https://reader034.vdocumento.com/reader034/viewer/2022051615/5531517b55034681568b4861/html5/thumbnails/16.jpg)
En las inserciones y borrados, hay que provocar un
desplazamiento de elementos que repercute en el tiempo de
ejecución2
![Page 17: Igor Santos Grueiro. Ya conocemos las listas Listas de amigos](https://reader034.vdocumento.com/reader034/viewer/2022051615/5531517b55034681568b4861/html5/thumbnails/17.jpg)
Se desaprovecha el espacio de la memoria real, en el caso de lista
cortas3
![Page 18: Igor Santos Grueiro. Ya conocemos las listas Listas de amigos](https://reader034.vdocumento.com/reader034/viewer/2022051615/5531517b55034681568b4861/html5/thumbnails/18.jpg)
ArrayList en java
![Page 19: Igor Santos Grueiro. Ya conocemos las listas Listas de amigos](https://reader034.vdocumento.com/reader034/viewer/2022051615/5531517b55034681568b4861/html5/thumbnails/19.jpg)
Para una lista dinámica, de nuevo
Object elementoNodo siguiente
Nodo
![Page 20: Igor Santos Grueiro. Ya conocemos las listas Listas de amigos](https://reader034.vdocumento.com/reader034/viewer/2022051615/5531517b55034681568b4861/html5/thumbnails/20.jpg)
public class NodoListaEnlazadaSimple {
private Object elemento;private NodoListaEnlazadaSimple siguiente;
}
}
Tiene los siguientes atributos
![Page 21: Igor Santos Grueiro. Ya conocemos las listas Listas de amigos](https://reader034.vdocumento.com/reader034/viewer/2022051615/5531517b55034681568b4861/html5/thumbnails/21.jpg)
}
Un nodo se puede crear de varias formas
![Page 22: Igor Santos Grueiro. Ya conocemos las listas Listas de amigos](https://reader034.vdocumento.com/reader034/viewer/2022051615/5531517b55034681568b4861/html5/thumbnails/22.jpg)
Se puede crear vacío1
public NodoListaEnlazadaSimple(){this.elemento = null;this.siguiente = null;
}
![Page 23: Igor Santos Grueiro. Ya conocemos las listas Listas de amigos](https://reader034.vdocumento.com/reader034/viewer/2022051615/5531517b55034681568b4861/html5/thumbnails/23.jpg)
null
![Page 24: Igor Santos Grueiro. Ya conocemos las listas Listas de amigos](https://reader034.vdocumento.com/reader034/viewer/2022051615/5531517b55034681568b4861/html5/thumbnails/24.jpg)
Se puede crear con un objeto dentro2
public NodoListaEnlazadaSimple(Object x) {this.elemento = x;this.siguiente = null;
}
![Page 25: Igor Santos Grueiro. Ya conocemos las listas Listas de amigos](https://reader034.vdocumento.com/reader034/viewer/2022051615/5531517b55034681568b4861/html5/thumbnails/25.jpg)
x
![Page 26: Igor Santos Grueiro. Ya conocemos las listas Listas de amigos](https://reader034.vdocumento.com/reader034/viewer/2022051615/5531517b55034681568b4861/html5/thumbnails/26.jpg)
Se puede crear con un objeto dentro y un enlace a
otro nodo3public NodoListaEnlazadaSimple(Object x,
NodoListaEnlazadaSimple sig) {this.elemento = x;
this.siguiente = sig;}
![Page 27: Igor Santos Grueiro. Ya conocemos las listas Listas de amigos](https://reader034.vdocumento.com/reader034/viewer/2022051615/5531517b55034681568b4861/html5/thumbnails/27.jpg)
XNodo siguiente
![Page 28: Igor Santos Grueiro. Ya conocemos las listas Listas de amigos](https://reader034.vdocumento.com/reader034/viewer/2022051615/5531517b55034681568b4861/html5/thumbnails/28.jpg)
}
Getters y Setters para el valor del objeto y para el nodo siguiente
![Page 29: Igor Santos Grueiro. Ya conocemos las listas Listas de amigos](https://reader034.vdocumento.com/reader034/viewer/2022051615/5531517b55034681568b4861/html5/thumbnails/29.jpg)
}
Podemos insertar un nodo siguiente
al nodo
public void insertarSig(Object x){NodoListaEnlazadaSimple nuevoNodo = new
NodoListaEnlazadaSimple();nuevoNodo.elemento = x;nuevoNodo.siguiente = this.siguiente;this.siguiente = nuevoNodo;
}
![Page 30: Igor Santos Grueiro. Ya conocemos las listas Listas de amigos](https://reader034.vdocumento.com/reader034/viewer/2022051615/5531517b55034681568b4861/html5/thumbnails/30.jpg)
elementosiguiente
X
![Page 31: Igor Santos Grueiro. Ya conocemos las listas Listas de amigos](https://reader034.vdocumento.com/reader034/viewer/2022051615/5531517b55034681568b4861/html5/thumbnails/31.jpg)
}
Podemos borrar el siguiente nodo
public void borrarSig(){this.siguiente = this.siguiente.siguiente;
}
![Page 32: Igor Santos Grueiro. Ya conocemos las listas Listas de amigos](https://reader034.vdocumento.com/reader034/viewer/2022051615/5531517b55034681568b4861/html5/thumbnails/32.jpg)
![Page 33: Igor Santos Grueiro. Ya conocemos las listas Listas de amigos](https://reader034.vdocumento.com/reader034/viewer/2022051615/5531517b55034681568b4861/html5/thumbnails/33.jpg)
Ahora la clase
ListaEnlazadaSimple
![Page 34: Igor Santos Grueiro. Ya conocemos las listas Listas de amigos](https://reader034.vdocumento.com/reader034/viewer/2022051615/5531517b55034681568b4861/html5/thumbnails/34.jpg)
public class ListaEnlazadaSimple {
private NodoListaEnlazadaSimple primero;
private NodoListaEnlazadaSimple recorrido;
private int tamanyo;
public ListaEnlazadaSimple(){this.primero = null;this.recorrido = null;this.tamanyo = 0;
}}
}
![Page 35: Igor Santos Grueiro. Ya conocemos las listas Listas de amigos](https://reader034.vdocumento.com/reader034/viewer/2022051615/5531517b55034681568b4861/html5/thumbnails/35.jpg)
//…public void vaciar(){
this.primero = null;this.recorrido = null;this.tamanyo = 0;
}//…
Para vaciar el primer nodo y el recorrido a null
![Page 36: Igor Santos Grueiro. Ya conocemos las listas Listas de amigos](https://reader034.vdocumento.com/reader034/viewer/2022051615/5531517b55034681568b4861/html5/thumbnails/36.jpg)
//…public boolean estaVacia (){
return (this.primero == null);}//…
Para comprobar si una lista está vacía comprobamos si
el primero es null
![Page 37: Igor Santos Grueiro. Ya conocemos las listas Listas de amigos](https://reader034.vdocumento.com/reader034/viewer/2022051615/5531517b55034681568b4861/html5/thumbnails/37.jpg)
//…public int tamanyo(){
return tamanyo;}//…
También, podemos recuperar el número de elementos
insertados en la lista
public Object cima(){ return v[cont-1]; }
![Page 38: Igor Santos Grueiro. Ya conocemos las listas Listas de amigos](https://reader034.vdocumento.com/reader034/viewer/2022051615/5531517b55034681568b4861/html5/thumbnails/38.jpg)
//…public void insertarPrimero(Object x) {
primero = new NodoListaEnlazadaSimple(x, primero);
this.tamanyo++;}//…
Podemos insertar un objeto en la primera posición de la lista
public Object cima(){ return v[cont-1]; }
![Page 39: Igor Santos Grueiro. Ya conocemos las listas Listas de amigos](https://reader034.vdocumento.com/reader034/viewer/2022051615/5531517b55034681568b4861/html5/thumbnails/39.jpg)
Primero Cima
x
![Page 40: Igor Santos Grueiro. Ya conocemos las listas Listas de amigos](https://reader034.vdocumento.com/reader034/viewer/2022051615/5531517b55034681568b4861/html5/thumbnails/40.jpg)
//…private NodoListaEnlazadaSimple
devuelvePos(int pos) {NodoListaEnlazadaSimple temp =
primero;for (int i = 1; i <= pos; i++) {
temp = temp.getSiguiente();}return temp;
}//…
Necesitaremos acceder al nodo en cierta posición de la lista
public Object cima(){ return v[cont-1]; }
![Page 41: Igor Santos Grueiro. Ya conocemos las listas Listas de amigos](https://reader034.vdocumento.com/reader034/viewer/2022051615/5531517b55034681568b4861/html5/thumbnails/41.jpg)
//…public void insertarPos(Object x, int pos) {
if (pos == 0)primero = new NodoListaEnlazadaSimple(x, primero);
elsedevuelvePos(pos - 1).insertarSig(x);
tamanyo++;}//…
Para insertar un objeto en cierta posición de la lista
public Object cima(){ return v[cont-1]; }
![Page 42: Igor Santos Grueiro. Ya conocemos las listas Listas de amigos](https://reader034.vdocumento.com/reader034/viewer/2022051615/5531517b55034681568b4861/html5/thumbnails/42.jpg)
elementosiguiente
X
Primero Cima Pos 1
![Page 43: Igor Santos Grueiro. Ya conocemos las listas Listas de amigos](https://reader034.vdocumento.com/reader034/viewer/2022051615/5531517b55034681568b4861/html5/thumbnails/43.jpg)
//…public void modificarPos(Object x, int pos) {
NodoListaEnlazadaSimple temp = devuelvePos(pos);
temp.setElemento(x);}//…
Para modificar un objeto en cierta posición de la lista
public Object cima(){ return v[cont-1]; }
![Page 44: Igor Santos Grueiro. Ya conocemos las listas Listas de amigos](https://reader034.vdocumento.com/reader034/viewer/2022051615/5531517b55034681568b4861/html5/thumbnails/44.jpg)
//…public void borrarPos(int pos) {
if (pos == 0)primero = primero.getSiguiente();
else {NodoListaEnlazadaSimple temp =
devuelvePos(pos - 1);temp.borrarSig();
}tamanyo--;
}//…
Para borrar un objeto en cierta posición de la lista
public Object cima(){ return v[cont-1]; }
![Page 45: Igor Santos Grueiro. Ya conocemos las listas Listas de amigos](https://reader034.vdocumento.com/reader034/viewer/2022051615/5531517b55034681568b4861/html5/thumbnails/45.jpg)
Primero Cima Pos 1
![Page 46: Igor Santos Grueiro. Ya conocemos las listas Listas de amigos](https://reader034.vdocumento.com/reader034/viewer/2022051615/5531517b55034681568b4861/html5/thumbnails/46.jpg)
//…public void borrar(Object x) {
NodoListaEnlazadaSimple ant = null;NodoListaEnlazadaSimple temp = primero;while ((temp != null) && (!temp.getElemento().equals(x))) {
ant = temp;temp = temp.getSiguiente();
}if (temp != null) {
if (temp == primero)primero = temp.getSiguiente();
elseant.setSiguiente(temp.getSiguiente());
tamanyo--;}
}//…
Para borrar un objeto específico de la lista
public Object cima(){ return v[cont-1]; }
![Page 47: Igor Santos Grueiro. Ya conocemos las listas Listas de amigos](https://reader034.vdocumento.com/reader034/viewer/2022051615/5531517b55034681568b4861/html5/thumbnails/47.jpg)
//…public Object extraerPos(int pos) {
return devuelvePos(pos).getElemento();}//…
Podemos devolver un elemento en cierta posición
public Object cima(){ return v[cont-1]; }
![Page 48: Igor Santos Grueiro. Ya conocemos las listas Listas de amigos](https://reader034.vdocumento.com/reader034/viewer/2022051615/5531517b55034681568b4861/html5/thumbnails/48.jpg)
//…public int buscar(Object x) {
int i = 0;NodoListaEnlazadaSimple temp = primero;while ((i < tamanyo) && (!temp.getElemento().equals(x))) {
temp = temp.getSiguiente();i++;
}if (i >= tamanyo)
return -1;else
return i;}//…
Para buscar un objeto específico de la lista
public Object cima(){ return v[cont-1]; }
![Page 49: Igor Santos Grueiro. Ya conocemos las listas Listas de amigos](https://reader034.vdocumento.com/reader034/viewer/2022051615/5531517b55034681568b4861/html5/thumbnails/49.jpg)
Las operaciones de recorrido
![Page 50: Igor Santos Grueiro. Ya conocemos las listas Listas de amigos](https://reader034.vdocumento.com/reader034/viewer/2022051615/5531517b55034681568b4861/html5/thumbnails/50.jpg)
//…public void inicioRecorrido() {
recorrido = primero;}//…
Podemos iniciar un recorrido por la lista
public Object cima(){ return v[cont-1]; }
![Page 51: Igor Santos Grueiro. Ya conocemos las listas Listas de amigos](https://reader034.vdocumento.com/reader034/viewer/2022051615/5531517b55034681568b4861/html5/thumbnails/51.jpg)
//…public Object getElemento() {
Object x = recorrido.getElemento();recorrido = recorrido.getSiguiente();return x;
}//…
Podemos seguir avanzando por la lista
public Object cima(){ return v[cont-1]; }
![Page 52: Igor Santos Grueiro. Ya conocemos las listas Listas de amigos](https://reader034.vdocumento.com/reader034/viewer/2022051615/5531517b55034681568b4861/html5/thumbnails/52.jpg)
//…public boolean finRecorrido() {
return (recorrido == null);}//…
Podemos saber si hemos acabado el recorrido
public Object cima(){ return v[cont-1]; }
![Page 53: Igor Santos Grueiro. Ya conocemos las listas Listas de amigos](https://reader034.vdocumento.com/reader034/viewer/2022051615/5531517b55034681568b4861/html5/thumbnails/53.jpg)
Ésta es la lista
simplemente enlazada
![Page 54: Igor Santos Grueiro. Ya conocemos las listas Listas de amigos](https://reader034.vdocumento.com/reader034/viewer/2022051615/5531517b55034681568b4861/html5/thumbnails/54.jpg)
Cada nodo tiene 1 enlace
![Page 55: Igor Santos Grueiro. Ya conocemos las listas Listas de amigos](https://reader034.vdocumento.com/reader034/viewer/2022051615/5531517b55034681568b4861/html5/thumbnails/55.jpg)
Pero hay más listas …
![Page 56: Igor Santos Grueiro. Ya conocemos las listas Listas de amigos](https://reader034.vdocumento.com/reader034/viewer/2022051615/5531517b55034681568b4861/html5/thumbnails/56.jpg)
Cada nodo tiene 2 enlaces
Listas doblemente enlazadas
Optimizan la inserción por el medio de la lista
![Page 57: Igor Santos Grueiro. Ya conocemos las listas Listas de amigos](https://reader034.vdocumento.com/reader034/viewer/2022051615/5531517b55034681568b4861/html5/thumbnails/57.jpg)
Podemos mejorar la inserción al final añadiendo una referencia al
nodo final
Lista con inserción por el final
Primero Último
![Page 58: Igor Santos Grueiro. Ya conocemos las listas Listas de amigos](https://reader034.vdocumento.com/reader034/viewer/2022051615/5531517b55034681568b4861/html5/thumbnails/58.jpg)
Y aún hay más
Listas circularesPueden ser simplemente o doblemente enlazadas
![Page 59: Igor Santos Grueiro. Ya conocemos las listas Listas de amigos](https://reader034.vdocumento.com/reader034/viewer/2022051615/5531517b55034681568b4861/html5/thumbnails/59.jpg)
Ejercicio
Realizar listas:Simplemente enlazadaSimplemente enlazada con inserción al final
: