Listas.
Tratamiento de listas en Java
Listas.
Modelo.
Modelo.
Lista
Memoria dinámica
inicio
nombre
Memoria estática
NodoLista
10
12
13
21
n
u
l
l
Aspectos sintácticos: clase Lista.
 La clase Lista identifica una referencia (puntero) a un objeto
(o null).
 La declaración de la clase Lista debe incluir:
 Las variables miembro.
 El/los constructor/es.
 [Opcional] Otros métodos que vayan a ser utilizados por objetos
externos.
 Ejemplo:
public class Lista {
NodoLista inicio;
String nombre;
public ListaEnlazada () {
inicio = null;
nombre = null;
}
// Otros métodos
}
Aspectos sintácticos: clase NodoLista
 La estructura de datos que representa los nodos de una
lista debe contemplarse como una clase (NodoLista.java).
 Se debe declarar:
 Las variables miembro (clave y sig).
 El/los constructor/es.
 El destructor [innecesario en Java].
 [Opcional] Otros métodos que vayan a ser utilizados por objetos
externos.
 Código:
class NodoLista {
int clave;
NodoLista sig;
NodoLista (int dato) {
clave = dato;
sig = null;
}
// otros métodos
}
Listas.
Algoritmos básicos con listas
Algoritmos básicos.
 Una sola ejecución:


Insertar al principio.
Eliminar el primero.
 Recorrido de la lista (recursivo):
 Sin modificar la estructura:

Recorrido completo: Mostrar el contenido de una lista.
 Modificando la estructura:

Recorrido completo:
 Insertar al final.
 Obtener el duplicado de una lista.
 Destruir una lista.
Lista
lista
 Crear nuevo nodo con la
información de entrada
 Enlazar el nuevo nodo a la
lista
inicio
 Insertar al principio.
nombre
10
13
NodoLista
21
aux
dato
static void insertarAlPrincipio (Lista lista, int dato) {
//¡ATENCION! No se verifica la introducción de claves repetidas.
NodoLista aux;
aux = new NodoLista (dato);
aux.sig = lista.inicio;
lista.inicio = aux;
}
null
Proceso único.
Inserción al principio. Modelo simplificado.
 Situación inicial.
 Creación de un nuevo nodo.
 Situación final.
Modelo de funcionamiento desde el
programa principal
public static void main (String [ ] args) {
Lista lista; //Declaración de la variable (puntero) lista de clase Lista
Memoria estática
Memoria dinámica
null
Variable lista
Lista = new Lista (); // Construcción de un objeto de clase Lista
Memoria dinámica
nombre
Variable lista
inicio
Memoria estática
Objeto de clase Lista
insertarAlPrincipio (lista,10); //Ejecución del método insertarAlPrincipio
nombre
}
Variable lista
Objeto de clase Lista
10
null
Memoria dinámica
inicio
Memoria estática
Objeto de clase NodoLista
Proceso único.
 Eliminar el primero.
Lista
static void eliminarPrimero (Lista lista) {
if (lista.inicio != null)
lista.inicio = lista.inicio.sig;
else System.out.println ("Error, lista vacia");
}
¿Y si la lista tiene un solo nodo?
nombre
inicio
lista
10
13
NodoLista
21
null
Recorrido completo de la lista.
Ejemplo: Mostrar el contenido.
public void mostrarLista () {
mostrarLista (inicio);
}
static void mostrarLista (NodoLista nodoLista) {
if (nodoLista != null) {
System.out.println (nodoLista.clave + " ");
mostrarLista (nodoLista.sig);
}
else System.out.println ("FIN");
}
Modificación de la estructura. Recorrido
completo
Insertar al final. Algoritmo.
• Módulo de llamada no recursivo (Lista).
• Módulo recursivo (NodoLista).
• Devuelve un objeto de la clase NodoLista.
• Se inicializa el valor devuelto con el propio argumento:;
• Se “reemplaza” el puntero nodoLista.sig por el valor
devuelto: );
resul = nodoLista;
• En la fase de transición se genera el nuevo nodo.
nodoLista.sig = insertar (nodoLista.sig, dato);
• El método solo surte efecto en la instancia de la fase de vuelta
correspondiente al último nodo original.
Se recuerda que en Java los argumentos solo pueden
pasarse “por valor”.
Modificación de la estructura. Recorrido
completo.
Insertar al final. Código
static void insertarAlFinal (Lista l, int dato) {
//¡ATENCION! No se verifica la introduccion de claves repetidas.
l.inicio = insertarAlFinal (l.inicio,dato);
}
static NodoLista insertarAlFinal (NodoLista nodoLista, int dato) {
NodoLista resul = nodoLista;
if (nodoLista != null)
nodoLista.sig = insertarAlFinal (nodoLista.sig, dato);
else {
resul = new NodoLista (dato);
//resul.sig = nodoLista; (Innecesario, ya es null)
}
return resul;
}
Modificación de la estructura. Recorrido
completo .
Insertar al final. Modelo físico.
8
dato
resul
null
null
Instancia 3
8
null
nodoLista
8
Instancia 2
resul
dato
4
Instancia 1
8
null
nodoLista
resul
dato
lanzadera
2
8
dato
nombre
inicio
nodoLista
lista
nodoLista.sig = insertarAlFinal (nodoLista.sig, 8);
Modificación de la estructura. Recorrido
completo.
Insertar al final. Modelo simplificado
 Situación inicial.
4
2
inicio
nombre
null
Lista
resul
8
null
 Fase de transición.
8
null
NodoLista
2
null
nombre
inicio
Lista
4
NodoLista
 Fase de vuelta.
Instancia 1
Instancia 2
NodoLista
2
4
null
nombre
inicio
Lista
Instancia 3
Recorrido completo. Obtener el duplicado de
una lista.
 Combinación de algoritmos básicos:
 Recorrido completo sin modificar estructura (lista origen).
 Insertar (lista destino). Alternativas:


En la fase de ida: insertarAlFinal.
En la fase de vuelta: insertarAlPrincipio.
static void duplicarLista (Lista listaO, Lista listaD) {
listaD.inicio = duplicarLista (listaO.inicio);
}
static NodoLista duplicarLista (NodoLista nodoListaO) {
NodoLista resul;
NodoLista aux;
if (nodoListaO != null) {
resul = duplicarLista (nodoListaO.sig);
aux = new NodoLista (nodoListaO.clave);
aux.sig = resul;
resul = aux;
}
else resul = null;
return resul;
}
Recorrido completo. Obtener el duplicado de una lista.
 Combinación de algoritmos básicos:
 (lista origen) Recorrido completo sin modificar estructura
 (lista destino) Insertar un nodo al principio de la lista en la fase de
vuelta
static void duplicarLista (Lista listaO, Lista listaD) {
listaD.inicio = duplicarLista (listaO.inicio);
}
static NodoLista duplicarLista (NodoLista nodoListaO) {
NodoLista resul;
NodoLista aux;
if (nodoListaO != null) {
resul = duplicarLista (nodoListaO.sig);
aux = new NodoLista (nodoListaO.clave);
aux.sig = resul;
resul = aux;
}
else resul = null;
return resul;
}
Descargar

Tema 2. Tablas