Listas simples (Insertar Buscar)

[Dany Solis]

Hola a todos.

Tengo mis métodos para buscar, eliminar Inicio, eliminar Final,Agregar Inicio, Agregar al Final, pero no he podido desarrollar los métodos para:

Buscar y Eliminar, el elemento buscado
Insertar elemento en la posición que indique el usuario.

He leido varios post, pero no he encontrado la solución.

Esto necesito hacerlo en listas simples y Doblemente enlazadas en JAVA, les comparto mis métodos y clases:

Código [Seleccionar] Expandir


//Clase nodo
package asesorialistas;
/*@author Daniel Solis*/
public class Nodo{
   
public int Dato;
public Nodo Sig;//Puntero Enlcae recursivo
//Enlaza los diferentes nodos


//Constructor inicializar nodos
public Nodo(int d){
//Para crear un nodo final
this.Dato=d; 
}
//Constructor para insertar al inicio
public Nodo(int d, Nodo n){
this.Dato=d;
this.Sig=n;
    }
}

//Metodos Lista

package asesorialistas;
/*@author Daniel Solis*/
public class Lista {
//Creando punteros
protected Nodo Inicio, Fin; //Punteros para saber donde inica y donde termina
//Donde esta el Inicio y Fin
public Lista(){
Inicio=null;
Fin=null;
    }
/*----------------------------------------------------------------------------*/
//Metodo para agregar al incio de la lista
public void AgregarInicio(int Elemento){
//Creando el nodo
Inicio = new Nodo(Elemento,Inicio);//Creando el Nodo
if(Fin==null){
    Fin=Inicio;
    }
}
/*----------------------------------------------------------------------------*/
//Metodo para agregar al final
public void AgrearFin(int Elemento){
    if (!EstaVacia()) {
      Fin.Sig=new Nodo(Elemento);
      Fin=Fin.Sig;   
    }else{
        Inicio=Fin=new Nodo(Elemento);
    }
}
/*----------------------------------------------------------------------------*/
//Metodo para mostrar la lista
public void Mostrar(){
Nodo recorrer=Inicio;
while (recorrer!=null){
    System.out.print("["+recorrer.Dato+"]");
    recorrer=recorrer.Sig;
    }
}
/*----------------------------------------------------------------------------*/
//Metodo esta la lista Vacia
public boolean EstaVacia() {
    return Inicio==null; 
}
/*----------------------------------------------------------------------------*/
public int BorrarInicio(){
        //creando el nodo
        int Elemento = Inicio.Dato;
        if(Inicio==Fin){
            Inicio = Fin = null;
        }
        else{
            Inicio=Inicio.Sig;
        }
        return Elemento;
}
/*----------------------------------------------------------------------------*/
public int BorrarFinal(){
        int Elemento = Fin.Dato;
        if(Inicio==Fin){
            Inicio = Fin = null;
        }else{
            Nodo temporal = Inicio;
            while(temporal.Sig != Fin){
                temporal = temporal.Sig;
            }
            Fin = temporal;
            Fin.Sig = null;
        }
        return Elemento;
}
/*----------------------------------------------------------------------------*/
public boolean BuscarElemento (int elemento){
    Nodo temporal=Inicio;
    while (temporal!=null&& temporal.Dato!=elemento)
    {
    temporal=temporal.Sig;
    }
    return temporal!=null;
    }

public boolean BuscarElementoEsp (int elemento){
    Nodo temporal=Inicio;
    while (temporal!=null&& temporal.Dato!=elemento)
    {
    temporal=temporal.Sig;
    }
    return temporal!=null;
    }
}

//Clase Principal

