Lectura 3 - Listas Enlazadas

Mdulo 3
Unidad 3
Lectura 3
Materia: Taller de Algoritmos y Estructuras de Datos I

Profesora: Adriana Prez
3- LISTAS ENLAZADAS
Frases introductorias
Las listas enlazadas son estructuras de datos complejas dinmicas que
permiten almacenar los elementos de acuerdo a un criterio de orden, esto
las diferencia de las pilas y colas por tener orden lgico distinto al orden
fsico.
3.1 Conceptos bsicos

Recordemos que hemos visto hasta el momento las estructuras dinmicas
lineales, pila y cola. Si bien estas estructuras son listas enlazadas, vimos que
su comportamiento responde a almacenar datos por orden de llegada
ubicndose siempre despus del ltimo elemento y elimina el primero en el
caso de la cola y el ltimo en el caso de la pila, respondiendo a la
caracterstica FIFO (first input, first output) y LIFO (last inpunt first
output) respectivamente. Cuando listamos los elementos los visualizamos
en el mismo orden en que los ingresamos, es por ello que su orden fsico es
igual a su orden lgico.
Las estructuras dinmicas llamadas listas enlazadas, tienen el mismo
criterio de orden de carga, orden de llegada, pero permiten insertar en
cualquier lugar y eliminar cualquier elemento de la lista.
En forma general, decimos que:
Una lista es una coleccin de elementos llamados generalmente
nodos, donde el orden entre ellos se establece por medio de
referencias; es decir, direcciones o enlaces a otros nodos, con cierto
criterio de carga y caractersticas que condicionarn las operaciones
de insercin y eliminacin de los nodos.
Ahora seguiremos con las estructuras dinmicas lineales listas simplemente

y doblemente enlazadas teniendo en cuenta que pueden ser ordenadas por
un criterio determinado con anterioridad.
La siguiente figura muestra una lista ligada con cuatro elementos.
Llamaremos a cada elemento de la lista, nodo. Cada nodo debe almacenar
el dato y un enlace que seala al nodo siguiente. La lista requiere de la
definicin de una variable que almacene el apuntador del primer nodo.
Cuando decimos primer nodo nos referimos al primero segn el orden
lgico.

Profesora: Adriana Prez | 2
Los nodos ligados no tienen que estar fsicamente adyacentes y el ltimo

tiene Null como enlace marcando el final de la lista, como vemos en la
figura anterior.
El nodo cabecera no
guarda ningn dato, solo
la referencia al primer
nodo de la lista.
Mark Allen Weiss en su libro Estructuras de datos en Java, bibliografa

bsica de la materia, trata las listas enlazadas en varios captulos. En el
captulo 6, hace una introduccin, en el captulo 16 hace la implementacin
en cdigo Java, usted puede codificarlos tal como lo presenta el autor. En
este mdulo veremos otra alternativa de resolucin para que pueda luego
tomar su propia codificacin, respetando siempre las buenas prcticas y la
Cuando la lista est vaca no guarda ninguna referencia en el atributo
siguiente:
Cabecera.sig = Null
Programacin Orientada a Objetos.
La clase nodo de la Lista enlazada es como el que utilizamos en la
estructura Cola, tiene 2 atributos, el objeto a almacenar y el enlace al
siguiente.

ackage com.estructuras;
public class Nodo<T extends Object> {
private T dato; //cualquier tipo de valor,
private Nodo<T> sig;
public Nodo() {
this.dato = null;
this.sig = null;
}
public T getDato() {
return dato;
}
public void setDato(T dato) {
this.dato = dato;
}
public Nodo getSig() {
return sig;
}
public void setSig(Nodo sig) {
this.sig = sig;
}
public Nodo(T dato) {
this.dato = dato;
}
public Nodo(T dato, Nodo sig) {
this.dato = dato;
this.sig = sig;
}
}
La lista enlazada es una estructura de datos compuesta por estos nodos

donde las operaciones de insertar y eliminar la diferencian de las pilas y
colas.
La vista de una lista es la siguiente:

Insercin de un nuevo nodo

El comportamiento es el siguiente:
Tmp = new Nodo();
//Crear un nodo nuevo
Tmp.dato = x;
//Colocar x en el campo dato
Tmp.siguiente = actual.siguiente; //El siguiente al nodo x es b

Actual.siguiente = tmp;
//El siguiente al nodo a es x
Eliminacin de un nuevo nodo

Actual.siguiente = actual.siguiente.siguiente; ; //El anterior enlaza
al siguiente al nodo a eliminar, en este caso, x.

Como se puede apreciar en las figuras anteriores el algoritmo necesita

realizar cambios en los enlaces para que pueda quedar reflejada la
operacin correctamente y al listarla se muestren los nodos que realmente
tiene.
Si bien se pueden almacenar valores primitivos, lo ideal es pensar en que se
pueden almacenar objetos de cualquier clase, ya sea una Java, como por
ejemplo String o Integer, como una definida por usted en el modelo de
resolucin del proyecto, como por ejemplo, Persona, Automovil, Producto,
entre otros.
Nodos auxiliares
Para las operaciones de listas enlazadas es necesario utilizar nodos
auxiliares:
Cabecera: tambin llamado primero, almacena la referencia al

primer nodo que almacena un dato.
Fin: tambin llamado ltimo, puede utilizarse de dos formas, una

