Listas enlazadas y listas circulares

Una lista es una colección, originalmente vacía, de elementos u objetos de cualquier tipo no necesariamente consecutivos en memoria, que durante la ejecución del programa pueden crecer o decrecer elemento a elemento según las necesidades previstas en el mismo.

Una lista está formada por un número variable de datos (elementos) de un mismo tipo, ordenados según una secuencia lineal. Cada elemento, salvo el primero, tiene un predecesor en la lista. Todos los elementos, salvo el último, tienen un sucesor.

Listas enlazadas

Piensa

Si los elementos no están consecutivos en memoria ¿cómo pasamos desde un elemento al siguiente cuando recorremos la lista? La respuesta es que cada elemento debe almacenar información de dónde está el siguiente elemento o el anterior, o bien ambos.

Podemos definir una lista como una estructura de datos formada por registros de, al menos, dos campos, en que uno de ellos contiene información que permite localizar al siguiente registro en la lista según una secuencia dada.

En función de la información que cada elemento de la lista almacene respecto a la localización de sus antecesores y/o predecesores, las listas pueden clasificarse en: listas lineales simplemente enlazadas, listas lineales doblemente enlazadas, listas circulares simplemente enlazadas, y listas circulares doblemente enlazadas.

Listas lineales simplemente enlazadas

Una lista lineal simplemente enlazada es una colección de objetos (elementos de la lista), cada uno de los cuales contiene datos o una referencia a los datos, y una referencia al siguiente objeto en la colección (elemento de la lista).

class Persona {
    //atributos
    String apellido;
    Persona siguiente; //referencia al siguiente elemento
    public Persona(){ // constructor por defecto
    }
}

Listas lineales doblemente enlazadas

En algunas aplicaciones puede ser deseable recorrer eficientemente una lista, tanto hacia adelante como hacia atrás. O, dado un elemento, podría desearse determinar con rapidez el siguiente y el anterior. En tales situaciones, quizá se quisiera poner en cada nodo de una lista un puntero al siguiente nodo y otro al anterior.

class Persona {
    //atributos
    String apellido;
    Persona siguiente; //referencia al siguiente elemento
    Persona anterior; //referencia al anterior elemento
    public Persona(){ // constructor por defecto
    }
}

Listas circulares

Una lista circular enlazada es una lista en la que el último elemento apunta al primero en lugar de apuntar al vacío o NULL.

Listas circulares simplemente enlazadas

En este tipo de listas es posible acceder a cualquier elemento de la lista desde cualquier punto dado desplazándonos en un único sentido. Una representación gráfica sería la siguiente

class ListaCircular {
    private Persona cabeza; // Referencia al primer nodo
    private Persona cola;   // Referencia al último nodo

    // Constructor por defecto
    public ListaCircular() {
        this.cabeza = null;
        this.cola = null;
    }

    // Método para agregar un nodo al final de la lista
    public void agregar(String apellido) {}

    // Método para recorrer e imprimir la lista
    public void mostrar() {}
}

Listas circulares doblemente enlazadas

Una lista circular doblemente enlazada es una combinación de las listas circulares y de las listas doblemente enlazadas. Su principal ventaja es que se permite el desplazamiento en cualquier sentido a través de la misma.

class ListaCircularDoble {
    private Persona cabeza; // Referencia al primer nodo
    private Persona cola;   // Referencia al último nodo

    // Constructor por defecto
    public ListaCircularDoble() {
        this.cabeza = null;
        this.cola = null;
    }

    // Método para agregar un nodo al final de la lista
    public void agregar(String apellido) {}

    // Método para recorrer e imprimir la lista hacia adelante
    public void mostrarAdelante() {}

    // Método para recorrer e imprimir la lista hacia atrás
    public void mostrarAtras() {}
}