jueves, 14 de diciembre de 2017

Listas Enlazadas Circulares Dobles

Listas Enlazadas Circulares Dobles

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

Creación de un nodo de entrada en Java

Un nodo de entrada se utiliza para recibir un mensaje en un flujo de mensajes, normalmente de un origen no soportado por los nodos de entr...