¿Que es una lista ligada simple?

Muchos compañeros de la universidad me han preguntado sobre cómo podrían crear una lista ligada simple en Java porque LinkedList no cumple con lo que necesitan o simplemente desean aprender a crearla ellos mismos. Es por eso que he decidido crear este artículo con el fin de ayudarles tanto a ellos como a ustedes que leen este artículo actualmente y repasar el tema.

Primero que todo recordemos que es una Lista Simplemente Ligada. Es una estructura de datos, muy parecida a un arreglo pero que no se accede mediante el uso de un índice sino mediante el uso de punteros. También es un tipo de estructura dinámica, ya que esta puede ir cambiando su tamaño durante el tiempo de ejecución y no es necesario crearla con un tamaño fijo como lo hacíamos anteriormente con los arreglos.

Figura 1. Ejemplo de liga simplemente ligada

Como puedes ver en la Figura 1, una lista ligada se compone de nodos y estos nodos tienen un número de atributos que va de acuerdo a las necesidades de la lista. Pero hay un atributo que siempre es necesario y es el que yo en este caso llamé siguiente, este atributo es el puntero que contendrá la dirección de memoria del siguiente nodo.

Las listas ligadas simples se recorren hacia «adelante», nodo por nodo, y el último nodo tiene que apuntar hacia el valor NULL para entender cuándo es el fin de la lista.

Ahora sí, vamos a lo que importa. Como crear una lista de estas en Java (en Objective-C es muy parecido, por no decir idéntico a C/C++, así que esta vez no habrá entrada sobre Obj-C):

• Creación de la clase Nodo: Vamos a crear nuestra clase nodo, esta nos dará el esquema que tendrá cada nodo de nuestra Lista Simplemente Ligada.

public class Nodo {
    private int campoA;
    private Nodo siguiente;

    public Nodo(int campoA) {
        this.campoA = campoA;
        siguiente = null;
    }

    public int getValor() {
        return campoA;
    }

    public void setValor(int campoA) {
        this.campoA = campoA;
    }

    public Nodo getSiguiente() {
        return siguiente;
    }

    public void setSiguiente(Nodo siguiente) {
        this.siguiente = siguiente
    }
}

• Operaciones básicas:
  • Creación de la lista:

public static void main(String args[]) {
    Scanner in = new Scanner(System.in);
    Nodo nuevo, primero, ultimo;
    boolean respuesta = true;
    int numero;
    String temporal;

    while (respuesta) {
        System.out.print("Ingresa el valor del nodo: ");
        numero = in.nextInt();
        nuevo = new Nodo(numero);
        if (primero == null) {
            primero = nuevo;
        } else {
            ultimo.setSiguiente(nuevo);
        }
        ultimo = nuevo;
        System.out.println("Agregar un nuevo nodo? (S/N)");
        temporal = in.next().toLowerCase();
        respuesta = temporal.equals("s");
    }
}

• Recorrer la lista:

public static void recorrerLista(Nodo primero) {
    Nodo auxiliar = primero;

    while(auxiliar != null) {
        System.out.println("Dato: " + auxiliar.getValor());
        auxiliar = auxiliar.getSiguiente();
    }
 }

Creo que el código se explica por sí solo. Si tienen alguna duda no olviden en contactarme vía Twitter o dejando un comentario.

Aquí pondré las clases Principal y Nodo para que las descarguen y prueben que sí funciona: Descargar fuentes