Listas Enlazadas en Java

java_base_web

Hola a todos, hoy os explicare que son y como programar la estructura de una lista enlazada en Java.

Una lista enlazada es una colección de objetos enlazadas entre si. Es lo que se denomina una estructura dinámica, estas pueden crecer tanto como se quiera.

No se deben confundir con los arrays, estos debemos definirles el tamaño que tendrán al crearlos.

Estas listas esta compuesta por una clase que maneja la lista y otra que contiene la información de los objetos de la lista, llamados nodos.

Para empezar, vamos a ver el código de la clase Nodo.


/**
 *
 * @author DiscoDurodeRoer
 * @param <T>
 */
public class Nodo<T> {
   
    private T dato;
    private Nodo<T> siguiente;

    /**
     * Constructor por defecto
     */
    public Nodo(){
        siguiente=null;
     }

    /**
     * Le pasamos un dato al nodo
     * @param p 
     */
    public Nodo(T p){
        siguiente=null;
        dato = p;
    }

    /**
     * Le pasamos un dato y su siguiente nodo al nodo
     * @param t Dato a insertar
     * @param siguiente Su sisguiente nodo
     */
    public Nodo(T t, Nodo<T> siguiente){
        this.siguiente=siguiente;
        dato = t;
    }
    
    public T getDato() {
        return dato;
    }

    public void setDato(T dato) {
        this.dato = dato;
    }

    public Nodo<T> getSiguiente() {
        return siguiente;
    }

    public void setSiguiente(Nodo<T> siguiente) {
        this.siguiente = siguiente;
    }
    
}

Ahora, vamos con la clase ListaEnlazada.


/**
 * @author DiscoDurodeRoer
 * @param <T>
 * Lista enlazada simple
 */
public class ListaEnlazada<T>{
   
    //Atributos
    private Nodo<T> primero;

    /**
     * Constructor por defecto
     */
    public ListaEnlazada(){
        listaVacia();
    }

    /**
     * Vacia la lista
     */
    private void listaVacia(){
        primero = null;
    }

    /**
     * Indica si la lista esta vacia o no
     * @return True = esta vacia
     */
    public boolean estaVacia(){
        return primero == null;
    }

    /**
     * Inserta un objeto al principio de la lista
     * @param t Dato insertado
     */
    public void insertarPrimero(T t){
        Nodo<T> nuevo = new Nodo<>(t);

        if (!estaVacia()){
            //Sino esta vacia, el primero actual pasa a ser
            // el siguiente de nuestro nuevo nodo
            nuevo.setSiguiente(primero);
        }
        
        //el primero apunta al nodo nuevo
        primero=nuevo;
        
    }

    /**
     * Inserta al final de la lista un objeto
     * @param t Dato insertado
     */
    public void insertarUltimo(T t){

        Nodo<T> aux = new Nodo<>(t);
        Nodo<T> rec_aux;

        if (estaVacia()) {
            insertarPrimero(t);
        }else {
            rec_aux = primero;
            
            //Buscamos el ultimo nodo
            while(rec_aux.getSiguiente() != null){
                rec_aux=rec_aux.getSiguiente();
            } 
                
            //Actualizamos el siguiente del ultimo
            rec_aux.setSiguiente(aux);
        }
    }

    /**
     * Quita el primer elemento de la lista
     */
    public void quitarPrimero(){
        Nodo<T> aux;
        if (!estaVacia()){
            aux=primero;
            primero = primero.getSiguiente();
            aux=null; //Lo marcamos para el recolector de basura
        }
    }

    /**
     * Quita el ultimo elemento de la lista
     */
    public void quitarUltimo(){
        Nodo<T> aux=primero;
        if(aux.getSiguiente()==null)
           //Aqi entra, si la lista tiene un elemento
           listaVacia();
        if(!estaVacia()) {
            aux=primero;
            
            //Buscamos el penultimo, por eso hay dos getSiguiente()
            while(aux.getSiguiente().getSiguiente() != null){
                aux=aux.getSiguiente();
            }
            
            //Marcamos el siguiente del antepenultimo como nulo, eliminando el ultimo
            aux.setSiguiente(null);
        }

    }        