de ellas es que el ltimo nodo con valor almacene la referencia a fin
y este almacene el null, que indica que no hay ms elementos. Otra
forma es que el nodo fin/ltimo almacene la referencia al ltimo
nodo de la lista, de esta forma al insertar al ltimo no es necesario
recorrer la lista desde el primero al ltimo, optimizando as el
tiempo de respuesta del algoritmo.
Tmp: tambin llamado nuevo, almacena la referencia al nuevo

nodo.
Actual: tambin llamado aux, es el que se utiliza para recorrer la

lista.
Para recorrer la lista utilice siempre un nodo

auxiliar que no sea cabeza ni fin, de caso
contrario perder las referencias y no podr
encontrar los nodos de la lista.
Lista simplemente enlazada ordenada
La lista simplemente enlazada ordenada almacena los datos con un criterio
de orden, es por ello que debe conocer ese criterio antes de realizar el
algoritmo de insercin.
Como las Pilas y Colas, las listas enlazadas utilizan una Interfaz para las
operaciones, las bsicas son:
Crear()
Insertar()
Eliminar()

Buscar()
Listar()
Tambin podemos agregar otras que consideremos importantes y

necesarias, como por ejemplo:
esVacia() //para saber si no hay elementos en la lista
vaciar() //para volver al estado inicial de vaca
3.2 Comparacin de atributos,

implementacin de mtodos de Java
Teniendo en cuenta que las listas enlazadas tienen orden lgico distinto al
orden fsico, o sea se muestran de acuerdo al orden del criterio establecido
no por el orden de ingreso en memoria, por ejemplo, si se quiere almacenar
los datos de los alumnos ordenados por legajo, es posible que la lista a
cargar sea: 10, 23, 4, 15.
El primer legajo en entrar ser el 10.
Cuando ingrese el 23 lo compara con el 10, como es mayor se ubica

despus, quedando 10, 23
Cuando ingresa el 4, lo compara con el 10 y corresponde que es < al

primero, por lo que lo ubica delante del 10, quedando: 4, 10, 23.
Cuando ingresa el 15 lo compara con 4, no es menor, lo compara con

el 23, no es mayor, por lo que est en el medio 4 < 15 < 23. El
algoritmo debe buscar el lugar dnde debe insertarlo, quedando: 4,
10, 15, 23.
En este caso, lo estamos ordenando por legajo, si hacemos un algoritmo

para este caso no servir para otra situacin distinta, por ejemplo para
ordenar clientes por apellido y nombre.
Como la programacin Orientada a Objetos busca reutilizar el cdigo es
importante generalizar estos algoritmos y que sirvan para todos los objetos,
para ello tenemos que utilizar los mtodos equals() y compareTo() de Java.
El mtodo equals()
El mtodo equals() permite comparar 2 cadenas o 2 objetos, es una funcin
booleana que nos devuelve true cuando son iguales y false cuando son
distintos. Recuerde que este mtodo es de la clase String del package
java.lang, por lo tanto no es necesario importar el paquete en el programa.

//equals
String s1 = Hola";
String s2 = hola";
if (s1.equals(s2)){
// s1 y s2 tinen el mismo contenido, devuelve true
}
if (s1 == s2) {
// compara si s1 y s2 tienen la misma referencia
}
El mtodo compareTo()
Para comparar dos objetos es posible hacerlo con el mtodo compareTo(),
de la clase String del paquete java.lang.
Este mtodo permite comparar por igual, mayor y menor valor,
devolviendo 0, 1 -1 respectivamente. Veamos un ejemplo muy simple:
//compareTo(Object object)
String s1 = Hola";
String s2 = hola";
if (s1.compareTo(s2) > 0) {
// s1 es ms grande que s2
}
else if (s1.compareTo(s2) == 0 {
// s1 y s2 son iguales
}
else
// s1 es menor a s2

Teniendo en cuenta su funcionamiento deberamos conocer dnde se tiene

que escribir el mtodo para luego poder usarlo.
Si la comparacin de dos cadenas u objetos con

equals() devolvi true, la misma comparacin
con compareTo() tiene que devolver 0 (cero).
Qu tenemos que tener en cuenta para usar el mtodo

compareTo()?
Para usar correctamente el mtodo compareTo() se tiene que tener en
cuenta:
El mtodo lo define en la clase del objeto que tiene el atributo a

comparar, por ejemplo si queremos comparar la edad de dos
alumnos, en la clase Alumno, que tiene el atributo edad es donde
coloca el mtodo.
La clase donde define el mtodo debe implementar la interfaz

Comparable.
La interfaz Comparable puede ser usada la que tiene definida en

Java o redefinirla.
Supongamos que tenemos que almacenar Mdicos ordenados por cdigo en

una lista simplemente enlazada, necesitamos las siguientes clases:
Mdico, clase del modelo
Nodo, para almacenar el objeto Mdico y el enlace
ListaSimple, con 2 nodos auxiliares primero y ltimo, adems tiene

las operaciones
ILista, interfaz con las operaciones.

Veamos el cdigo del ejemplo:

package modelo;
import estructuras.*;
@SuppressWarnings("unchecked")
public class Medico implements Comparable {
private
private
private
private
String Nombre;
String Apellido;
Integer CodigoDeMedico;
Integer NumeroDeMatricula;
public Medico() {
}
public String getNombre() {
return Nombre;
}
public void setNombre(String nombre) {
Nombre = nombre;
}
//se completa con los getxx() y setXX() de los dems
atributos
public String toString(){
return "Nombre: " + this.getNombre() +
"\nApellido: " + this.getApellido() +
"\nCodigo Identificatorio: " +
this.getCodigoDeMedico() +
"\nNumero De Matricula: " +
this.getNumeroDeMatricula();
}
//mtodo para comparer el objeto active con el recibido por
cdigo de mdico, devuelve 0, 1 -1
public int compareTo(Object m) {
Medico medico = (Medico)m;
return
this.getCodigoDeMedico().compareTo(medico.getCodigoDeMedico())
}
}

package com.estructuras;
public Nodo() {
this.dato = null;
this.sig = null;
}
this.dato = dato;
}
this.dato = dato;
this.sig = sig;
}
return dato;
}
this.dato = dato;
}
return sig;
}
this.sig = sig;
}
}

