Estructura de datos: computación práctica con Java

Introducción

Imagina que estás gestionando una gran cantidad de datos en tu programa. Seguramente buscarías la forma más beneficiosa y eficiente de hacerlo. Pero, ¿cómo elegir la solución más viable?

Las estructuras de datos son la manera de organizar y almacenar datos. Existen para que ciertos datos se puedan utilizar de manera eficiente, lo que permite una mejor gestión.

El objetivo de este artículo es comprender cómo funcionan las estructuras de datos bajo la superficie, discutir las ventajas y desventajas de cada una y ver, en diferentes situaciones, cuál es el tiempo de ejecución y el rendimiento de estas estructuras.

Este conocimiento es importante para poder optar por una de ellas en nuestro programa, es decir, eligiendo la solución más viable. Para ello, veremos cómo se aplican en la práctica utilizando un proyecto en Java como base.

Almacenamiento Secuencial y Vectores

Con [Eclipse](Aumentando tu productividad con el eclipse | Alura Cursos Online) abierto, comenzaremos nuestro primer proyecto de estructuras de datos. Por ejemplo, trabajaremos con una universidad donde necesitamos almacenar y recuperar datos de los alumnos. Es decir, los agregaremos al final o en medio de una lista, los eliminaremos, los encontraremos por su número, y así sucesivamente.

El primer paso en este proyecto es modelar la clase "Alumno". Para ello, creamos un nuevo proyecto y dentro de él, la clase Alumno, donde guardaremos el nombre del alumno, que recibiremos en el propio constructor de la clase.

Luego, crearemos el getter e implementaremos los métodos "equals" y "toString", que serán muy importantes. "equals" es el método utilizado para comparar objetos, en este caso, alumnos. Realizaremos casting (una conversión) del objeto a alumno. El método "toString" devuelve el nombre del alumno y otros atributos si tiene en clase.

package ed;

public class Alumno {

    private String nombre;

    public Alumno(String nombre) {
        this.nombre = nombre;
    }

    public String getNombre() {
         return nombre;
     }

@Override
public boolean equals(Object obj) {
    Alumno otro = (Alumno) obj;
    return otro.getNombre().equals(this.nombre);
}

@Override
public String toString() {
    return nombre;
 }
}

Una vez hecho esto, la primera estructura de datos que veremos es el Almacenamiento Secuencial. La idea de esta estructura es almacenar un alumno detrás del otro. Tendremos un conjunto de espacios llamado arreglo (Array), donde el primer alumno está en el primer espacio, el segundo alumno en el segundo espacio, y así sucesivamente.

Teniendo esto en cuenta, crearemos una nueva clase llamada "Vector" en la que debemos implementar la estructura de almacenamiento secuencial. También debemos agregar un array con 100 posiciones e implementar los métodos de comportamiento de este array:

package ed;

public class Vector {
 private Alumno[] alumnos = new Alumno[100];

    public void agrega(Alumno alumno) {
        //recibe a un alumno
    }

    public Alumno obten(int posicion) {
        //recibe una posición y devuelve al alumno
        return null;
    }

    public void elimina(int posicion) {
        //elimina por la posición
    }

    public boolean contiene(Alumno alumno) {
        //averigua si el estudiante está en la lista
        return false;
    }

    public int tamano() {
        //devuelve la cantidad de alumnos
        return 0;
    }

    public String toString() {
        //facilitará en la impresión
        return Arrays.toString(alumnos);
    }

}

Los return's ya se han insertado para que podamos compilar el código. Antes de implementar los comportamientos, escribiremos el método main (principal) para probar el Vector, incluso antes de que el código exista. Para ello, crearemos la clase "VectorPrueba":

package ed;

public class VectorPrueba {

    public static void main(String[] args) {

    }
}

Método agrega

El primer método que probaremos es "agrega", que agrega un alumno, utilizando dos alumnos:

public static void main(String[] args) {
        Alumno a1 = new Alumno("Luis");
        Alumno a2 = new Alumno("Jose");

        Vector lista = new Vector();

        lista.agrega(a1);
        lista.agrega(a2);

        System.out.println(lista);
    }

Al ejecutar el programa, obtendremos:

[null, null, null, null, null...]

Habrá 100 null's (valores nulos), por lo que el método "agrega" está funcionando. Entonces, ¿por qué no lo implementamos? La idea es recorrer todo el array y, tan pronto como encontremos una posición nula, almacenar al alumno actual en ella:

public void agrega(Alumno alumno) {
        for(int i = 0; i < alumnos.length; i++) {
            if(alumnos[i] == null) {
                alumnos[i] = alumno;
                break;
            }
        }
    }

Si ejecutamos la prueba nuevamente, obtendremos:

[Luis, Jose, null, null, null...]

Ahora los dos alumnos se han agregado al array. Pero tengamos en cuenta que el algoritmo que implementamos no es muy eficiente, ya que cuanto mayor sea el número de alumnos agregados al array, más tiempo llevará el método, ya que el bucle recorrerá varias veces las posiciones ya ocupadas. Intentaremos mejorarlo para que no dependa de la cantidad de elementos en la lista. Para ello, utilizaremos el siguiente código:

private Alumno[] alumnos = new Alumno[100];
    private int totalDeAlumnos = 0;

    public void agrega(Alumno alumno) {
        this.alumnos[totalDeAlumnos] = alumno;
        totalDeAlumnos++;
    }

Método tamaño

El siguiente método que probaremos es "tamaño":

public int tamano() {
        return totalDeAlumnos;
}

Agreguemos lo siguiente al método main:

 System.out.println(lista.tamano());
 lista.agrega(a1);
 System.out.println(lista.tamano());
 lista.agrega(a2);
 System.out.println(lista.tamano());

Devolverá:

0
1
2
[Luis, Jose, null, null, null...]

En cada iteración, devuelve el tamaño de la lista de alumnos que se ha completado.

Método contiene

Implementemos el método "contiene". Queremos "preguntar" a la lista si un alumno específico está presente en ella.

public boolean contiene(Alumno alumno) {

        for(int i = 0; i < totalDeAlumnos; i++) {
            if(alumno.equals(alumnos[i])) {
                return true;
            }
        }
        return false;
    }

Para probar "true", agregamos lo siguiente en el método principal:

System.out.println(lista.contiene(a1));

Al ejecutarlo:

0
1
2
[Luis, Jose, null, null, null...]
true

Para probar "false", creamos una alumna que no se agregará a la lista:

Alumno a3 = new Alumno("Maria");
System.out.println(lista.contiene(a3));

Al ejecutarlo:

0
1
2
[Luis, Jose, null, null, null...]
true
false

Método obten

Para implementar este método, que nos devuelve el nombre del alumno en la posición que especificamos, haremos lo siguiente:

public Alumno obten(int posicion) {
        return alumnos[posicion];
}

Recuerda que nuestro array tiene 100 posiciones. ¿Qué sucedería si preguntáramos por el alumno en la posición 200? Lo probaremos en el método main:

Alumno x = lista.obten(1);
System.out.println(x);

El programa devuelve "Jose", que se encuentra en la posición número 1. Si seleccionamos la posición 200, el programa generará un error con el mensaje "ArrayIndexOutOfBounds", es decir, estamos intentando acceder a una posición del array que no existe.

Comencemos a pensar en la validación de los datos que pasamos al programa. Queremos que devuelva, por ejemplo, un mensaje más amigable en lugar de un error. Crearemos un método auxiliar que determine si una determinada posición está ocupada:

private boolean posicionOcupada(int posicion) {
    return posicion >= 0 && posicion < totalDeAlumnos;
}

En el método "obten":

 public Alumno obten(int posicion) {

        if(!posicionOcupada(posicion)) {
            throw new IllegalArgumentException("posición inválida");
        }

        return alumnos[posicion];
 }

Esta parte es muy importante, ya que es nuestra responsabilidad como implementadores de la estructura garantizar que se manejen los datos mal utilizados por el usuario.

Otro método agrega

Implementaremos otro método que, a diferencia de "agrega", que ya hemos visto, inserta un alumno en cualquier posición del arreglo (array):

public void agrega(int posicion, Alumno alumno) {

}

Pensemos en cómo construir este método. Imaginemos, en nuestro array de 100, que las primeras diez posiciones ya están ocupadas. Queremos insertar un alumno en la tercera posición, como se muestra en la siguiente imagen:

Para ello, moveremos a todos los alumnos desde la tercera posición hacia adelante a la derecha y colocaremos al nuevo alumno en el hueco que quede, como se puede observar en la siguiente imagen:

Entonces, hacemos lo siguiente:

public void agrega(int posicion, Alumno alumno) {

    for(int i = totalDeAlumnos - 1; i >= posicion; i-=1) {
        alumnos[i+1] = alumnos[i];
    }
    alumnos[posicion] = alumno;
    totalDeAlumnos++;
}

Probemos añadir una alumna:

lista.agrega(1, a3);
System.out.println(lista);

El programa devolverá:

[Luis, Maria, Jose, null, null...]

La alumna Maria se ha desplazado a la posición 1, empujando a todos los demás hacia la derecha. Sin embargo, como en el caso de "obten", necesitamos una validación:

private boolean posicionValida(int posicion) {
    return posicion >= 0 && posicion <= totalDeAlumnos;
}

En el método:

public void agrega(int posicion, Alumno alumno) {

    if(!posicionValida(posicion)) {
        throw new IllegalArgumentException("posición inválida");
    }
    for(int i = totalDeAlumnos - 1; i >= posicion; i-=1) {
        alumnos[i+1] = alumnos[i];
    }
    alumnos[posicion] = alumno;
    totalDeAlumnos++;
}

Método elimina

Nuestro próximo desafío es el método "elimina", que será similar a "agrega", pero pensando en sentido contrario: eliminamos al alumno de la posición n y desplazamos hacia la izquierda a todos los que estaban después de él:

public void elimina(int posicion) {
    for(int i = posicion; i < this.totalDeAlumnos; i++) {
        this.alumnos[i] = this.alumnos[i+1];
    }
    totalDeAlumnos--;
}

Probando:

lista.elimina(1);
System.out.println(lista);

Antes estaba así:

[Luis, Maria, Jose, null, null...]

Y ahora:

[Luis, Jose, null, null, null...]

Redimensionando el array

Ya hemos implementado los métodos principales de nuestro Vector. Sin embargo, ten en cuenta que el tamaño del arreglo (array) es constante y vale 100. Queremos que se pueda cambiar según la cantidad de estudiantes.

En Java no podemos cambiar el tamaño de un array, por lo que tendremos que crear uno nuevo más grande y copiar todo lo que está en el antiguo a este nuevo. Crearemos el método "garantizaEspacio":

private void garantizaEspacio() {
    if(totalDeAlumnos == alumnos.length) {
        Alumno[] nuevoArray = new Alumno[alumnos.length*2];
        for(int i = 0; i < alumnos.length; i++) {
            nuevoArray[i] = alumnos[i];
        }
        this.alumnos= nuevoArray;
    }
}

Falta ahora invocar en los dos métodos "agrega":

public void agrega(Alumno alumno) {
    this.garantizaEspacio();
    ...
}

public void agrega(int posicion, Alumno alumno) {
    this.garantizaEspacio();
    ...
}

Ahora, si añadimos más elementos de los que caben en el tamaño del array anterior, se redimensionará en un nuevo array.

Para probar esta implementación, crearemos un bucle en el método main que agregará 300 alumnos:

for(int i = 0; i < 300; i++) {
    Alumno y = new Alumno("Alvaro" + i);
    lista.agrega(y);
}
System.out.println(lista);

El programa, de hecho, devolverá una lista de 300 elementos:

[Luis, Jose, Alvaro 0, Alvaro 1, Alvaro 2, Alvaro 3...]

En este ejemplo, ten en cuenta que hubo dos redimensionamientos:

1. Cuando superó los 100, el array se duplicó a 200 posiciones.
2. Cuando superó los 200, el array se duplicó a 400 posiciones (teniendo 100 de ellas con valores nulos).

ArrayList

Java ya tiene una implementación de Vector, que es la clase conocida como "ArrayList". Es muy similar a todo lo que hemos estado haciendo ahora y funciona como almacenamiento secuencial, con los métodos implementados en esta lección:

ArrayList<Alumno> listaDeJava = new ArrayList<Alumno>();

Aunque existe y nos hace la vida más fácil, es importante aprender cómo y qué implementar para crear una estructura de datos.

Listas Enlazadas

Usamos vectores y vimos que son buenas estructuras de datos para diferentes casos, como por ejemplo: agregar elementos al final del vector; obtener un elemento aleatorio; eliminar elementos.

Sin embargo, otros métodos no eran tan simples, como, por ejemplo, insertar un elemento en medio del vector, una actividad computacionalmente costosa y con un proceso de ejecución lento.