    /**
     * Devuelve el último elemento de la lista
     * @return Último elemento
     */
    public T devolverUltimo(){
        T elemen = null;
        Nodo<T> aux;
        if (!estaVacia()){
            aux = primero;
            
            //Recorremos
            while(aux.getSiguiente() != null){
                aux = aux.getSiguiente();
            }
            elemen = aux.getDato();
        }
        return elemen;
    }

    /**
     * Devuelve el primer elemento de la lista
     * @return Primer elemento, null si esta vacia
     */
    public T devolverPrimero(){
        T elemen = null;
        if (!estaVacia()){
            elemen = primero.getDato();
        }
        return  elemen;
    }

    /**
     * Devuelve el número de elementos de la lista
     * @return Número de elementos
     */
    public int cuantosElementos(){
        Nodo<T> aux;
        int numElementos=0;
        aux = primero;

        //Recorremos
        while(aux != null){
            numElementos++;
            aux = aux.getSiguiente();
        }
        return numElementos;

    }
    
    /**
     * Devuelve el dato del nodo en la posicion pos
     * @param pos
     * @return dato del nodo en la posicion indicada
     */
    public T devolverDato(int pos){
        Nodo<T> aux=primero;
        int cont=0;
        T dato=null;
        
        if(pos<0 || pos>=cuantosElementos()){
            System.out.println("La posicion insertada no es correcta");
        }else{
            //recorremos
            while(aux!=null){
                if (pos == cont){
                    //Cogemos el dato
                    dato=aux.getDato();
                }
                
                aux=aux.getSiguiente();
                cont++;
                
            }
        }
        
        return dato;
        
    }
    
    /**
     * Devuelve el nodo de la posicion indicada
     * @param pos
     * @return Nodo de la posicion indicada
     */
    public Nodo<T> devolverNodo(int pos){
        Nodo<T> aux=primero;
        int cont=0;
        
        if(pos<0 || pos>=cuantosElementos()){
            System.out.println("La posicion insertada no es correcta");
        }else{
            //recorremos
            while(aux!=null){
                if (pos == cont){
                    //Devuelvo aux, con esto salimos de la función
                    return aux; 
                }
                
                //Actualizo el siguiente
                aux=aux.getSiguiente();
                cont++;
                
            }
        }
        
        return aux;
        
    }
    
    /**
     * Inserta un nuevo nodo en la posicion indicada con el su dato
     * @param pos
     * @param dato 
     */
    public void introducirDato(int pos, T dato){
        Nodo<T> aux=primero;
        Nodo<T> auxDato=null; //Debemos crear un nodo para insetar el dato
        Nodo<T> anterior=primero; //Debemos crear un nodo para insetar el dato
        
        int contador=0;
        
        if(pos<0 || pos>cuantosElementos()){
            System.out.println("La posicion insertada no es correcta");
        }else{
            
            if(pos==0){
                insertarPrimero(dato);
            }else if(pos==cuantosElementos()){
                insertarUltimo(dato);
            }else{
                //Recorremos
                while(aux!=null){
                    if (pos == contador){
                        //Creo el nodo
                        auxDato=new Nodo<>(dato, aux);
                        //El siguiente del anterior a aux es auxDato
                        anterior.setSiguiente(auxDato);
                    }
                    
                    //Actualizo anterior
                    anterior=aux;
                    
                    contador++;
                    aux=aux.getSiguiente(); //Actualizo siguiente
                }
            }
        }
        
    }
    
    /**
     * Modifica el dato indicado en el nodo de la posicion indicada
     * @param pos
     * @param dato 
     */
    public void modificarDato(int pos, T dato){
        Nodo<T> aux=primero;
        int cont=0;
        
        if(pos<0 || pos>=cuantosElementos()){
            System.out.println("La posicion insertada no es correcta");
        }else{
            //Recorremos
            while(aux!=null){
                if (pos == cont){
                    //Modificamos el dato directamente
                    aux.setDato(dato); 
                }
                cont++;
                aux=aux.getSiguiente(); //Actualizamos
            }
        }
        
    }