public interface ILista {
public
public
public
public
public
public
public
void Vaciar();
void Insertar(Comparable dato);
boolean EsVacia();
boolean Buscar(Comparable dato);
Object Eliminar(Comparable dato);
String ListarAscendente();
String ListarDescendente();
public class Lista<T extends Object> implements ILista {
private Nodo cabecera;
private Nodo ultimo;
public Lista () {
this.cabecera = null;
this.ultimo = null;
}
public Nodo getCabecera() {
return cabecera;
}
public void setCabecera(Nodo primero) {
this.cabecera = primero;
}
public Nodo getUltimo() {
return ultimo;
}
public void setUltimo(Nodo ultimo) {
this.ultimo = ultimo;
}
..
Continuamos con el cdigo de cada operacin definida en la Interfaz

ILista.
Comprobamos si est vaca con:

public boolean EsVacia() {
if (this.cabecera == null && this.ultimo == null){
return true;
}
return false;
}

Vaciamos la Lista con:
public void Vaciar() {

this.cabecera = null;
this.ultimo = null;
}
Listamos de forma ascendente, o sea del primero al ltimo con:
public String ListarAscendente() {

String salida = "";
Nodo auxiliar = this.cabecera;
while(auxiliar != null){
salida += auxiliar.getDato().toString()+"\n";
auxiliar = auxiliar.getSiguiente();
}
return salida;
}
Listamos de forma descendente, o sea del ltimo al primero con:
public String ListarDescendente() {

String salida = "";
Nodo auxiliar = this.ultimo;
salida += auxiliar.getDato().toString()+"\n";
auxiliar = auxiliar.getAnterior();
}
return salida
}

Insertamos un nuevo elemento en la Lista, en este caso un objeto

Mdico ordenado por cdigo
public void Insertar(Comparable dato) {
Nodo nuevo = new Nodo (dato);
Nodo auxAnterior = this.cabecera;
//enlazamos con el nico nodo que hay en la lista
if(this.EsVacia()){
this.cabecera = nuevo;
this.ultimo = nuevo;
}
//si el nuevo cdigo es menor al que estaba primero
else if (nuevo.getDato().compareTo(this.getCabecera().getDato())<0){
//enlaza el nuevo nodo con el que estaba primero
nuevo.setSiguiente(this.getCabecera());
//enlaza la cabecera con nuevo para indicar que es el primero
this.setCabecera(nuevo);
}
else //si el nuevo cdigo es mayor al ltimo
if (nuevo.getDato().compareTo(this.getUltimo().getDato())> 0){
//enlaza el ltimo con el nuevo
this.ultimo.setSiguiente(nuevo);
//siguiente del nuevo es Null por ser ahora el ltimo dato
nuevo.setSiguiente(null);
//enlaza con nuevo para indicar que es el ltimo nodo
this.setUltimo(nuevo);
}
else{ //est en el medio
while(auxiliar != null &&
nuevo.getDato().compareTo(auxiliar.getDato()) > 0){
auxAnterior = auxiliar;
}
//sale del while cuando encuentra su lugar, con auxiliar
parado en el que le sigue al nuevo nodo y auxAnterior en el anterior
nodo
//enlaza el anterior con el nuevo
auxAnterior.setSiguiente(nuevo);
//enlaza el nuevo con el siguiente
nuevo.setSiguiente(auxiliar);
}
}

Buscamos un mdico por cdigo en la lista:

public boolean Buscar(Comparable dato) {
//declaramos un auxiliar para buscar el dato
NodoDoble auxiliar = this.cabecera;
boolean salida = false;
//recorre la lista
//compara el cdigo del nodo visitado con el ingresado
if(auxiliar.getDato().compareTo(dato) == 0){
salida = true;
}
}
return salida;
}
Eliminamos un Mdico de acuerdo a un cdigo ingresado:

public Object Eliminar(Comparable dato) {
Object salida = null;
if (this.EsVacia()){
Mostrar.mostrar("Lista Vacia");
}
else //compara con el primero, si es igual
if(dato.compareTo(this.getCabecera().getDato()) == 0){
salida = this.cabecera.getDato();
//cambia cabecera enlazando con el segundo
this.cabecera = this.cabecera.getSiguiente();
}
else //busca si est en la lista
while(auxiliar != null &&
dato.compareTo(auxiliar.getDato()) != 0){
auxAnterior = auxiliar;
}
If(auxiliar = null){
salida = auxiliar.getDato();
//enlaza el anterior con el siguiente, eliminando el nodo
auxAnterior.setSiguiente(auxAnterior.getSiguiente());
}
return salida;
}
}