Ya hemos visto el vector y hemos analizado sus ventajas y desventajas. Ahora, aprenderemos sobre otra lista. Con ella, intentaremos mejorar el código para que la adición de elementos en medio del array sea un proceso más rápido.

A esta lista la llamamos lista enlazada. La diferencia con el vector es que en el vector, los elementos están uno junto al otro en la memoria, mientras que en la lista enlazada, se encuentran en diferentes lugares, pero uno apunta al otro indicando el siguiente.

Así diseñamos la estructura, donde un elemento también conoce la dirección del siguiente. Para esto crearemos una clase "Celda" que tendrá un siguiente objeto (de tipo "Celda"). Para facilitar, también crearemos un constructor y getters (para el elemento) y setters (para el elemento y para la Celda):

public Celda(Object elemento, Celda proximo) {
    this.elemento = elemento;
    this.proximo = proximo;
}

public Celda getProximo() {
    return proximo;
}

public void setProximo(Celda proximo) {
    this.proximo = proximo;
}

public Object getElemento() {
    return elemento;
}

Ahora vamos a crear la Clase "ListaEnlazada" y definir sus funciones:

package ed.listaenlazada;

public class ListaEnlazada {

    public void agregaAlPrincipio(Object elemento) {}

    public void agrega(Object elemento) {}

    public void agrega(int posicion, Object elemento) {}

    public Object obten(int posicion) { return null; }

    public void elimina(int posicion) {}

    public int tamano() { return 0; }

    public boolean contiene(Object o) { return false;}
}

Método agregaAlPrincipio

Comencemos imaginando que tenemos una lista de celdas que apuntan entre sí. Para que una nueva celda entre al principio del array, debe apuntar a la siguiente, es decir, la primera del array actual. Por lo tanto, debemos tener un atributo llamado "primera". Como la lista comienza vacía, esta celda apunta a null:

public class ListaEnlazada {

    private Celda primera = null;

    public void agregaAlPrincipio(Object elemento) {
        Celda nueva = new Celda(elemento, primera);

    }

En una lista vacía, cuando agregamos una celda en la primera posición del array, debe apuntar a null. Sin embargo, cuando agregamos una siguiente, también al principio, esta apuntará a la anterior, y sumaremos 1 al total de elementos:

public class ListaEnlazada {

    private Celda primera = null;
    private int totalDeElementos = 0;

    public void agregaAlPrincipio(Object elemento) {
        Celda nueva = new Celda(elemento, primera);
        this.primera = nueva;

        this.totalDeElementos++;
    }

Para probarlo, crearemos la clase "PruebaListaEnlazada" con el método main y lo implementaremos para imprimir después de cada inserción de elementos:

package ed.listaligada

public class PruebaListaEnlazada {

    public static void main(String[] args) {
        ListaEnlazada lista = new ListaEnlazada();

        System.out.println(lista);
        lista.agregaAlPrincipio("Adrian");
        System.out.println(lista);
        lista.agregaAlPrincipio("Carina");
        System.out.println(lista);
        lista.agregaAlPrincipio("Daniel");
        System.out.println(lista);
    }
}

Si lo dejamos así, la devolución no será amigable y no entenderemos nada. Crearemos un "toString" amigable en la clase "ListaEnlazada":

@Override
public String toString () {

    if(this.totalDeElementos == 0) {
        return "[]";
    }

    Celda actual = primera;

    StringBuilder builder = new StringBuilder("[");

    for(int i = 0; i < totalDeElementos; i++) {
        builder.append(actual.getElemento());
        builder.append(",");

        actual = actual.getProximo();
    }

    builder.append("]");

    return builder.toString();
}

Al ejecutar, devuelve:

[]
[Adrian,]
[Carina,Adrian,]
[Daniel,Carina,Adrian,]

Método agrega (al final de la lista)

Para listas enlazadas, este método es un poco más complejo. Lo que nos dice si un elemento es el último del array es si apunta a null. Para eso, es necesario recorrer toda la lista. Resolveremos el problema creando una flecha para el último elemento (de la misma manera que hicimos para el primero):

private Celda primera = null;

private Celda ultima = null;

Con este cambio, tendremos que ajustar algunas cosas en el método "agregarAlPrincipio". Si la lista está vacía, la primera celda también será la última:

 public void agregaAlPrincipio(Object elemento) {
        Celda nueva = new Celda(elemento, primera);
        this.primera = nueva;

        if(this.totalDeElementos == 0) {
            this.ultima = this.primera;
        }

        this.totalDeElementos++;
    }

Volviendo al desafío de insertar al final, creamos una nueva celda cuyo siguiente elemento es null, ya que se está agregando al final del array. Debemos hacer que la última celda actual apunte a esta nueva.

public void agrega(Object elemento) {

    Celda nueva = new Celda(elemento, null);
    this.ultima.setProximo(nueva);
    this.ultima = nueva;
    this.totalDeElementos++;    
}

Pero necesitamos ocuparnos del caso particular en que la lista está vacía y lo haremos utilizando el otro método ya implementado:

public void agrega(Object elemento) {

    if(this.totalDeElementos == 0) {
        agregaAlPrincipio(elemento);
    } else {
        Celda nueva = new Celda(elemento, null);
        this.ultima.setProximo(nueva);
        this.ultima = nueva;
        this.totalDeElementos++;
    }
}

Vamos a hacer una prueba:

lista.agrega("Gabriel");
System.out.println(lista);

Lo que devuelve:

[Daniel,Carina,Adrian,Gabriel,]

Método agrega (en medio de la lista)

Para implementar este método, vamos crear otros dos para ayudar. Uno indicará cuando la posición exista y esté ocupada:

private boolean posicionOcupada(int posicion) {
    return posicion >= 0 && posicion < this.totalDeElementos;
}

Y el otro señalará la celda en la que queremos insertar el elemento:

private Celda obtenCelda(int posicion) {

    if(!posicionOcupada(posicion)) {
        throw new IllegalArgumentException("posición inexistente");
    }

    Celda actual = primera;

    for(int i = 0; i < posicion; i++) {
        actual = actual.getProximo();
    }
    return actual;
}

Imaginemos ahora, una vez más, que ya tenemos una lista donde un elemento apunta al otro. El elemento izquierdo debe apuntar al nuevo elemento y este al de la derecha. Entonces, en código, hacemos lo siguiente:

public void agrega(int posicion, Object elemento) {

    Celda anterior = this.obtenCelda(posicion - 1);
    Celda nueva = new Celda(elemento, anterior.getProximo();
}

De esta manera, obtenemos la Celda izquierda (anterior) y la nueva en lugar de la siguiente (anterior.getProximo). Por último, solo debemos hacer que el anterior sea el nuevo elemento y sumar 1 al total de elementos.

public void agrega(int posicion, Object elemento) {

    Celda anterior = this.obtenCelda(posicion - 1);
    Celda nueva = new Celda(elemento, anterior.getProximo());
    anterior.setProximo(nueva);
    this.totalDeElementos++;
}

Todavía falta implementar el método para cuando la lista esté vacía o cuando la posición "del medio" sea, en realidad, la última.

public void agrega(int posicion, Object elemento) {

    if(posicion == 0) {
        agregaAlPrincipio(elemento);
    } else if (posicion == this.totalDeElementos) {
        agrega(elemento);
    } else {
        Celda anterior = this.obtenCelda(posicion - 1);
        Celda nueva = new Celda(elemento, anterior.getProximo();
        anterior.setProximo(nueva);
        this.totalDeElementos++;
}

Vamos a probarlo en el main:

lista.agrega(2, "Juliana");
System.out.println(lista);

Lo que devuelve:

[Daniel,Carina,Juliana,Adrian,Gabriel,]

Método obten

Para el "obten":

public Object obten(int posicion) {
    return this.obtenCelda(posicion).getElemento();
}

En main:

Object x = lista.obten(2);
System.out.println(x);

Lo que devuelve:

Juliana

Método tamaño

Para el "tamaño":

public int tamano() {
    return this.totalDeElementos;
}

En main:

System.out.println(lista.tamano());

Lo que devuelve:

5

Método elimina

Antes de implementar el método "elimina", vamos a hacer el "eliminaDelComienzo":

public void eliminaDelComienzo() {
    if(this.totalDeElementos == 0) {
        throw new IllegalArgumentException("lista vacía");
    }

    this.primera = this.primera.getProximo();
    this.totalDeElementos--;

    if(this.totalDeElementos == 0) {
        this.ultima = null;
    }
}

Probando:

lista.eliminaDelComienzo();
System.out.println(lista);

Lo que devuelve:

[Carina,Juliana,Adrian,Gabriel]

El elemento en la primera posición (Daniel) fue removido.

Listas doblemente enlazaadas

Ya aprendimos sobre Listas enlazadas, cuya idea era que una celda estaba conectada a su próxima en un array. Nos ha facilitado la implementación y la velocidad de ejecución.

Ahora, vamos a conocer las Listas doblemente enlazadas, cuyos elementos no solo apuntan a su próximo, sino también a su anterior.

Entonces, volviendo a nuestra Clase Celda, vamos a crear un nuevo parámetro con tu getter y setter:

private Celda anterior;

...

public Celda getAnterior() {
    return anterior;
}

public void setAnterior(Celda anterior) {
    this.anterior = anterior;
}

Y vamos a crear un Constructor que nos ayudará a implementar el primer método:

public Celda(Object elemento) {
    this(null, elemento);
}

A partir de ahora, vamos a repensar nuestro código implementado en la clase anterior para que se adapte a los nuevos parámetros.

Método agregaAlPrincipio

En la clase "ListaEnlazada", el primer método que implementamos fue "agregaAlPrincipio". Vamos a reescribirlo:

public void agregaAlPrincipio(Object elemento) {
    if(this.totalDeElementos == 0) {
        Celda nueva = new Celda(elemento);
        this.primera = nueva;
        this.ultima = nueva;
    } else {
        Celda nueva = new Celda(this.primera, elemento);
        this.primera.setAnterior(nueva);
        this.primera = nueva;
    }
    this.totalDeElementos++;
}

Vamos a entender este código:

• Si la lista está vacía, creamos una celda y su siguiente es null, y lógicamente su anterior también. Esto ya lo habíamos hecho anteriormente.
• Creamos una nueva celda cuyo siguiente es la primera. Y su anterior es la nueva. Y la primera es la nueva.

Método agrega (al final)

public void agrega(Object elemento) {
    if(this.totalDeElementos == 0) {
        agregaAlPrincipio(elemento);
    } else {
        Celda nueva = new Celda(elemento);
        this.ultima.setProxima(nueva);
        nueva.setAnterior(this.ultima);
        this.ultima = nueva;
        this.totalDeElementos++;
 }

Muy similar al método implementado anteriormente. La única diferencia es que lo configuramos para la celda anterior.

Recordemos lo que hicimos:

• Creamos una nueva celda.
• La última apunta a la siguiente de esta nueva celda.
• La nueva celda apunta al anterior de la última actual.
• La última actual ahora es la nueva celda.

Método agrega (en cualquier posición)

public void agrega(int posicion, Object elemento) {
    if(posicion == 0) {
        agregaAlPrincipio(elemento);
    } else if (posicion == this.totalDeElementos) {
        this.agrega(elemento);
    } else {
        Celda anterior = obtenCelda(posicion - 1);
        Celda proxima = anterior.getProxima();

        Celda nueva = new Celda(anterior.getProxima(), elemento);
        nueva.setAnterior(anterior);
        anterior.setProxima(nueva);
        proxima.setAnterior(nueva);
        this.totalDeElementos++;
}

Método elimina (al final)

Ahora que sabemos acerca de las listas doblemente enlazadas, podemos implementar el método para eliminar al final.

Si el array tiene solo un elemento, llamamos al método "eliminaAlPrincipio":

public void eliminaAlFinal() {
    if(this.totalDeElementos == 1) {
        this.eliminaAlPrincipio();
    }

Para eliminar el elemento al final, necesitamos la penúltima celda, que está enlazada a él:

public void eliminaAlFinal() {
    if(this.totalDeElementos == 1) {
        this.eliminaAlPrincipio();
    } else {
        Celda penultima = this.ultima.getAnterior();
        penultima.setProxima(null);
        this.ultima = penultima;
        this.totalDeElementos--;
    }
}

Vamos a probar el método. Antes, la lista tenía Carina,Juliana,Adrian,Gabriel. Llamando a la función:

lista.removeDofim();
System.out.println(lista);

El resultado será:

[Carina,Juliana,Adrian]

Método elimina (en cualquier posición)

Si el elemento está en la primera o en la última posición, simplemente llamamos a los métodos ya implementados.

public void elimina(int posicion) {
    if(posicion == 0) {
        this.eliminaAlPrincipio();
    } else if (posicion == this.totalDeElementos - 1) {
        this.eliminaAlFinal();
    }
}

Pero ahora necesitamos pensar en cómo eliminar el elemento del medio. Vamos a navegar y dar nombres a los elementos y configurar sus anteriores y siguientes:

public void elimina(int posicion) {
    if(posicion == 0) {
        this.eliminaAlPrincipio();
    } else if (posicion == this.totalDeElementos - 1) {
        this.eliminaAlFinal();
    } else {
        Celda anterior = this.pegaCelula(posicion - 1);
        Celda actual = anterior.getProximo();
        Celda proxima = actual.getProximo();

        anterior.setProximo(proxima);
        proxima.setAnterior(anterior);

        this.totalDeElementos--;
    }
}

Probemos este método. Primero agreguemos algunos nombres más a la lista para tener algo como esto:

[Carina,Juliana,Adrian,Cecilia]

Ahora hagamos, por ejemplo:

lista.elimina(2);
System.out.println(lista);

Lo que nos devuelve:

[Carina,Juliana,Cecilia]

El elemento en la posición 2, Adrian, ha sido eliminado de la lista.

Método contiene

Este método será similar al del vector. Usaremos el while, que es otra forma de bucle.

public boolean contiene(Object elemento) {
    Celda actual = this.primera;

    while(actual != null) {
        if(actual.getElemento().equals(elemento)) {
            return true;
        }
        actual = actual.getProximo();
    }
    return false;
}

El método recorrerá todo el array hasta encontrar (true) o no encontrar (false) el elemento mencionado.

Vamos a probarlo:

System.out.println(lista.contem("Cecilia"));
System.out.println(lista.contem("Mauricio"));

El programa devolverá:

true
false

Cecilia está en la lista y Mauricio no.

Pilas

Ya hemos aprendido acerca de las listas enlazadas y las listas enlazadas doblemente, que tienen celdas que apuntan a otras, anteriores y posteriores. Vimos en los ejercicios que Java ya tiene todo esto implementado a través de la clase LinkedList.

En este momento, veremos otra estructura de datos cuya principal diferencia con otros tipos de estructuras de datos es que guarda varios estados de una aplicación para que en el futuro, si es necesario, se pueda volver a estos estados. A esta estructura le llamamos Pila\.

Vamos a crear un paquete y dentro de él la clase "Pila". Las operaciones que tendremos en esta pila son:

package ed.pila

public class Pila {

    public void agrega(String nombre) {

    }

    public String elimina() {
        return "";
    }

    public boolean vacia() {
        return false;
    }
}

La Pila sigue la regla de insertar elementos uno tras otro y la eliminación funciona de la misma forma, desde el último hasta el primer elemento. Para empezar a implementar, no partimos de cero. Ya tenemos una parte del código hecha, ya que la hicimos en los estudios de listas. Vamos a utilizar la implementación que Java nos ofrece.

package ed.pila

import java.util.LinkedList;
import java.util.List;

public class Pila {
    private List<String> nombres = new LinkedList<String>();
}

Creemos un documento de prueba para empezar a implementar los métodos:

package ed.pila

public class PruebaDePila {

    public static void main(String[] args) {
        Pila pila = new Pila();
    }
}

Lo que debemos implementar también es el toString:

@Override
public String toString() {
    return nombres.toString();
}

Método agrega

Implementar el método utilizando el concepto de Pila es simple, ya que siempre seguiremos un orden. Entonces, el método agrega quedará así:

public void agrega(String nombre) {
    nombres.add(nombre);    
}

Probemos:

pila.agrega("Luisa");
System.out.println(pila);

pila.agrega("Daniel");
System.out.println(pila);

Lo que devuelve:

[Luisa]
[Luisa, Daniel]

Método elimina

Aquí simplemente llamamos a "elimina" de LinkedList pasando el elemento en la posición nombres.size()-1:

public String elimina() {
    return nombres.elimina(nombres.size()-1);
}

Para probar, vamos a imprimir cada elemento que se eliminará y luego la lista final:

String r1 = pila.elimina();
System.out.println(r1);

String r2 = pila.elimina();
System.out.println(r2);

System.out.println(pila);

Lo que nos devuelve:

Daniel
Luisa
[]

Los elementos se eliminaron empezando desde el final de la lista.

Método vacia

Este método indica si la lista está vacía o no. Tenemos dos formas de implementarlo:

public boolean vacia() {
    return nombres.size() == 0;
}

O utilizando la función de LinkedList:

public boolean vacia() {
    return nombres.isEmpty();
}

Para probarlo, imprimamos el valor booleano System.out.println(pila.vacia()); antes y después de insertar elementos en la lista. Veremos que devuelve:

true
false

Antes, la lista estaba vacía y después de insertar elementos, ya no lo está.

Java también tiene una clase propia para pilas, llamada Stack. Cambiando los nombres de nuestros métodos a los de la clase de Java, tenemos:

• agrega-> push
• elimina -> pop

Podemos escribir en el archivo de prueba:

Stack<String> stack = new Stack<String>();
stack.push("Mauricio");
stack.push("Daniel");

System.out.println(stack);

Lo que imprime [Mauricio, Daniel]. Y para eliminar:

stack.pop();
System.out.println(stack);

Lo que imprime [Mauricio].

Método peek

Como vimos, el pop elimina el último elemento de la pila. El método peek también trabaja con ese elemento, pero sin eliminarlo, ya que simplemente lo devuelve. Por lo tanto, si tenemos la pila [Mauricio, Daniel]:

String nombre = stack.peek();
System.out.println(nombre);

Nos devuelve Daniel.

Utilización de las pilas

El concepto de pilas se utiliza ampliamente en compiladores y autómatas, por lo que podemos decir que esta estructura de datos tiene mucha utilidad en la ciencia de la computación. El propio y muy conocido comando "Deshacer" en editores de texto, código, imágenes, etc., se basa en las pilas. También podemos jugar con palabras e invertir el orden de sus letras utilizando pilas.

Filas

Ahora vamos a conocer las Filas, que se estructuran de manera similar a las pilas. Sin embargo, a diferencia de las pilas, donde el primer elemento que entra es el último en salir, en las filas el primer elemento que entra es el primero en salir.

Creemos la clase "Filas", que será compatible con LinkedList, y tendrá algunos métodos y toString.

package ed.fila;

import java.util.LinkedList;
import java.util.List;

public class Fila {

    private List<String> alumnos = new LinkedList<String>();

    //métodos

    @Override
    public String toString() {
        return alumnos.toString();
    }

}

También creamos, como es costumbre, el método main para probar las funciones de la Fila:

package ed.fila;

public class PruebaDeFila {
    public static void main(String[] args) {
        Fila fila = new Fila();
    }
}

Método agrega

Este método funciona de la misma manera que el de la pila:

public void agrega(String alumno) {
    alumnos.add(alumno);
}

Hagámoslo para probar:

fila.agrega("Mauricio");
fila.agrega("Luis");

System.out.println(fila);

Lo que devuelve:

[Mauricio, Luis]

Método elimina

Recuerda que en la estructura de FILA, siempre se elimina el primer elemento de la matriz, por lo que hacemos:

public String elimina() {
    return alumnos.elimina(0);
}

Para probar:

String x1 = fila.elimina();
System.out.println(x1);
System.out.println(fila);

Lo que devuelve:

Mauricio
[Luis]

"Mauricio", que es el primer elemento, ha sido eliminado.

Método vacia

También nos falta este método. Lo implementamos de la siguiente manera:

public boolean vacia() {
    return alumnos.isEmpty();
}

Queue

Al igual que la estructura de las Pilas tenía el nombre de Stack, a la estructura de las Filas le damos el nombre de Queue:

Para las filas, los métodos tienen los siguientes nombres:

• agregar: add
• eliminar: poll

Los implementamos de la siguiente manera:

Queue<String> filaDeJava = new LinkedList<String>();

filaDeJava.add("Mauricio");
String x2 = filaDeJava.poll();

Si imprimimos x2, nos devuelve Mauricio.

Conclusión

En este artículo, hemos visto en la práctica vectores, listas enlazadas, listas doblemente enlazadas, pilas y filas. Es muy importante comprender cómo funciona una estructura debajo de la superficie, por lo que el estudio de las estructuras de datos es una parte fundamental de la programación y de la formación de profesionales en el campo. Aprendiendo esto, estarás preparado para elegir la mejor solución.

Si este contenido te ha interesado, puedes acceder a los siguientes enlaces para mejorar tu aprendizaje:

• Estructura de datos: introducción | Alura Cursos Online
• Cursos Java Orientado a Objetos | Formación | Alura (aluracursos.com)

Este artículo se basa en contenido desarrollado por Mauricio Aniche en 2014.

Artículo hecho por Akemi Alice.

Artículo traducido para Alura Latam por Brenda Souza.