package asesorialistas;
import java.awt.HeadlessException;
import javax.swing.JOptionPane;
/*@author Dany*/
public class Principal {
    public static void main(String[] args) {
        //crear instancias de las clases
        Lista Listita = new Lista();
        //menu do while
        int opcion = 0;
        int Elemento; //valor a la lista (para insertar)
       
        do {
            try {
                opcion = Integer.parseInt(JOptionPane.showInputDialog(null, "***  MENU DE OPCIONES  ***\n"
                        + "1.- Agregar un Elemento al Inicio \n"
                        + "2.- Agregar un Elemento al Final \n"
                        + "3.- Mostrar los Elementos de las listas \n"
                        + "4.- Checar si la lista esta vacia \n"
                        + "5.- Borrar Elemento al inicio \n"
                        + "6.- Borrar Elemento al final \n"
                        + "7.- Buscar Elemento \n"
                        + "8.- Buscar Elemento y eliminar elemento \n"
                        + "9.- Salir \n"));

                switch(opcion){
                   
                    case 1:
                        try {
                            Elemento = Integer.parseInt(JOptionPane.showInputDialog(null, "Ingresa el Elemento "
                                    + "al inicio"));
                            Listita.AgregarInicio(Elemento);
                        } catch (NumberFormatException e) {
                            JOptionPane.showMessageDialog(null,"Error"+e.getMessage());
                        }
                        break;
                       
                    case 2:
                                                try {
                           Elemento = Integer.parseInt(JOptionPane.showInputDialog(null, "Ingresa el Elemento "
                                    + "al final"));
                            Listita.AgrearFin(Elemento);
                        } catch (NumberFormatException e) {
                            JOptionPane.showMessageDialog(null,"Error"+e.getMessage());
                        }
                        break;
 
                    case 3:
                        Listita.Mostrar();
                        System.out.println("");
                        break;
                       
                    case 4:
                        Listita.EstaVacia();
                        break;
                       
                    case 5:
                        try {
                            Elemento = Listita.BorrarInicio();
                            JOptionPane.showMessageDialog(null, "El Elemento eliminado es: "
                                    +Elemento,"Eliminando nodo de inicio",
                                    JOptionPane.INFORMATION_MESSAGE);
                           
                        } catch (NumberFormatException e) {
                            JOptionPane.showMessageDialog(null,"Error"+e.getMessage());
                        }
                        break;
                       
                     case 6:
                        try {
                            Elemento = Listita.BorrarFinal();
                            JOptionPane.showMessageDialog(null, "El Elemento eliminado es: "
                                    +Elemento,"Eliminando nodo de fin",
                                    JOptionPane.INFORMATION_MESSAGE);
                           
                        } catch (NumberFormatException e) {
                            JOptionPane.showMessageDialog(null,"Error"+e.getMessage());
                        }
                        break;
                       
                        case 7:
                            Elemento=Integer.parseInt(JOptionPane.showInputDialog(null,"Ingresa el "+" elemento a buscar...","Buscando nodos en la lista",
                                    JOptionPane.INFORMATION_MESSAGE));
                            if (Listita.BuscarElemento(Elemento)==true) {
                            JOptionPane.showMessageDialog(null, "El elemento " + Elemento + " si esta en la lista",
                                        "nodo encontrado",JOptionPane.INFORMATION_MESSAGE); 
                            }else{JOptionPane.showMessageDialog(null, "El elemento " + Elemento + " no esta en la lista",
                                        "nodo no encintrado",JOptionPane.INFORMATION_MESSAGE);       
                            }   
                        break;
                       
                        case 8:
                            Elemento=Integer.parseInt(JOptionPane.showInputDialog(null,"Ingresa el "+" elemento a buscar...","Buscando nodos en la lista",
                                    JOptionPane.INFORMATION_MESSAGE));
                            if (Listita.BuscarElemento(Elemento)==true) {
                            int resp = JOptionPane.showConfirmDialog(null, "El elemento " + Elemento + " si esta en la lista quieres eliminarlo");
                                    if (JOptionPane.OK_OPTION == resp){
                                            System.out.println("Eliminar registro");
                                            }else{System.out.println("No Eliminar");
                                        }
                            }else{JOptionPane.showMessageDialog(null, "El elemento " + Elemento + " no esta en la lista",
                                        "nodo no encintrado",JOptionPane.INFORMATION_MESSAGE);       
                            }   
                        break;     
                }
            } catch (HeadlessException | NumberFormatException e) {
                JOptionPane.showMessageDialog(null,"Error"+ e.getMessage());
            }
        } while (opcion != 9);
       
    }
}


Espero puedan darme una mano con este ejercicio, saludos.

DS

[Serapis]

Buscar y Eliminar, el elemento buscado
Insertar elemento en la posición que indique el usuario.

Te ilustraré un poco sobre el tema...

He leido varios post, pero no he encontrado la solución.

Más bien, deberías decir que o bien no has sabido buscar o bien no lo has entendido. No te atrevas a decir que soluciones no existen... son temas demasiado recurrentes.

Esto necesito hacerlo en listas simples y Doblemente enlazadas en JAVA

Yo te explico en pseudocódigo, queda a tu esfuerzo pasarlo a Java. En el foro, se ofrece ayuda, no se regalan trabajos hechos, el interesado tiene que poner de su parte...