3.3 Clases Iteradoras

Como hemos visto hasta ahora, el comportamiento de las listas requiere de
algoritmos que pueden tener estructuras repetitivas en su interior, como lo
son el buscar() y listar().
Las clases iteradoras simplifica el problema que se puede presentar cuando
en la clase Lista se est accediendo a los nodos, puede ser que otro mtodo
lo acceda con un auxiliar con lo cual podemos perder la referencia o estar
visitando un nodo equivocado.
En este caso la posicin de la lista en la que se encontrara sera dado por la
clase iteradora, manteniendo la nocin de la posicin actual y el nodo
cabecera puede ser inicializado por el constructor.
Es necesario que la clase iteradora pertenezca al mismo paquete que la lista,
o sea que est en el package estructuras.
Cada instancia de la clase iteradora da el marco que permite solamente las
operaciones legales sobre la lista como, por ejemplo avanzar.
La clase iteradora requiere de su Interfaz, por lo que estamos agregando
una clase y una interfaz a nuestro esquema anterior.
Se incorporan nuevos mtodos, tales como:
estaDentro(), que refleja que lo encuentra.
Avanzar(), permite que el auxiliar avance secuencialmente
Primero(), coloca el auxiliar en la primera posicin.
Recuperar(), elemento en la posicin actual.
Veamos los cambios necesarios en la clase Lista y en la interfaz ILista

public interface ILista<T extends Object>{
//public void eliminar(Object x); lo sacamos de la interfaz
//public void listarAs();lo sacamos de la interfaz
//public void listarDes();lo sacamos de la interfaz
//public boolean buscar(T x); lo sacamos de la interfaz
public Boolean esVacia();
public void vaciar();
}

public class Lista<T extends Object> implements ILista<T> {
private Nodo<T> cabecera;
private Nodo<T> fin; //puede no usarse
public Lista() {
cabecera = new Nodo(null);

}
Public boolean esVacia() {
Return cabecera.siguinete = null
}
Public void vaciar(){
Cabecera.siguiente = null;
}
.
}
Necesitamos la Interfaz de la Lista Iteradora, podra tener las siguientes

operaciones:
import java.Exception.*;
public interface IListaIter<T extends Object>
void inserter(Comparable x);

void eliminar(Comparable x);
boolean buscar(Comparable x);
void primero();
void avanzar();
Boolean estaDentro();
Object recuperar();
La clase ListaIteradora implementa la interfaz y define los mtodos, en

nuestro caso, solo colocamos la cabecera que es:

import java.exception.*;
public class ListaEnlazadaIter<T extends Object> implements
IListaIter<T> {
.
}
3.4 Listas doblemente enlazadas y listas

circulares
Listas doblemente enlazada
Las estructuras de datos Listas doblemente enlazadas tienen un
comportamiento idntico a las simplemente enlazadas. Si estn ordenadas
su orden fsico es distinto al orden lgico.
Se diferencian en:
que utilizan un nodo con dos enlaces, ya que guarda las direcciones
del anterior y del siguiente nodo.
Se pueden listar del primero al ltimo y del ltimo al primero.
Si bien ocupan ms memoria por tener un enlace ms, es conveniente
utilizarla cuando se requiere su listado descendente.
En cuanto al algoritmo tenemos que recordar que tenemos un enlace ms
para actualizar en cada operacin.
Veamos los primeros casos, cuando est vaca y la creamos con el primer
elemento:

Si insertamos tenemos que tener presente los 3 casos vistos anteriormente:
Menor que el primero:
Mayor que el ltimo:
nuevo.ant = ltimo
nuevo.sig = NULL
ltimo.sig = nuevo
ltimo = nuevo

Insercin al medio:
El mismo criterio se lleva a cabo para eliminar un elemento en la lista,

puede ser el primero, el ltimo o uno del medio.
Veamos grficamente estas operaciones:
Elimina el primero:

Elimina el ltimo:
Los boolean, no aceptan ningn casting, mientras que el

casting de char a byte o short, puede dar un negativo, ya que
char no contempla el signo.
Elimina uno del medio:
Listas circulares
Las listas enlazadas circulares pueden ser simplemente enlazadas o
doblemente enlazadas, ambas tienen la caracterstica de no tener nulos en
los nodos de los extremos.
En las listas simplemente enlazadas, el ltimo nodo enlaza con el primero.
En las listas doblemente enlazadas el primero enlaza con el ltimo nodo y el
ltimo enlaza con el primero.

Recordemos entonces:
La referencia siguiente del ltimo nodo

apunta al primero
En general no tienen nodo cabecera
Se mantiene una referencia al primer
nodo
Se pueden usar simultneamente listas
circulares con listas doblemente enlazadas
Son tiles cuando queremos hacer bsquedas
que permitan circularidad
Ej Editores de textoUna de las caractersticas
importantes de las estructuras de datos es la
reutilizacin.
Su grfica sera:
El cdigo que cambia cuando inserta es el siguiente:

//Inserta primero
Nvo.anterior = ultimo;
Nvo.siguiente = cabecera;
Cabecera.anterior = nuevo;
Ultimo.siguiente = nvo
//Inserta al ltimo
Ultimo.siguiente = nvo;
Nvo.anterior = ultimo;
Nvo.siguiente = cabecera;
Cabecera.anterior = nvo;

El cdigo que cambia cuando elimina es el siguiente:
//Elimina el primero
Cabecera.siguiente.anterior = cabecera.anterior ;
Cabecera = cabecera.siguiente;
Cabecera.anterior = ultimo;
//Elimina al ltimo
Ultimo.anterior.siguiente = cabecera;
Ultimo = ultimo.anterior;
Cabecera.anterior = ultimo;
3.5 Implementacin
Una vez que aprendimos las caractersticas de las estructuras de datos
Listas enlazadas, simples, dobles y circulares con el uso de las Interfaces
necesarias para las operaciones, estamos en condiciones de poder hacer un
ejercicio con Listas doblemente enlazadas con clases Iteradoras.
Hay situaciones en las que es necesario relacionar ms de una estructura
para resolverla. Veamos el siguiente caso:
Una Clnica almacena los datos de los pacientes que van llegando a los
turnos por orden de llegada en una cola por mdico. Como son varios los
mdicos que atienden en un mismo horario, organiza los datos de los
mdicos en una lista doblemente enlazada, ordenada por cdigo de mdico.
Datos del nodo de la Cola:
Objeto paciente
sig de la cola
Datos del nodo de la Lista:

Objeto mdico
Sig de la lista
Objeto Paciente:
Nro. De Historia clnica
Apellido y nombre
Dni

Objeto Mdico:
Cdigo de mdico
Nro. De matrcula
Apellido y nombre
Cola de pacientes
Es necesario disear las clases del modelo y utilizar las clases del package
modelo como librera, o sea si logr que fuesen generales para cualquier
objeto no se deberan modificar, solo reusar.
Efectuar las siguientes operaciones para N pacientes y N mdicos:
Ingresar los datos de los mdicos en la lista.
Cuando llega un paciente buscar el mdico en la lista y cargar los datos en la
cola.
Ingresando un cdigo de mdico, mostrar todos los pacientes que tiene en
cola de espera.

Diagrama de las clases para Lista Doble
Diagrama para la estructura Cola

Clases del modelo: Mdico y Paciente
package modelo;
import estructuras.*;
public class Medico implements Comparable {
private
private
private
private
private
String Nombre;
String Apellido;
Integer CodigoDeMedico;
Integer NumeroDeMatricula;
Cola c; //estructura Cola como atributo
public Medico() {
}
public Medico(String nombre, String apellido,
Integer codigoDeMedico,
Integer numeroDeMatricula, Cola c) {
Nombre = nombre;
Apellido = apellido;
CodigoDeMedico = codigoDeMedico;
NumeroDeMatricula = numeroDeMatricula;
Es importante
this.c
= c; que repase tambin las sentencias
}repetitivas for, while y do while utilizndolos en la
programacin.

return Nombre;
}
Nombre = nombre;
}
//dems getxx() y setxx()
public Cola getCola() {
return c;
}
public void setCola(Cola c) {
this.c = c;
}
"\nCodigo Identificatorio: " +
this.getCodigoDeMedico() +
"\nNumero De Matricula: " +
this.getNumeroDeMatricula();
}
//mtodo para comparer los medicos por cdigo
public int compareTo(Object m) {
Medico medico = (Medico)m;
if(this.getCodigoDeMedico().compareTo(medico.getCodi
goDeMedico()) == 0){
}
return this.getCodigoDeMedico();
}

Clase Paciente:
package modelo;
public class Paciente implements Comparable {
private
private
private
private
String Nombre;
String Apellido;
Integer NumeroDeHistoriaClinica;
Integer Dni;
public Paciente() {
}
public Paciente(String nombre, String apellido,
Integer numeroDeHistoriaClinica, Integer
dni) {
Nombre = nombre;
Apellido = apellido;
NumeroDeHistoriaClinica = numeroDeHistoriaClinica;
Dni = dni;
}
return Nombre;
}
Nombre = nombre;
}
"\nNumero De Historia Clinica: " +
this.getNumeroDeHistoriaClinica() +
"\nDni: " + this.getDni();
}
//mtodo para comparer a completer con el atributo necesario
public int compareTo(Object o) {
return 0;
}
}

Cdigo del Nodo simple:
public Nodo() {
this.dato = null;
this.sig = null;
}
return dato;
}
this.dato = dato;
}
return sig;
}
this.sig = sig;
}
this.dato = dato;
}
this.dato = dato;
this.sig = sig;
}
}

