Listas Java

Listas Dobles.

El método deleteFromtail( ) indica un problema inherente a las listas ligadas simples. Los nodos en este tipo de listas contienen solo referencias a los sucesores, por lo que no hay acceso inmediato a los predecesores. Por esa razón, delateFromTail( ) se implementó con un ciclo que no permitió encontrar al predecesor de tail. Aunue cuando este procesador esta, por así decirlo en la mira se encuentra fuera del alcance tenemos que examinar la lista completo para detenernos justo frene a tail de modo que podamos eliminarlo. Para las listas largas y ejecuciones frecuentes de deleteFromTail ( ) esto puede ser impedimento para cambiar el procesamiento de la lista.

Listas Circulares

Una lista circular es una lista lineal que en la que el último elemento apunta al primero. Entonces es posible acceder a cualquier elemento de la lista desde cualquier punto dado. Las operaciones sobre una línea circular resultan más sencillas, ya que se evitan casos especiales. Por ejemplo, el método añadir de la clase CListaLinealSE<T> expuesta anteriormente contemplada dos casos: insertar al principio de la lista e insertar a continuación de un elemento. Como una lista circular, estos dos casos se reducen a uno.

Cuando recorremos una lista circular, diremos que hemos llegado al final de la misma cuando nos encontremos de nuevo en el punto de partida, suponiendo desde luego, que el punto de partida se guarda de alguna manera en la lista; por ejemplo con una referencia fija al mismo, esta referencia puede sr el primer elemento de la lista; también puede ser al último elemento, en cuyo caso también es conocida la dirección del primer elemento. Otra posible solución seria poner un elemento especial identificable en cada lista circular como lugar de partida. Este elemento especial recibe el nombre de elemento de cabecera de la lista. Esto presenta, además, la ventaja de que la lista circular no estará nunca vacía.

Como ejemplo vamos a construir una lista circular con una referencia fija al último elemento. Una lista circular con una referencia al último elemento equivalente a una lista lineal recta con dos referencias, una al principio y otra al final.

Para construir una lista circular, primero tendremos que definir la clase de objetos que van a formar parte de la misma. Por ejemplo, cada elemento de la lista puede definirse como una estructura de datos con dos miembros: una referencia al elemento siguiente y otra al área de datos. El área de datos puede ser de un tipo predefinido o de un tipo definido por el usuario. Según esto, el tipo de cada elemento de la lista puede venir definido de la forma siguiente:

Private class CElemento

{

//Atributos

private T datos;

private CElemento siguiente ; // siguiente elemento

//Metodo

Private CElemento( ) {} // constructor

Primate CElemento (T d, CElemento s) // constructor

{

Datos = d;

Siguiente = s;

}

}

Veamos que por tratarse de una lista lineal siempre mente enlazada aunque sea circular, la estructura de sus elementos no varía con respecto a lo estudiado anteriormente.

Podemos autorizar el proceso de implementar una lista circular diseñando una clase CListaCircularSE que proporcione los atributos y métodos necesarios para crear cada elemento de la lista, así como para permitir el acceso a los mismos. Esta clase nos permitirá posteriormente derivar otras clases que sean más específicas; por ejemplo, una clase para manipular pilas o una clase para manipular colas.

Operaciones básicas con listas

Las operaciones básicas que podemos realizar con las listas incluyen fundamentalmente las siguientes:

• Insertar un elemento en una lista

• Buscar un elemento en una lista

• Borrar un elemento de una lista

• Recorrer los elementos de la lista

• Borrar todos los elementos de la lista

Partiendo de las definiciones.

Class CElementoLse

{

// Atributos

Int dato;

CElementoLse siguiente; // referencia al siguiente elemento

// Metodos

CElementoLse() {} // constructor sin parámetros

CElementoLse (int d) // constructor con parámetros

{

Dato = d;

}

}

Public class Test

{

Public static void main (String [] args)

{

CELementoLse p, q, r; //referecnias

}

}

Vamos a exponer en los siguientes apartados como realizar cada una de las operaciones básicas. Observe que por sencillez vamos a trabajar con una lista de enteros.

Inserción de un Elemento al comienzo de la lista.

Supongamos una lista lineal referenciada por p. para insertar un elemento al principio de la lista, primero se crea el elemento y después se reasigna las referencias tal como a continuación:

q = new CElementoLse():

q.dato = n // asignación de valores

q =.siguiente = p; // reasignación de referencias

Estas operaciones básicas nos sugieren como crear una lista. Para ello y, partiendo de una lista vacía, no tenemos más que repetir la operación de insertar un elemento al comienzo de una lista, tantas veces como elementos deseemos que tenga dicha lista. Veámoslo a continuación:

//Crear una lista lineal simplemente enlazada

Public class Test

{

Public static void main (String[] args)

{

CElementoLse p, q; // referencias

Integer n = null; int ;

//crear una lista de enteros

System.out.println(“Introducir datos. Finalizar con CTRL + Z.”);

P = null; // la lista esta vacía

System.out.print(“dato”);

While((n=Leer.datoInt()) !=null)

{

q=new CElementoLse();

q.dato = n;

q.siguiente = p;

p= q;

System.out.print(“dato”);

}

}

}

Notar que el orden de los elementos en la lista, es inverso al orden en el que se han llegado. Asimismo, como es ya habitual, utilizamos la clase Leer diseñada para leer datos del teclado.

Buscar en una lista un elemento con un valor X

Supongamos que queremos buscar un determinado elemento en una lista cuyo primer elemento esta referencia por p. La búsqueda es secuencial y termina cuando se encuentra en el elemento, o bien cuando se llega al final de la lista.

q=p

System.out.print(“Dato a buscar”) ; x= leer.datoInt();

While ( q != null && q.dato !=x)

q= q.siguiente; // q referencia al siguiente elemento

Observe

...