Las listas son estructuras de datos lineales (como se vio en la clasificación de la unidad de introducción) que permiten almacenar un conjunto ordenado de elementos y de esa manera darles un mejor tratamiento. Ejemplos de usos de las listas:

1. Lista de números para realizar cálculos estadísticos.
2. Lista de nombres de usuarios para un sistema de registro.
3. Lista de productos en un carrito de compras.

Creación de una lista indexada en java

Como puede verse en el siguiente código, tenemos dos formas de crear listas indexadas en java, una es utilizando la interfaz List y la otra es usando la clase ArrayList .

                    
import java.util.ArrayList;
import java.util.List;

public class Lista{
    public static void main(String[] args) {
        
        List < String > nombresA = new ArrayList<>();        
        ArrayList < String > nombresB = new ArrayList<>();        

    }    
}                    
                

¿Cual es la diferencia?

1. List nombresA = new ArrayList<>();
   1. Declaración con interfaz: Aquí se declara una variable nombresA de tipo List. List es una interfaz que define un conjunto de métodos para trabajar con listas, como agregar, eliminar, buscar elementos, etc.
   2. Instanciación con clase concreta: Sin embargo, se instancia un objeto de la clase ArrayList, que es una implementación concreta de la interfaz List. Esta clase proporciona una implementación eficiente de las operaciones de una lista.
2. List nombresB = new ArrayList<>();
   1. Declaración y creación directa: Aquí se declara una variable nombresB y se instancia directamente un objeto de la clase ArrayList.
   2. Menos flexible: Al especificar directamente ArrayList, se pierde cierta flexibilidad. Si en el futuro quisieras cambiar la implementación a otra clase que implemente List (por ejemplo, LinkedList), tendrías que modificar todas las referencias a ArrayList en tu código.

Dicho lo anterior, se recomienda la primera opción, ya que al declarar la variable como List, te estás acoplando al contrato definido por la interfaz List. Esto hace tu código más flexible y mantenible. Si en el futuro necesitas cambiar la implementación a otra clase que implemente List, solo tendrías que cambiar la línea de instanciación, y el resto de tu código seguiría funcionando sin cambios. Y por esa razón de ahora en adelande usaremos esa recomendación.

3.3.1 Operaciones básicas de listas

1. add(E e): Agrega un elemento al final de la lista.
2. add(int index, E element): Inserta un elemento en una posición específica.
3. get(int index): Devuelve el elemento en la posición indicada.
4. size(): Devuelve el número de elementos en la lista.
5. set(int index, E element): Reemplaza el elemento en la posición indicada.
6. remove(int index): Elimina el elemento en la posición indicada.
7. remove(Object o): Elimina la primera ocurrencia del elemento especificado.
8. contains(Object o): Devuelve true si la lista contiene el elemento especificado.
9. clear(): Elimina todos los elementos de la lista.
10. isEmpty(): Devuelve true si la lista está vacía.
11. indexOf(Object o): Devuelve el índice de la primera ocurrencia del elemento especificado, o -1 si no se encuentra.
12. lastIndexOf(Object o): Devuelve el índice de la última ocurrencia del elemento especificado, o -1 si no se encuentra.
13. Para revisar todos los métodos visita la docmuentación de la clase aqui .

Ejemplo 1: implementación de una lista en Java .

                    
import java.util.ArrayList;
import java.util.List;

public class Lista{
    public static void main(String[] args) {
        
        List < String > tripulacion = new ArrayList<>();        
        
        //Agregamos elementos con add()
        tripulacion.add("Zoro");
        tripulacion.add("Robin");
       //Contenido de la lista: [Zoro, Robin]
       
       //Agregamos un elemento en la posición 0
       tripulacion.add(0, "Luffy");
       System.out.println("Integrantes de los mugiwaras: "+tripulacion);
       // Indices                  0      1     2 
       //Contenido de la lista: [Luffy, Zoro, Robin]
        
       //Si queremos imprimir/obtener a Robin
       System.out.println(tripulacion.get(2));

       //Si quremos ver en que posición se encuentra Nami
       int indice = tripulacion.indexOf("Nami");
       System.out.println("Posición de Nami: "+ indice);
       // Como la tripulante nami no se encuentra, la variable indice vale -1

    }    
}                    
                

Ejemplo 2: implementación de una lista Personalizada