Interfaz para la estructura Cola:
public interface ICola {
public
public
public
public
public
public
public
public
public
int tamanyo();
boolean isVacia();
void vaciar();
void insertar(Object dato);
Object primero();
void listar();
Object quitarPrimero();
void buscar(Object dato);
Object buscarO(Object dato);
Estructura Cola:
public class ColaEnlazada implements ICola {
private Nodo primero;
private Nodo ultimo;
private int tamanyo;
public ColaEnlazada() {
this.primero = null;
this.ultimo = null;
this.tamanyo = 0;
}
.. //getxx() y setxx() necesarios
Operaciones
public boolean isVacia() {
return (primero==null);
}
public void vaciar() {
primero=null;
ultimo=null;
}
//inserta un Nuevo elemento
public void insertar(Object dato) {
if (dato!=null) {
Nodo nuevo = new Nodo(dato, null);
tamanyo++;
if (isVacia()) {
this.primero=nuevo;
} else {
ultimo.setSig(nuevo);
}
ultimo=nuevo;
}
}

//retorna el primer dato

public Object primero() {
if(isVacia()) return null;
return (primero.getDato());
}
public Object quitarPrimero() {
Object dato = null;
if (!isVacia()) {
tamanyo--;
dato = primero.getDato();
primero=primero.getSig();
if (primero == null) {
ultimo = null;
}
}
return dato;
}
public void listar() {
if(isVacia()) return;
Nodo aux = this.primero;
while(aux!=null) {
System.out.println(aux.getDato().toString());
aux = aux.getSig();
}
}
//busca un dato con equals()
public void buscar(Object dato) {
if(isVacia()) return;
int cont=1;
Nodo aux = primero.getSig();
while ((aux!=null) &&
!(aux.getDato().equals(dato))) {
cont++;
aux=aux.getSig();
}
if (aux==null)
System.out.println("No se encontro");
else
System.out.println("Se encontro " +
aux.getDato().toString() + " en el nodo n: " + cont);
}

//busca un objeto y lo retorna

public Object buscarO(Object dato) {
Nodo aux = primero.getSig();
while ((aux!=null)&&
!(aux.getDato().equals(dato))) {
aux=aux.getSig();
}
if(aux!=null)
return aux.getDato();
return null;
}
}
Nodo doble:
public class NodoDoble<T extends Object>{
private T dato;//cualquier tipo de valor,
private NodoDoble<T> sig;
private NodoDoble<T> ant;
public NodoDoble() {
this.dato = null;
this.sig = null;
this.ant = null;
}
public NodoDoble(T dato) {
this.dato = dato;
}
public NodoDoble(T dato, NodoDoble sig) {
this.dato = dato;
this.sig = sig;
}
public NodoDoble(T dato, NodoDoble sig, NodoDoble ant)
{
this.dato = dato;
this.sig = sig;
this.ant = ant;
}
//con sus getxx() y setxx()

Interfaz de la lista:
public interface IListaDoble<T extends Object>{
public Boolean esVacia();
public void vaciar();
public void listarAscendente();
public void listarDescendente();
}
Interfaz de la Lista Iteradora:

import com.exception.ElementoNoEncontradoException;
public interface IListaIter<T extends Object> {
//declara dos constants para los mensajes
static final String MSJ_NO_ENCONTRADO="Elemento no encontrado";
static final String MSJ_FALLO_ELIMINACION="Fallo eliminacion
elemento no encontrado";
public void imprimir();
void insertarOrdenado(T dato);
void insertar (T x,T y) throws ElementoNoEncontradoException;
void avanzar();
boolean estaDentro();
T recuperar();
void primero();
boolean buscar (T x);
void eliminar (T x) throws ElementoNoEncontradoException;
}

Cdigo de la Listadoblemente enlazada:

public class ListaDoble<T extends Object> implements IListaDoble<T> {
private NodoDoble<T> cab;
private NodoDoble<T> fin;
public ListaDoble () {
cab = null;
fin = null;
}
public NodoDoble getCabecera () {
return this.cab;
}
public NodoDoble getFin () {
return this.fin;
}
public Boolean esVacia () {
return (this.cab == null);
}
public void vaciar () {
this.cab = null;
this.fin = null;
}
//mtodos para insertar ordenado que son llamados desde la ListaIter
public void insertar (T dato) {
NodoDoble<T> nvo = new NodoDoble (dato);
this.cab = nvo;
this.fin = nvo;
}
public void insertarPrimero (T dato) {
if ( esVacia() )
this.cab = this.fin = new NodoDoble (dato);
else {
nvo.setSig(cab);
nvo.setAnt(null);
nvo.getSig().setAnt(nvo);
this.cab = nvo;
}
}
public void insertarUltimo (T dato) {
if ( esVacia() )
this.cab = this.fin = new NodoDoble (dato);
else {
nvo.setSig(null);
nvo.setAnt(this.fin);
nvo.getAnt().setSig(nvo);
this.fin = nvo;
}
}
public void insertarMedio (NodoDoble auxSig,NodoDoble auxAnt, T
dato) {
Taller de Algoritmos
y Estructuras de Datos I
NodoDoble<T> nvo Materia:
= new NodoDoble
(dato);
auxAnt.setSig(nvo);
nvo.setAnt(auxAnt);
//mtodos para eliminar llamados desde ListaIter

public void eliminarPrimero() {
this.cab = this.cab.getSig();
this.cab.setAnt(null);
}
public void eliminarUltimo() {
this.fin = this.fin.getAnt();
this.fin.setSig(null);
}
//Elimina el nodo que se encuentra en el medio, entre dos Nodos
public void eliminarMedio (NodoDoble auxSig, NodoDoble auxAnt)
{
auxAnt.setSig(auxSig);
auxSig.setAnt(auxAnt);
auxSig.getAnt().setAnt(null);
auxAnt.getSig().setSig(null);
}
// Elimina el nodo que se le pasa por parametro, cuando el
mismo se encuentra en el medio, entre dos Nodos
public void eliminarMedio (NodoDoble nodoAEliminar) {
nodoAEliminar.getAnt().setSig(nodoAEliminar.getSig());
nodoAEliminar.getSig().setAnt(nodoAEliminar.getAnt());
nodoAEliminar.setAnt(null);
nodoAEliminar.setSig(null);
}
//Lista del primero al ltimo
public void listarAscendente() {
if (this.esVacia()) {
System.out.println ("La lista est vaca.");
}
NodoDoble<T> aux = this.getCabecera();
while (aux != null) {
System.out.println (aux.getDato().toString());
aux = aux.getSig();
}
}
//Lista del ultimo al primero
public void listarDescendente() {
if (this.esVacia()) {
System.out.println ("La lista est vaca.");
return;
}
NodoDoble<T> aux = this.getFin();
System.out.println (aux.getDato().toString());
aux = aux.getAnt();
}
System.out.println( "\n" );
}
}

Cdigo de la clase Lista Iteradora:

import com.exception.ElementoNoEncontradoException;//o java.exception
public class ListaEnlazadaIter<T extends Object> implements
IListaIter<T> {
protected ListaDoble<T> laLista;
protected NodoDoble<T> actual;
//constructor de la clase
public ListaEnlazadaIter(ListaDoble unaLista) {
laLista=unaLista;
actual=laLista.esVacia()?unaLista.getCabecera():unaLista.getCab
ecera().getSig();
}
public NodoDoble<T> getActual() {
return actual;
}
public void setActual(NodoDoble<T> actual) {
this.actual = actual;
}
//mtodo para listar los elementos
public void imprimir() {
if (laLista.esVacia()) {
System.out.println("Es Vacia");
return;
}
//mtodo para listar los elementos
public void imprimir() {
System.out.println("Es Vacia");
return;
}
NodoDoble<T> aux = laLista.getCabecera();
System.out.println (aux.getDato());
aux = aux.getSig();
}
System.out.println( "\n" );
}
//mtodo para insertar
public void insertar (T x,T y) throws ElementoNoEncontradoException
{
//controla que no est el elemento en la lista
if(!this.buscar(x)) new
ElementoNoEncontradoException(MSJ_NO_ENCONTRADO);
this.insertar(x); //llama a insertar()
}

//inserta un elemento en la lista enlazada no ordenada

public void insertar (T x) throws ElementoNoEncontradoException
{
NodoDoble<T> nuevoNodo=new NodoDoble(x);
laLista.insertarPrimero(x);
} else {
laLista.insertarUltimo(x);
}
actual=nuevoNodo;
}
public void avanzar() { //mtodo para avanzar en el recorrido
if(actual!=null) {
actual=actual.getSig();
}
}
public boolean estaDentro() { //devuelve verdadero si lo
encuentra
return actual!=null && actual!=laLista.getCabecera();
}
public T recuperar() { //devuelve el elemento encontrado
return estaDentro()?actual.getDato(): null;
}
public void primero() {
actual=laLista.getCabecera(); // devuelve el primero
}
public boolean buscar (T x)
{ //busca un objeto y devuelve True si
lo encuentra
NodoDoble<T> itr = laLista.getCabecera();
while (itr!=null &&
((Comparable)itr.getDato()).compareTo(x)!=0)
itr=itr.getSig();
if (itr!=null) {
actual=itr;
return true;
}
return false;
}
//busca un objeto y devuelve el objeto si lo encuentra
public Object buscarO (T x)
{
while (itr!=null &&
itr=itr.getSig();
if (itr!=null) {
actual=itr;
return itr.getDato();
}
return null;
}

//mtodo para inserter ordenado

public void insertarOrdenado(T dato) {
if (dato!=null) {
if (laLista.esVacia()) { //si no hay datos llama a
inserter primero
NodoDoble<T> nuevoNodo=new NodoDoble(dato);
actual=nuevoNodo;
laLista.insertarPrimero(dato);
return;
} else {
NodoDoble<T> nodoAux = laLista.getCabecera();
//busca el lugar que debe ocupar y llama al mtodo que lo hace,
insertarPrimero(), insertarMedio() o insertarUltimo()de la clase
ListaDoble
while (nodoAux!=null) {
if((((Comparable)
dato).compareTo(nodoAux.getDato())) < 0) {
if(nodoAux.getAnt()!=null) {
laLista.insertarMedio(nodoAux,
nodoAux.getAnt(), dato);
return;
} else {
return;
}
} else if (((Comparable)
dato).compareTo(nodoAux.getDato()) == 0) {
if(nodoAux.getAnt()!=null) {
laLista.insertarMedio(nodoAux,
nodoAux.getAnt(), dato);
return;
} else {
return;
}
}
nodoAux = nodoAux.getSig();
}
laLista.insertarUltimo(dato);
}
}
}

//mtodo para eliminar

public void eliminar (T x) throws ElementoNoEncontradoException {
while (itr!=null &&
itr=itr.getSig();
// Si encontro el dato procedo a eliminarlo
if(itr!=null) {
// En caso que la lista este compuesto por un solo
nodo Elimino la lista
if (itr.getAnt() == null && itr.getSig() == null) {
laLista.vaciar();
} else {
//Esta al Principio de la Lista
if (itr.getAnt() == null) {
laLista.eliminarPrimero();
return;
//Esta al Final de la Lista
} else if (itr.getSig() == null) {
laLista.eliminarUltimo();
return;
// Esta en Medio de la Lista
} else {
laLista.eliminarMedio(itr.getSig(),
itr.getAnt());
//laLista.eliminarMedio(itr);
}
}
}
}
}

Conclusin
Con lo visto en esta unidad usted est en condiciones de plantear el diseo
de clases y la codificacin organizada en paquetes de dichas clases.
En el planteo de solucin de un caso deber ver en qu estructuras de datos
almacenar los objetos, para ello tiene las estructuras estticas como las
colecciones de arreglos o las estructuras dinmicas lineales como Pila, Cola,
Listas enlazadas.
Dependiendo de cmo deba tratar los datos almacenados est en
condiciones de poder elegir la estructura que ms le convenga utilizar.
Recuerde siempre tratar de disear cdigo reutilizable y tener sus propias
libreras, las cuales podr utilizar en distintos proyectos.
Espero que le haya sido de utilidad lo aprendido en este mdulo.

Bibliografa Lectura 3
Mark Allen Weiss, Estructuras de Datos en Java, ed. Addison Wesley. 2000
Deitel y Deitel, Java cmo programar , sptima edicin, ed. Pearson, 2008.
Pressman Roger, (2006), Ingeniera de Software. Un enfoque prctico 6ta.
edicin, Ed. McGraw Hill
ORACLE, Oracle 10g: Programacin Java, Gua del Alumno, 2003
www.uesiglo21.edu.ar


Lectura 3 - Listas Enlazadas

Cargado por

Copyright:

Formatos disponibles

Lectura 3 - Listas Enlazadas

Cargado por

Información del documento

Descripción original:

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Lectura 3 - Listas Enlazadas

Cargado por

Copyright:

Formatos disponibles

Mdulo 3

Materia: Taller de Algoritmos y Estructuras de Datos I

3.1 Conceptos bsicos

Ahora seguiremos con las estructuras dinmicas lineales listas simplemente

Materia: Taller de Algoritmos y Estructuras de Datos I

Los nodos ligados no tienen que estar fsicamente adyacentes y el ltimo

Mark Allen Weiss en su libro Estructuras de datos en Java, bibliografa

Materia: Taller de Algoritmos y Estructuras de Datos I

La lista enlazada es una estructura de datos compuesta por estos nodos

Materia: Taller de Algoritmos y Estructuras de Datos I

Insercin de un nuevo nodo

Tmp = new Nodo();

//Crear un nodo nuevo

//Colocar x en el campo dato

Tmp.siguiente = actual.siguiente; //El siguiente al nodo x es b

//El siguiente al nodo a es x

Eliminacin de un nuevo nodo

Materia: Taller de Algoritmos y Estructuras de Datos I

Como se puede apreciar en las figuras anteriores el algoritmo necesita

Cabecera: tambin llamado primero, almacena la referencia al

Fin: tambin llamado ltimo, puede utilizarse de dos formas, una

Tmp: tambin llamado nuevo, almacena la referencia al nuevo

Actual: tambin llamado aux, es el que se utiliza para recorrer la

Para recorrer la lista utilice siempre un nodo

Materia: Taller de Algoritmos y Estructuras de Datos I

Tambin podemos agregar otras que consideremos importantes y

esVacia() //para saber si no hay elementos en la lista

vaciar() //para volver al estado inicial de vaca

3.2 Comparacin de atributos,

El primer legajo en entrar ser el 10.

Cuando ingrese el 23 lo compara con el 10, como es mayor se ubica

Cuando ingresa el 4, lo compara con el 10 y corresponde que es < al

Cuando ingresa el 15 lo compara con 4, no es menor, lo compara con

En este caso, lo estamos ordenando por legajo, si hacemos un algoritmo

Materia: Taller de Algoritmos y Estructuras de Datos I

Materia: Taller de Algoritmos y Estructuras de Datos I

Teniendo en cuenta su funcionamiento deberamos conocer dnde se tiene

Si la comparacin de dos cadenas u objetos con

Qu tenemos que tener en cuenta para usar el mtodo

El mtodo lo define en la clase del objeto que tiene el atributo a

La clase donde define el mtodo debe implementar la interfaz

La interfaz Comparable puede ser usada la que tiene definida en

Supongamos que tenemos que almacenar Mdicos ordenados por cdigo en

Mdico, clase del modelo

Nodo, para almacenar el objeto Mdico y el enlace

ListaSimple, con 2 nodos auxiliares primero y ltimo, adems tiene

ILista, interfaz con las operaciones.

Materia: Taller de Algoritmos y Estructuras de Datos I

Materia: Taller de Algoritmos y Estructuras de Datos I

Materia: Taller de Algoritmos y Estructuras de Datos I

Continuamos con el cdigo de cada operacin definida en la Interfaz

Comprobamos si est vaca con:

Materia: Taller de Algoritmos y Estructuras de Datos I

Vaciamos la Lista con:

public void Vaciar() {

Listamos de forma ascendente, o sea del primero al ltimo con:

public String ListarAscendente() {

Listamos de forma descendente, o sea del ltimo al primero con:

public String ListarDescendente() {