    /**
     * Borra un elemento de la lista
     * @param pos Posición de la lista que queremos borrar
     */
    public void borraPosicion(int pos){

        Nodo<T> aux=primero;
        Nodo<T> anterior=null;
        int contador=0;

        if(pos<0 || pos>=cuantosElementos()){
            System.out.println("La posicion insertada no es correcta");
        }else{
            while(aux!=null){
                if (pos == contador){
                    if (anterior==null){
                        primero = primero.getSiguiente();
                    }else {
                        //Actualizamos el anterior
                        anterior.setSiguiente(aux.getSiguiente());
                    }
                    aux=null;
                }else{
                    anterior=aux;
                    aux=aux.getSiguiente();
                    contador++;
                }
            }
        }
    }

    /**
     * Devuelve el primer el elemento y lo borra de la lista
     * @return Primer elemento
     */
    public T devolverYBorrarPrimero(){

        T dato=devolverPrimero();
        quitarPrimero();
        return dato;
    }

    /**
     * Indica la posición del primer dato que se encuentre
     * @param t dato buscado
     * @return Posición del dato buscado, -1 si no se encuentra o esta vacia
     */
    public int indexOf (T t){

       Nodo<T> aux=primero;
       if (estaVacia()){
            return -1;
       }else{
           int contador=0;
           boolean encontrado=false;
           
            //recorremos, cuando encontrado=true, sale del bucle
           while(aux!=null && !encontrado){
               if(t.equals(aux.getDato())){
                   //Cambiamos a true
                   encontrado=true;
               }else{
                    contador++;
                    //actualizamos
                    aux=aux.getSiguiente(); 
               }
           }
           if(encontrado){
                return contador;
           }else{
                //no se ha encontrado
                return -1;
           }
       }
    }
    
    /**
     * Indica la posición del primer dato desde la posicion indicada
     * @param t dato buscado
     * @param pos
     * @return Posición del dato buscado, -1 si no se encuentra o esta vacia
     */
    public int indexOf (T t, int pos){

       Nodo<T> aux;
       if (estaVacia()){
            return -1;
       }else{
           int contador=pos;
           boolean encontrado=false;
           
           //Empezamos desde el nodo correspondiente
           aux=devolverNodo(pos);
           
           //recorremos, cuando encontrado=true, sale del bucle
            while(aux!=null && !encontrado){
               if(t.equals(aux.getDato())){
                   //Cambiamos a true
                   encontrado=true;
               }else{
                    contador++;
                    //Actualizamos
                    aux=aux.getSiguiente();
               }
            }
            if(encontrado){
                return contador;
            }else{
                return -1;
            }
       }
    }

    /**
     * Indica si un dato existe en la lista
     * @param t Dato a comprobar
     * @return Si el dato existe, devuelve true
     */
    public boolean datoExistente(T t){

        boolean existe=false;

        Nodo<T> aux=primero;

        while(aux!=null && !existe){

            if(aux.getDato().equals(t)){
                existe=true;
            }
            
            //Actualizamos
            aux=aux.getSiguiente();
        }

        return existe;
    }
    
    /**
     * Muestra el contenido de la lista
     */
    public void mostrar(){
        System.out.println("Contenido de la lista");
        System.out.println("---------------------");
        
        Nodo<T> aux=primero;
        
        while(aux!=null){
            System.out.println(aux.getDato());//mostramos el dato
            aux=aux.getSiguiente();
        }
        
    }
    
    /**
     * Devuelve el contenido de la lista en un String
     * @return contenido de la lista
     */
    @Override
    public String toString(){
        
        String contenido="";
        Nodo<T> aux=primero;
        
        while(aux!=null){
            contenido+=aux.getDato()+"\n"; //guardamos el dato
            aux=aux.getSiguiente();
        }
        
        return contenido;
    }

}

Os dejo también un pequeño fichero de prueba para que veáis como funciona.


/**
 * Muestra de funcionamiento de la lista enlazada
 * @author DiscoDurodeRoer
 */
public class ListaEnlazadaSimple {