Para poder implementar una lista personalizada, primero debemos definir la clase con la estructura deseada.

En la siguiente clase llamada Personaje, se especifican 3 atributos, nombre, ocupacion y cargo, significa que si se crea una lista de tipo Personaje (es decir, que almacene objetos de tipo Personaje), cada indice de la lista podra almacenar un conjunto de datos y no solo uno, como en el ejemplo anterior.

También se especifica un constructor tradicional, un método para obtener información de los atributos y otro método para actualizar la información.

                    
public class Personaje {

String nombre;
String ocupacion;
String cargo;

public Personaje(String n, String o, String c){
    nombre = n;
    ocupacion = o;
    cargo = c;
}

public String getPersonaje(){
    return nombre+" "+ocupacion+" "+cargo;
}

public void setPersonaje(String n, String o, String c){
    nombre = n;
    ocupacion = o;
    cargo = c;
}
}
                    
                

El siguiente código muestra la implementación de la clase Personaje definida anteriormente. La implementación se realiza a través de la creación de dos listas, piratas y marines, se les ingresa información y para el caso de piratas se hace uso del método getPersonaje(), para poder ver la información.

                    
import java.util.ArrayList;
import java.util.List;

public class Lista {

    public static void main(String[] args) {
        
        List< Personaje > piratas = new ArrayList<>();

        //Forma 1 de agregar un elmento a la lista personalizada
        
        Personaje nuevoPersonaje = new Personaje("Luffy", "Pirata", "Capital");
        piratas.add(nuevoPersonaje);
        nuevoPersonaje = new Personaje("Nami", "Pirata", "Navegante");
        piratas.add(nuevoPersonaje);
        
        //Forma 2 de agregar un elemento a la lista personalizada
        piratas.add(new Personaje("Boa Hancock", "Pirata", "capitana"));
        piratas.add(new Personaje("Sanji", "Pirata", "Cocinero"));

        List< Personaje > marines = new ArrayList<>();
        marines.add(new Personaje("Garp", "Marin","Vicealmirante"));
        marines.add(new Personaje("Kizaru", "Marin","Almirante"));
        marines.add(new Personaje("Akainu", "Marin", "Almirante de flota"));

        //Como es un lista de objetos, no se puede acceder directamente a la
        //información pasamdo como argumento la lista al mótodo print
        //Se debe realizar a travez de los métodos

        //acceder a Kizaru
        System.out.println(marines.get(1).getPersonaje());

        //Acceder a la lista completa de piratas
        for (int i = 0; i < piratas.size(); i++) {
            System.out.println(piratas.get(i).getPersonaje());
        }

    }
}                    
                

3.1.2 Listas enlazadas y tipos

Una lista enlazada es una estructura de datos lineal que almacena una colección de elementos llamados nodos (Los cuales se crean a partir de la clase Nodo, como se verá mas adelante). A diferencia de los arrays, que tienen un tamaño fijo y los elementos se almacenan en posiciones de memoria contiguas, en una lista enlazada cada nodo contiene, además del dato, un puntero (o referencia, la cual simplemente se refiere a la dirección en memoria de la localización del elemento) al siguiente nodo.

Imagina una cadena de vagones de un tren. Cada vagón representa un nodo en la lista. Cada vagón tiene un enganche que lo conecta al siguiente vagón. En una lista enlazada, el primer vagón es el inicio de la lista, y el último vagón no tiene ningún vagón enganchado a él.

Clasificación de las listas enlazadas

1. Lista simplemente enlazada (LSE). Cada nodo (elemento) contiene un único enlace que lo conecta al nodo siguiente o nodo sucesor. La lista es eficiente en recorridos directos (“adelante”).
   

   

   Figura 3.2 Representación de una LSE

2. Lista doblemente enlazada (LDE). Cada nodo contiene dos enlaces, uno a su nodo predecesor y otro a su nodo sucesor. La lista es eficiente tanto en recorrido directo (“adelante”) como en recorrido inverso (“atrás”).

   

   Figura 3.2 Representación de una LDE

3. Lista circular simplemente enlazada (LCSE). Es aquella en la que el último elemento (cola) se enlaza al primer elemento (inicio) de tal modo que la lista puede ser recorrida de modo circular (“en anillo”).

   

   Figura 3.2 Representación de una LCSE

