La lista circular doble es una especie de lista enlazada “doblemente enlazada”, pero que posee una característica adicional para el desplazamiento dentro de la lista, “ésta no tiene fin” y tiene 2 apuntadores a si misma.
Para que la lista sea sin fin, el puntero siguiente del último elemento apuntará hacia el 1er elemento y el puntero anterior del primer elemento apuntara hacia el ultimo elemento de la lista en lugar de apuntar al valor NULL, como hemos visto en el caso de listas enlazadas simples o doblemente enlazadas.
En las listas circulares dobles, nunca se llega a una posición en la que ya no sea posible desplazarse.
Cuando se llegue al último elemento, el desplazamiento volverá a comenzar desde el primer elemento.
Los operaciones básicas de una lista circular doble son:
· Insertar: inserta un nodo con dato x en la lista, pudiendo realizarse esta inserción al principio o final de la lista o bien en orden.
· Eliminar: elimina un nodo de la lista, puede ser según la posición o por el dato.
· Buscar: busca un elemento en la lista.
· Localizar: obtiene la posición del nodo en la lista.
· Imprimir: imprime los elementos de la lista.
Nodo principal
public class Nodo {
private Integer dato;
private Nodo anterior;
private Nodo siguiente;
}
Método Insertar al inicio
public void insertarInicio(Integer d){
Nodo nuevo=new Nodo(d);
if(inicio==null)
inicio=nuevo;
else{
Nodo aux=inicio;
while(aux.getSiguiente()!=inicio)
aux=aux.getSiguiente();
aux.setSiguiente(nuevo);
nuevo.setAnterior(aux);
nuevo.setSiguiente(inicio);
inicio.setAnterior(nuevo);
inicio=nuevo;
}
}
Método insertar al final
public void insertarFinal(Integer d){
Nodo nuevo=new Nodo(d);
if(inicio==null)
inicio=nuevo;
else{
Nodo aux=inicio;
while(aux.getSiguiente()!=inicio)
aux=aux.getSiguiente();
aux.setSiguiente(nuevo);
nuevo.setAnterior(aux);
nuevo.setSiguiente(inicio);
inicio.setAnterior(nuevo);
}
}
Método insertar ordenadamente
public void agregarOrdenados(Integer d){
Nodo nuevo=new Nodo(d);
if(inicio==null)
inicio=nuevo;
else{
Nodo aux=inicio;
while((aux.getSiguiente()!=inicio) && (aux.getDato()<d)){
aux=aux.getSiguiente();
}
if((aux.getSiguiente()==inicio) && (aux.getDato()<d)){
aux.setSiguiente(nuevo);
nuevo.setAnterior(aux);
nuevo.setSiguiente(inicio);
inicio.setAnterior(nuevo);
}else{
Nodo ant=aux.getAnterior();
nuevo.setAnterior(ant);
ant.setSiguiente(nuevo);
nuevo.setSiguiente(aux);
aux.setAnterior(nuevo);
if((aux==inicio) && (inicio.getDato()>d))
inicio=nuevo;
}
}
}
Método imprimir
public void imprimir(){
if(inicio==null)
System.out.println("<-->NULL<-->");
else{
Nodo aux=inicio;
System.out.print("<--> Inicio");
do{
System.out.print(" <--> "+aux.getDato());
aux=aux.getSiguiente();
}while(aux!=inicio);
System.out.println(" <-->NULL<-->");
}
}
Método buscar elemento
public boolean buscar(Integer d){
Nodo aux=inicio;
while((aux.getSiguiente()!=inicio) && (!(aux.getDato().equals(d))))
aux=aux.getSiguiente();
return aux.getDato().equals(d);
}
No hay comentarios:
Publicar un comentario