Igor Santos Grueiro
Ya conocemos las
listas
Listas de amigos
Listas de compras
Qué es una lista?
¿
Una lista es un conjunto de elementos
homogéneo que cumple:
El orden relativo de estos elementos
es significativo
(1,2,3) != (1,3,2)
Pueden haber elementos repetidos
(1,2,2,2,2,2,2,3)
Ya sabemos utilizar la
lista enlazada
cómo
Pero, ¿
se
implementa por dentro?
Una lista se puede construir:
De forma estática
De forma dinámica
Una lista se puede implementar de
forma estática mediante un array
Tiene una única ventaja:
permite el acceso directo a un
elemento
Tiene múltiples desventajas
1
El tamaño de la lista tiene
que ser fijo y conocido en
tiempo de compilación
En las inserciones y borrados,
hay que provocar un
desplazamiento de elementos
que repercute en el tiempo de
ejecución
Se desaprovecha el
espacio de la memoria
real, en el caso de lista
cortas
ArrayList en java
Para una lista dinámica, de nuevo
Nodo
Nodo siguiente
Object elemento
}
Tiene los siguientes atributos
public class NodoListaEnlazadaSimple {
private Object elemento;
private NodoListaEnlazadaSimple siguiente;
}
}
Un nodo se puede crear
de varias formas
1 Se puede crear vacío
public NodoListaEnlazadaSimple(){
this.elemento = null;
this.siguiente = null;
}
null
2
Se puede crear con un
objeto dentro
public NodoListaEnlazadaSimple(Object x) {
this.elemento = x;
this.siguiente = null;
}
x
3
Se puede crear con un
objeto dentro y un enlace a
otro nodo
public NodoListaEnlazadaSimple(Object x,
NodoListaEnlazadaSimple sig) {
this.elemento = x;
this.siguiente = sig;
}
X
Nodo siguiente
}
Getters y Setters
para el valor del objeto
y para el nodo siguiente
}
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;
}
siguiente
elemento
X
}
Podemos borrar el siguiente nodo
public void borrarSig(){
this.siguiente = this.siguiente.siguiente;
}
Ahora la clase
ListaEnlazadaSimple
}
public class ListaEnlazadaSimple {
private NodoListaEnlazadaSimple primero;
private NodoListaEnlazadaSimple recorrido;
private int tamanyo;
public ListaEnlazadaSimple(){
this.primero = null;
this.recorrido = null;
this.tamanyo = 0;
}
}
Para vaciar el primer nodo y
el recorrido a null
//…
public void vaciar(){
this.primero = null;
this.recorrido = null;
this.tamanyo = 0;
}
//…
Para comprobar si una lista
está vacía comprobamos si
el primero es null
//…
public boolean estaVacia (){
return (this.primero == null);
}
//…
public Object cima(){
return v[cont-1];
}
También, podemos recuperar
el número de elementos
insertados en la lista
//…
public int tamanyo(){
return tamanyo;
}
//…
public Object cima(){
return v[cont-1];
}
Podemos insertar un objeto en la
primera posición de la lista
//…
public void insertarPrimero(Object x) {
primero = new
NodoListaEnlazadaSimple(x, primero);
this.tamanyo++;
}
//…
Primero
x
Cima
public Object cima(){
return v[cont-1];
}
Necesitaremos acceder al nodo en
cierta posición de la lista
//…
private NodoListaEnlazadaSimple
devuelvePos(int pos) {
NodoListaEnlazadaSimple temp =
primero;
for (int i = 1; i <= pos; i++) {
temp = temp.getSiguiente();
}
return temp;
}//…
public Object cima(){
return v[cont-1];
}
Para insertar un objeto en cierta
posición de la lista
//…
public void insertarPos(Object x, int pos) {
if (pos == 0)
primero = new
NodoListaEnlazadaSimple(x, primero);
else
devuelvePos(pos - 1).insertarSig(x);
tamanyo++;
}
//…
Primero
Cima
Pos
siguiente
elemento
X
1
public Object cima(){
return v[cont-1];
}
Para modificar un objeto en cierta
posición de la lista
//…
public void modificarPos(Object x, int
pos) {
NodoListaEnlazadaSimple temp =
devuelvePos(pos);
temp.setElemento(x);
}
//…
public Object cima(){
return v[cont-1];
}
Para borrar un objeto en cierta
posición de la lista
//…
public void borrarPos(int pos) {
if (pos == 0)
primero = primero.getSiguiente();
else {
NodoListaEnlazadaSimple temp =
devuelvePos(pos - 1);
temp.borrarSig();
}
tamanyo--;
}//…
Primero
Cima
Pos
1
public Object cima(){
return v[cont-1];
}
Para borrar un objeto específico
de la lista
//…
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();
else
ant.setSiguiente(temp.getSiguiente());
tamanyo--;
}
}//…
public Object cima(){
return v[cont-1];
}
Podemos devolver un elemento
en cierta posición
//…
public Object extraerPos(int pos) {
return devuelvePos(pos).getElemento();
}//…
public Object cima(){
return v[cont-1];
}
Para buscar un objeto específico
de la lista
//…
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;
}
//…
Las operaciones de recorrido
public Object cima(){
return v[cont-1];
}
Podemos iniciar un recorrido
por la lista
//…
public void inicioRecorrido() {
recorrido = primero;
}//…
public Object cima(){
return v[cont-1];
}
Podemos seguir avanzando por
la lista
//…
public Object getElemento() {
Object x = recorrido.getElemento();
recorrido = recorrido.getSiguiente();
return x;
}//…
public Object cima(){
return v[cont-1];
}
Podemos saber si hemos
acabado el recorrido
//…
public boolean finRecorrido() {
return (recorrido == null);
}
//…
Ésta es la lista
simplemente enlazada
Cada nodo tiene
1 enlace
Pero hay más listas …
Cada nodo tiene
2 enlaces
Optimizan
la inserción por
Listas doblemente
el medio
de la lista
enlazadas
Podemos mejorar la inserción al
final añadiendo una referencia al
nodo final
Primero
Lista con
Último
inserción por el final
Y aún hay más
Pueden
Listas
sercirculares
simplemente
o doblemente enlazadas
Ejercicio
Realizar listas:
Simplemente
enlazada
Simplemente enlazada
con inserción al final
Descargar

listas