4. Lista circular doblemente enlazada (LCDE). Una lista doblemente enlazada en la que el último elemento se enlaza al primer elemento y viceversa. Esta lista se puede recorrer de modo circular (“en anillo”) tanto en dirección directa (“adelante”) como inversa (“atrás”).

   

   Figura 3.2 Representación de una LCDE

Codificación de una lista simplemente enlazada en Java con TDAs

Para implementar una lista simplemente enlazada (De ahora en adelante LSE) necesitaremos 3 clases, las cuales de describen a continuación.

1. Nodo: Esta clase se usa para crear cada uno de los elementos que componen la lista. Su especificación determina las características de la información que se pretende agregar.
2. Lista: Esta clase contiene los métodos para operar la lista, por ejemplo: agregar, eliminar, modificar, vaciar, buscar, etc.
3. Main: Esta clase es la que contiene el método main o es cualquier otra clase desde la cual se pretenda utilizar la lista, es decir, su creación y manipulación.

Codificación de la clase Nodo

En el siguiente código se muestra la estrucura de la clase correspondiente al nodo (elemento que compone a una lista enlazada usando TDAs). El código muestra dos atributos, dato y enlace.

1. dato corresponde a la información que contendrá el nodo, y es la parte a especificar si es que se pretende espeficicar la iformación a se pretende manejar.
2. elace es el elemento que almacena la dirección en memoria del siguiente elemento. El ultimo nodo de la lista tendrá el valor "null"

                    
public class Nodo{
    int dato;
    Nodo enlace;

    public Nodo(int dato){
        this.dato = dato;
        this.enlace = null;
    }
}                    
                

Si quisiéramos almacenar datos personales en cada uno de los nodos de una LSE, la configuración del nodo quedaría de la siguiente manera.

                    
public class Nodo{
    String nombre;
    int edad;
    String direccion;
    String telefono;
    Nodo enlace;

    public Nodo(String nombre, int edad, String direccion, String telefono){
        this.nombre = nombre;
        this.edad = edad;
        this.direccion = direccion;
        this.telefono = telefono;
        this.enlace = null;
    }
}                    
                

Al ser un TDA, la estructura del nodo se puede personalisar segun las necesidades (como ya se mencionó anteriormente), pero de ahora en adelante se manejará el primer diseño, es decir, con los atributos dato y enlace.

Codificación de la clase Lista

En el siguiente código se muestra la estrucura de la clase Lista, en la cual podreos encontrar los métodos para manipular el contenido de una lista.

                    
public class Lista {
    Nodo inicio;

    public Lista(){
        this.inicio = null;
    }

    public void addInicio(int dato){
        Nodo nuevo = new Nodo(dato);
        nuevo.enlace = inicio;
        this.inicio = nuevo;
    }

    public void addFinal(int dato){
        Nodo nuevo = new Nodo(dato);
        Nodo p = inicio;
        while (p != null) {
            if (p.enlace == null) {
                p.enlace = nuevo;
                break;
            }else{
                p = p.enlace;            
            }
        }
    }
    public void imprimir(){
        Nodo p = inicio;
        while (p != null) {
            System.out.println("Dato:"+p.dato);
            System.out.println("Enla:"+p.enlace);
            p = p.enlace;            
        }
    }    
}
                    
                

En el tema 3.3.1 se mencionaron los diferentes métodos o acciones que se pueden realizar sobre una lista, para el caso de las listas enlazadas a ser realizada a travez de TDAs, los metodos deben codificarse manualmente. En el código anterior se muestran algunos de éstos métodos, si alguno hiciera falta, el lector puede agregar cualquier método para la acción que haga falta.

Implementación de la clase Lista

En el siguiente código se crea inicialmente una lista vacía, despues a travez de los métodos addInicio() y addFinal() se realizan inserciones en la lista. y por último, se muestra el contenido de la lista al ejecutar el método imprimir().

                    
public class ListaE {
    public static void main(String[] args) {
        
        Lista lista = new Lista();//Crea una lista vacía
        
        lista.addInicio(5); //La lista contiene [5]
        lista.addInicio(8); //La lista contiene [8, 5]
        lista.addInicio(2); //La lista contiene [2, 8, 5]
        lista.addFinal(4); // La lista contiene [2, 8, 5, 4]
        
        lista.imprimir();        
    }    
}