Vamos con los temas:

public boolean BuscarElemento (int elemento){
   Nodo temporal=Inicio;
   while (temporal!=null&& temporal.Dato!=elemento)
   {
   temporal=temporal.Sig;
   }
   return temporal!=null;
   }

Aquí tu primer error es devolver un buleano.
La función que debe devolver un boleano sería: "ExisteElemento"
...pero no 'BuscarElemento". Buscar debe devolver un nodo, o bien algún dato contenido (se supone que distinto al buscado, porque paraeso es mejor llamar a la función "buleano = Funcion Existe(int dato) ..."

Así, mejor aún una función interna de búsqueda siempre debiera devolver el nodo, la función externa, invocaría a esa interna y devolverá el dato que interese, incluso el índice que ocupa en la lista.
Una cosa más sobre los nombres d elas funciones... Resulta cansino que las llames: BuscarElemento, Guardarelemento, AñadirElemento ... Sobra la palabra elemento.

No estas operando con cebollas, siempre son nodos, luego es redundante, señalar, nodo, elemento, dato. Basta el verbo...

La búsqueda en una lista simplemente enlazada, debe comenzar lógicamente en la raíz, o en el primero...
Cuando se usa una ráiz es un nodo oculto, con lo que una lista aparentemente vacía siempre contiene un nodo oculto y resulta muy útil para delimitar bucles. No obstante no lo usaré en el código, para no forzarte a modificar todo tu código ya hecho.

Código [Seleccionar] Expandir


Nodo = funcion Buscar(int Dato)
   nodo n
   Si (s_Nodos > 0)  ' s_nodos es un contador de los nodos que contiene la lista...  cuando se añade uno, se suma uno, cuando se elimina 1 , se resta uno...
       n= primero
       Hacer mientras ((n.Dato <> dato) y (n.Siguiente <> null))
           n = n.siguiente
       Siguiente
       Si n.Dato = dato
           devolver n  // hacemos esta comprobación, porque el bucle también acaba al llega al final de la lista.
       sino
           devolver null
       fin si
   Sino
       devolver null
   Fin si
Fin funcion

Esa, si quieres puede ser la función privada, y crear una pública:

Código [Seleccionar] Expandir

Buleano = Funcion Existe(int Dato)
   Si Buscar(dato) <> null
       devolver True
   sino
       devolver false
   fin si
fin funcion

Eliminar el elemento:
Una vez somos capaces de buscar y encontrar un nodo, estaremos en condiciones de poder eliminarlo.

Código [Seleccionar] Expandir

buleano = Funcion Eliminar(int Dato)
   nodo n

   n = Buscar(dato)
   Si (n<> null)
       Si n.siguiente = null  // si el que queremos eliminar es el último
           n= null  // borramos el nodo.
       Sino   // no es el último, antes de eliminarlo, tenemos que 'atar' el anterior con el siguiente
               // pero esto sólo podrmeos hacerlo en una lista simple, si tenemos acceso al nodo previo... como es justo el anterior al buscado, no nos vale... exige modificar la función o crear otra...
             // ????. HOP, que pasó...? lee bajo el código de la función  que luego reharemos esta función... con el código que aquí falta.
       fin si
   Sino
       devolver False  // no se encontró, no hay nada que eliminar...
   Fin si
Fin funcion

Una solución para poder eliminar el nodo de una lista simplemente enlazada, sería modificar la función Buscar, para que devuelva de alguna manera también el nodo previo...
Esta función busca un nodo, y si lo encuentra por referencia devuelve el previo. Nota que si el buscado es el primero, el previo sería null.

Código [Seleccionar] Expandir

nodo = Funcion Buscar(int Dato, nodo Anterior)
   nodo n

   Anterior = n   //esto es, lo hace null, por si a la entrada ya contuviera un nodo.
   Si (s_Nodos=0)  // s_nodos es un contador de los nodos que contiene la lista...  cuando se añade uno, se suma uno, cuando se elimina 1, se resta uno...  
       //devolver null
   Sino
       n = primero    
       // Nota que ahora le preguntamos por 1, esto nos simplifica el bucle 'while'...
       Si (s_Nodos > 1)                    
           Hacer
               si n.Dato = dato
                   devolver n  // 'Anterior' se devuelve por referencia con el valor que YA contiene
               si no
                   Anterior = n
                   n = n.siguiente
               fin si
           Siguiente mientras (n.Siguiente <> null)
           //devolver null
       Sino                    
           si n.Dato = dato
               devolver n
           //Sino
               //devolver null
           fin si
       Fin si
   Fin si
   // basta una sola línea para devolver null... si se localiza, se devuelve desde donde se localiza, si no null, desde aquí.  se dejan comentadas donde irían en cada caso
   devolver null