    public static void main(String[] args) {
        
        //Creo la lista enlazada de numeros
        //Puede ser de String, double, Objetos, etc.
        ListaEnlazada<Integer> lista=new ListaEnlazada<>();
        
        System.out.println("Insercion de numeros del 0 al 9 en forma de cola");
        for(int i=0;i<10;i++){
            lista.insertarUltimo(i);
        }
        
        //Mostramos la lista
        lista.mostrar(); 
        
        System.out.println("");
        
        System.out.println("Numero de elementos: " + lista.cuantosElementos());
        System.out.println("");
        
        System.out.println("Eliminación del dato que esta en la posicion 3");
        lista.borraPosicion(3); //Elimina el el dato 3
        
        lista.mostrar();
        
        System.out.println("Numero de elementos: " + lista.cuantosElementos());
        System.out.println("");
        
        System.out.println("Insercion del dato 2 en la posicion 5");
        lista.introducirDato(5, 2);
        
        lista.mostrar();
        
        System.out.println("Numero de elementos: " + lista.cuantosElementos());
        System.out.println("");
        
        System.out.println("Modificamos el dato de la posicion 5 por un 3");
        lista.modificarDato(5, 3);
        
        lista.mostrar();
        
        System.out.println("Numero de elementos: " + lista.cuantosElementos());
        System.out.println("");
        
        System.out.println("Inserto en la posicion 0");
        lista.introducirDato(0, 10);
        
        lista.mostrar();
        System.out.println("");
        
        System.out.println("Inserto en la ultima posicion");
        //Equivalente a insertarUltimo
        lista.introducirDato(lista.cuantosElementos(), 11);
     
        lista.mostrar();
        System.out.println("");
        
        System.out.println("Posicion del dato 5: "+lista.indexOf(5));
        System.out.println("Posicion del dato 5 desde la posicion 7: "+lista.indexOf(5, 7));
        
        System.out.println("");
        
        System.out.println("¿Existe el dato 10 en la lista? "+lista.datoExistente(10));
        System.out.println("¿Existe el dato 20 en la lista? "+lista.datoExistente(20));
    }
    
}

Os dejo aquí para que podáis descargar e importar el programa en vuestros netbeans o eclipses. Para eclipse copiar los .java.

[wpdm_package id=’8365′]

Como vemos, el único atributo de la lista es primero que es el primer elemento, es decir, su referencia, este con su atributo siguiente apuntara al siguiente elemento cuando se añade un nuevo elemento. Puede tener también otros atributos, como ultimo que indicara el ultimo elemento.

Esta lista enlazada puede usarse para cualquier tipo de dato, gracias a los genéricos, fíjate en el fichero de prueba de como se debe iniciar. Una vez hecho, todos los datos son de ese tipo dentro de un nodo

Veamos un pequeño esquema sobre como es una lista enlazada.

Cuando la creamos tendría este aspecto.

listaEnlazada1

Como vemos, no tiene nada, ya que no hemos insertado nada. Cuando insertamos un dato, internamente se crea un nodo, si la lista esta vacía sera el primero, sino lo esta, normalmente, va al final pero según como quieras insertar.

listaEnlazada2

Insertamos otro elemento al final.

listaEnlazada3

Cuando insertamos datos (en este caso 2 elementos), primero apunta al primer nodo y este al segundo. En el último nodo,  el atributo siguiente es null, ya que no hay mas nodos.

También podemos borrar, si borramos el primero, el nodo2 sera el nuevo primero.

listaEnlazada4

Y así consecutivamente, os recomiendo ejecutar el código de prueba e intentar comprender el código.

Para recorrer una lista enlazada que tenga varios nodos, siempre empezamos por el nodo primero y usando el método getSiguiente(), avanzamos por cada uno de los nodos. El código sería así:


Nodo<T> aux=primero; //aux apunta al primero
while(aux!=null){
     //Lo que quieras
     aux=aux.getSiguiente();
}

Gráficamente, se haría así para esta lista enlazada:

listaEnlazada3Aux apunta al primer nodo.

recorridoListaEnlazada1
Después, aux apunta al segundo nodo.
recorridoListaEnlazada2
Por ultimo, aux vale null pero como en la comprobación del while hemos puesto que si aux!=null continue, como es null, se para.

recorridoListaEnlazada3

Espero que os sea de ayuda. Si teneos dudas, preguntad. Estamos para ayudarte.

Etiquetas

4 comments

  1. mil gracias por tu buen aporte

  2. en relación a este apartado, teniendo la lista con números aleatorios

    como puedo mostrar en que posición entra cada uno de los datos?

  3. […] de empezar, os recomiendo usar la lista enlazada que hemos proporcionado en este blog, pincha aquí para ir al […]

  4. Gracias por la expliación, me ayudó bastante para mi clase de estructura de datos ^.^

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *