Java

Introducción: una simple colección
Implemente una clase denominada Lista. La clase deberá
mantener una colección de números y proveer los
siguientes métodos:
public class Lista{
public void agregarAlFinal(int data){
void agregarAlFinal(int data){
...
}
public void imprimirContenido(){
...
}
public boolean estaContenido(int data){
...
}
public boolean eliminar(int data){
...
}
}Listas dinámicas simplemente enlazadas
Listas dinámicas simplemente enlazadas
Franco Guidi Polanco
Escuela de Ingeniería Industrial
Pontificia Universidad Católica de Valparaíso, Chile
fguidi@ucv.cl

Actualización: 17 de noviembre de 2010
Franco Guidi Polanco (PUCV-EII)

Introducción: una simple colección

17-11-2010

2

Aproximación al uso de listas dinámicas
Supongamos laclase Pontífice.

Recuerda la clase que has implementado… más
adelante la revisitaremos.

public class Pontífice{
private String Nombre;
private Pontifice sucesor;
public Pontífice(String n Pontífice s){
nombre = n;
sucesor = s;
}
public void setNombre(String n){
nombre = n;
}
public String getNombre(){
return nombre;
}
public void setSucesor(Pontífice s){
sucesor = s;
}
publicPontífice getSucesor(){
return sucesor;
}

Los objetos de
esta clase
tienen un
nombre y una
referencia un
referencia a un
sucesor. El
sucesor es un
objeto de la
bj
misma clase:
}

Franco Guidi Polanco (PUCV-EII)

17-11-2010

3

Franco Guidi Polanco (PUCV-EII)

17-11-2010

4

Aproximación al uso de listas dinámicas

Aproximación al uso de listas dinámicas

Supongaque una aplicación tiene una variable de tipo
Pontífice.

Dado:
“Pedro”

Pontífice p2 = new Pontífice (“Lino” , null)
Pontífice p1 = new Pontífice(“Pedro”, p2);

Explique qué hace el siguiente código:

Podemos imaginar que en la memoria existirán dos objetos
imaginar que en la memoria existirán dos objetos
relacionados de la siguiente forma:
1A04

1A04

“Lino”System.out.println( p1.getNombre() );

30F1

“Pedro” 30F1

“Lino”

p1

Y el siguiente:
el siguiente:
null

System.out.println( p1.getSucesor().getNombre() );

p1

Representaremos la situación anterior sin hacer explícitas
la situación anterior sin hacer explícitas
las direcciones de memoria (excepto null):
“Pedro”

Y el siguiente:
Pontifice aux = p1.getSucesor();
aux
p1.getSucesor();System.out.println( aux.getNombre() );

“Lino”

p1
Franco Guidi Polanco (PUCV-EII)

17-11-2010

5

Franco Guidi Polanco (PUCV-EII)

Aproximación al uso de listas dinámicas: recorrido

Dado:
“Lino”

“Anacleto”

...

“Pedro”
“Benedicto
XVI”

“Anacleto”

...

“Benedicto
XVI”

La búsqueda de un nombres se logra mediante el siguiente
código:
código:

La impresión detodos los nombres se logra
mediante el siguiente código:

String buscado = ... // aquí se asigna un valor
boolean está = false;
Pontífice aux = p1;
while( aux != null ){
if( aux.getNombre().equals( buscado ) )
está = true;
aux = aux.getSucesor();
aux
}
if( está )
System.out.println( buscado + “ sí está” );
else
System.out.println( buscado + “ no está” );

Pontífice aux = p1;while( aux != null ){
System.out.println( aux.getNombre() );
aux
);
aux = aux.getSucesor();
}

17-11-2010

“Lino”

p1

p1

Franco Guidi Polanco (PUCV-EII)

6

Aproximación al uso de listas dinámicas: recorrido

Dado:
“Pedro”
“Pedro”

17-11-2010

7

Franco Guidi Polanco (PUCV-EII)

17-11-2010

8

Esquema tentativo de una lista dinámica
simplemente enlazada

Listasdinámicas simplemente enlazadas
Son estructuras dinámicas: se asigna memoria
para los elementos de la lista en la medida que es
necesario.
Cada elemento se almacena en una variable
dinámica denominada nodo.
En la lista simplemente enlazada, cada nodo
apunta al nodo que contiene el elemento siguiente

Nodos

data

data

data

data

head

null

ListaEnlazada

Franco Guidi...