Fin funcion

Con esta función AHORA SI podemos eliminar un nodo dentro de unalista SIMPLEmente enlazada, porque AHORA SI podemos atar de forma sencilla y fácil el anterior y posterior al que se desea eliminar.

Rehacemos la función Eliminar que antes dejamos a medio terminar...

Código [Seleccionar] Expandir

buleano = Funcion Eliminar(int Dato)
   nodo n, p    // nodo a eliminar y nodo previo

   n = Buscar(dato, p)
   Si (n<> null)
       Si n.siguiente = null  // si el que queremos eliminar es el último
           n= null  // borramos el nodo.
       Sino   // no es el último, antes de eliminarlo, tenemos que 'atar' el anterior con el siguiente
              p.siguiente = n.siguiente
              n.siguiente = null   // tiene una referencia a siguiente si no se eliminan todas las referencias de un objeto aún reside en memoria (ocupando espacio aunque no tengamos acceso al objeto. el nodo 'n' quedaría oculto en memoria si esta línea no apareciera).
              n = null
       fin si
       devolver true
   Sino
       devolver False  // no se encontró, no hay nada que eliminar...
   Fin si
Fin funcion

La función Insertar, igualmente es dependiente de la función buscar... Y como ahora tenemos una función 'buscar' OPTIMA, podrmeos además insertar un eleemnto delante o detrás del deseado.

Código [Seleccionar] Expandir


buleano = Funcion Insertar(int DatoInsertar, int DatoReferencia, buleano Detras)
   nodo b, p, n    // nodo a buscar, nodo previo y nodo nuevo

   b = Buscar(DatoReferencia, p)
   Si (b<> null)
       n.Dato = DatoInsertar
       Si detras = False   // es decir se pide colocar delante del nodo de referencia. Exige comprobar que 'b' no sea el primero.
           Si (p <> null)  // si previo es nulo, es porque 'b' sería el primero...
               p.Sigueinte = n
               n.Siguiente = b  
           Sino
               n.Siguiente = b
               primero = n
           Fin si
       Sino   // se pide colocar detrás del nodo de referencia, hay que comprobar que no sea el último.
           Si (b.Siguiente <> null)
               p = b.Siguiente
               b.siguiente = n
               n.Siguiente = p  
           Sino
               b.siguiente = n
               // Ultimo = n
           Fin si
       Fin si
       devolver TRUE  // el nodo de referencia fue encontrado y el nuevo dato insertado donde se pedía...    
   sino
       devolver FALSE  // no se encontró el nodo deseado para insertarlo. Cabría esperar que si no se localiza se añada al final. Eso a tu esfuerzo y consideración...
   fin si
fin funcion


Llevando la cuenta de nodos que contiene la lista, puede además especificarse una inserción en una posición concreta... pero queda a tu esfuerzo, solo nota que al buscar... ya no buscas verificando si el nodo es null, si no, si no se alcanza la cantidad total de ítems, y en cada ciclo se suma uno.

En una lista doblemente enlazada, es más sencillo. La búsqueda vale como la primera (función que puse de búsqueda). No se precisa devolver previo, porque al nodo encontrado, se le puede reclamar el previo no solo el siguiente.
Lo importante con la lista DOBLEmente enlazada es que al eliminar un nodo, primero hay que atar sus dobles referencias, y luego eliminar ambas referencias del nodo a eliminar... antes de eliminar el propio nodo.

Sea 'n' el nodo a eliminar ya localizado en una lista doblemente enlazada, que ni es el primero, ni el último...

Código [Seleccionar] Expandir


   nodo n

  ..... operaciones previas de búsqueda, etc...

   n.previo.siguiente = n.siguiente   // ata al previo el siguiente, ya que 'él dejará de existir,
                    // es necesario, para que la lista siga conectada con siguiente, siguiente, siguiente...
   n.siguiente.previo = n.previo // ata al siguiente con el previo, para que
                   // se pueda seguir recoriendo hacia atrás con x.previo.previo.previo...

   // y se autoelimina, pero primero se 'desata' de sus referencias (de sus vecinos).
   n.siguiente = null  
   n.anterior = null
   n = null  / y finalmente 'se muere' él...