Estructura de datos con Java

Imagine administrar una grande cantidad de datos en su programa, seguramente buscaría utilizar una forma más eficiente, por esto, como elegir la forma más viable?

La estructura de datos es la forma de organizar y guardar datos, esta existe para que determinado dato pueda ser utilizado de manera eficiente, posibilitando una mejor administración. El objetivo de este artículo es comprender cómo funcionan las estructuras de datos por detrás de escena, 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 que podamos elegir uno de ellos en nuestro programa, es decir, elegir la solución más viable. Para ello, veámoslo en la práctica utilizando un proyecto Java como base.

Almacenamiento secuencial y vectores

Con Eclipse abierto, comencemos nuestro primer proyecto de estructuras de datos. Como ejemplo, trabajaremos con una universidad, donde necesitamos almacenar y recuperar datos de los estudiantes. En otras palabras, lo agregaremos al final o en medio de una lista, lo eliminaremos, lo buscaremos según su número, etc.

El primer paso en este proyecto es modelar la clase "Estudiante". Para ello creamos un nuevo proyecto y dentro de él la clase Estudiante, que es donde almacenaremos el nombre del estudiante, el cual recibiremos en el propio Class Builder.

A continuación, creemos el captador e implementemos los métodos "equals" y "toString", que serán muy importantes. "Iguales" es el método que se utiliza para comparar dos objetos, en este caso estudiantes. Harémos un casting del objeto alumno. "toString" devuelve el nombre del estudiante:

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;
    }   

}

Al hacer esto, la primera estructura de datos que veremos es el almacenamiento secuencial. La idea de esta estructura es almacenar un alumno tras otro. Tendremos un conjunto de espacios (Array), donde: el primer alumno está en el primer espacio, el segundo alumno en el segundo espacio, y así sucesivamente.

Sabiendo esto, creemos una nueva Clase, llamada "Vector", en la que necesitamos implementar la estructura de almacenamiento secuencial. Además, necesitamos insertar 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 adicionar(Alumno alumno) {
        //recibe un alumno
    }

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

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

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

    public int tamanio() {
        //Devuelve la cantidad de alumnos
        return 0;
    }

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

}

Los retornos ya se han insertado para que podamos compilar el código. Antes de implementar los comportamientos, escribiremos el método principal para probar el Vector, incluso antes de que exista el código. Para ello crearemos la Clase "VetorTeste":

package ed;

public class VetorTeste {

    public static void main(String[] args) {

    }
}

Método Adicionar

El primer método que probaremos es "adicionar", utilizando dos estudiantes:

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

        Vector lista = new Vector();

        lista.adicionar(a1);
        lista.adicionar(a2);

        System.out.println(lista);
    }

Al correr el programa nos devuelve:

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

Habrá 100 valores nulos, por lo que el método "agregar" está funcionando. Entonces ¿lo vamos a implementar? La idea es recorrer todo el array y, en cuanto encuentre una posición nula, se almacena en él el alumno actual:

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

Ejecutando nuevamente el programa nos va a devolver:

[Juan, Jose, null, null, null...]

Ahora los dos estudiantes han sido insertados en el array. Pero tengamos en cuenta que el algoritmo que implementamos no tiene mucho rendimiento, ya que cuanto mayor sea el número de estudiantes insertados en el array, más tardará el método, ya que el bucle atravesará los espacios ya llenos varias veces. Intentaremos mejorarlo para que no dependa de la cantidad de elementos de la lista. Para hacer esto, usaremos el siguiente código:

    private Aluno[] alunos = new Aluno[100];
    private int totalDeAlunos = 0;

    public void adiciona(Aluno aluno) {
        this.alunos[totalDeAlunos] = aluno;
        totalDeAlunos++;
    }

Método Tamaño

El siguiente método que vamos a probar es "tamaño":

public int tamanio() {
        return totalDeAlumnos;
    }

Agreguémoslo al método principal:

System.out.println(lista.tamanio());
        lista.adicionar(a1);
        System.out.println(lista.tamanio());
        lista.adicionar(a2);
        System.out.println(lista.tamanio());

Nos Devolverá:

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

En cada iteración, devuelve el tamaño de la lista completa de estudiantes.

Método Contiene

Implementemos el método "contener". Queremos "preguntar" a la lista si un estudiante específico está o no en ella.

public boolean contener(Aluno alumno) {

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

Para probar "true", agregamos en la main:

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

Ejecutando..

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

Para probar "falso" creamos un estudiante que no se agregará a la lista:

Alumno a3 = new Alumno("Danilo");
System.out.println(lista.contener(a3));

Ejecutando..

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

Método pegar

Para implementar este método, que devuelve el nombre del estudiante en el puesto que solicitamos, hacemos:

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

Recuerda que nuestro array tiene 100 posiciones. ¿Qué pasaría si preguntáramos por el estudiante en la posición 200? Probemos usando main:

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

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

Empecemos a pensar en validar los datos que vamos a pasar al programa. Necesitamos que devuelva, por ejemplo, un mensaje más amigable, en lugar de un error. Crearemos un método auxiliar que nos dirá si una determinada posición está ocupada o no:

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

En el método pegar:

 public Alumno pega(int posicion) {

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

        return alumnos[posicion];
    }

Esta parte es muy importante, ya que es nuestra responsabilidad implementar la estructura para asegurar que maneja cualquier dato incorrecto proporcionado por el usuario.

Otro método Adicionar

Implementemos otro método que, a diferencia del método "agregar" que ya hemos visto, inserta un estudiante en cualquier posición de la matriz:

public void adiciona(int posicao, Aluno aluno) {

}

Pensemos en cómo construir este método. Imaginemos, en nuestro conjunto de 100, que las primeras diez posiciones ya están ocupadas. Queremos insertar un estudiante en tercera posición, como en la imagen a continuación:

Para ello arrastraremos a todos los alumnos de la tercera posición en adelante hacia la derecha y colocaremos a ese alumno en el hueco que quedó, como podemos ver en la siguiente imagen:

Entonces hacemos:

public void adiciona(int posicion, Alumno alumno) {

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

Probémoslo agregando un estudiante:

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

Lo que el programa nos devuelve:

[Jose, Danilo, Jose, null, null...]

El estudiante Danilo pasó a la posición 1, empujando a todos hacia la derecha. Sin embargo, de la misma manera que "lo entiende", necesitamos validación:

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

Y en el método:

public void adiciona(int posicion, Aluno alumno) {

    if(!posicionValida(posicion)) {
        throw new IllegalArgumentException("posicion invalida");
    }
    for(int i = totalDeAlumnos - 1; i >= posicion; i-=1) {
        alumnos[i+1] = alumnos[i];
    }
    alumnos[posicion] = alumno;
    totalDeAlumnos++;
}

Método Remover

Nuestro siguiente reto es el método "quitar", que será similar al método "añadir", pero pensando a la inversa: quitamos al alumno de la posición n y empujamos a todos los que vinieron detrás de él hacia la izquierda:

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

Probando:

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

Antes estaba así:

[Jose, Danilo, Jose, null, null...]

Y ahora:

[Joao, Jose, null, null, null...]

Cambiar el tamaño del Array

Ya hemos implementado los métodos principales de nuestro Array. Sin embargo, tenga en cuenta que el tamaño de la matriz 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 una nueva más grande y copiar todo lo que hay en la anterior a esta. Creamos el método "guardarEspacio":

private void guardarEspacio() {
    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;
    }

}

Ahora necesitamos invocar los dos métodos "agregar":

public void adicionar(Alumno alumno) {
    this.guardarEspacio();
    ...
}

public void adiciona(int posicion, Alumno alumno) {
    this.guardarEspacio();
    ...
}

Ahora, si agrega más elementos que el tamaño del array anterior, su tamaño cambiará a un nuevo array.

Para probar esta implementación, creemos un bucle en la main que agregará 300 estudiantes:

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

De hecho, el programa devolverá una lista de 300 elementos:

[Joao, Jose, Joao 0, Joao 1, Joao 2, Joao 3...]

En este ejemplo, observe que hubo dos cambios de tamaño:

1. Cuando superó los 100, duplicó la matriz a 200 posiciones;
2. Cuando superó los 200, se duplicó la matriz a 400 posiciones (100 de ellas con valores nulos).

ArrayList

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

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

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

Listas enlazadas

Usamos vectores(Array) y vimos que son buenas estructuras de datos para varios casos, tales como: agregar elementos al final del vector; tomar un elemento aleatorio; eliminar elementos.

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

Ya vimos Vector y observamos sus pros y sus contras y ahora vamos a conocer otra lista. Con él intentaremos mejorar el código para que agregar elementos en medio del array sea un proceso más rápido.

A esta lista la llamamos lista enlazada. La diferencia entre este y el Vector es que en este los elementos están uno al lado del otro en la memoria, mientras que en la lista enlazada están en diferentes lugares, pero uno apunta al otro indicando el siguiente.

Así es como diseñaremos la estructura, en la que un elemento también sabrá la dirección del siguiente. Para hacer esto, crearemos una Clase "Celda" que tendrá un objeto y su siguiente objeto (de tipo "Celda"). Para facilitar las cosas, creemos también un Constructor y captadores (para el elemento) y definidores (para el elemento y la Celda):

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

public Celula getProximo() {
    return proximo;
}

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

public Object getElemento() {
    return elemento;
}

Ahora creemos la clase "Lista enlazada" y definamos sus funciones:

package ed.listaenlazada;

public class ListaEnlazada {

    public void adicionarEnElComienzo(Object elemento) {}

    public void adicionar(Object elemento) {}

    public void adiciona(int posicao, Object elemento) {}

    public Object pegar(int posicao) { return null; }

    public void remover(int posicao) {}

    public int tamanio() { return 0; }

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

Método adicionarEnElComienzo

Empecemos imaginando que ya tenemos una lista con celdas apuntando entre sí. Para que una nueva celda ingrese al comienzo de la matriz, debe apuntar a su siguiente celda, es decir, la primera celda de la matriz actual. Entonces debemos tener un atributo llamado "primero". Cuando la lista comienza vacía, esta celda apunta a nulo:

public class ListaEnlazada {

    private Celula primera = null;

    public void adicionarEnElComienzo(Object elemento) {
        Celula nueva = new Celula(elemento, primera);

    }

En la lista vacía, cuando agregamos una celda a la primera posición de la matriz, debe apuntar a nulo. Cuando agreguemos uno siguiente, también al principio, apuntará al anterior; y suma 1 al número total de elementos:

public class ListaEnlazada {

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

    public void adicionarEnElComienzo(Object elemento) {
        Celula nueva = new Celula(elemento, primera);
        this.primera = nueva;

        this.totalDeElementos++;
    }

Para probar, creemos la clase "Prueba de lista enlazada" con el método principal e implementémosla para imprimir después de cada inserción de elemento:

package ed.listaenlazada

public class ProbarListaEnlazada {

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

        System.out.println(lista);
        lista.adicionarEnElComienzo("mauricio");
        System.out.println(lista);
        lista.adicionarEnElComienzo("paulo");
        System.out.println(lista);
        lista.adicionarEnElComienzo("guilherme");
        System.out.println(lista);
    }
}

Si lo dejamos así, el feedback no será amigable y no entenderemos nada. Creemos un toString amigable en la clase "ListaEnlazada":

@Override
public String toString () {

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

    Celula 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();
}

Ahora si ejecutamos nos devuelve:

[]
[mauricio,]
[paulo,mauricio,]
[guilherme,paulo,mauricio,]

Método Adicionar (Al final de la lista)

Para las 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 nulo. Para hacer esto, necesita escanear la lista completa. Resolvamos el problema creando una flecha para el último elemento (de la misma manera que hicimos para el primero):

private Celula primera = null;

private Celula ultima = null;

Con este cambio tendremos que arreglar algunas cosas en el método "addNoComeco". Si la lista está vacía, el primer elemento también será el último:

 public void adicionarEnElComienzo(Object elemento) {
        Celula nueva = new Celula(elemento, primera);
        this.primera = nueva;

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

        this.totalDeElementos++;
    }

Volvamos al desafío de insertar al final. Creamos una nueva celda cuyo siguiente elemento es nulo, después de todo se está agregando al final de la matriz. Necesitamos hacer que el último actual apunte a este nuevo.

public void adicionar(Object elemento) {

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

Vamos a verificar:

lista.adicionar("marcelo");
System.out.println(lista);

Lo que devuelve:

[guilherme,paulo,mauricio,marcelo,]

Método Adiciona (En el medio de la lista)

Para implementar este método, crearemos otros dos para ayudar. Se indicará cuando el puesto existe, está ocupado:

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

Y el otro apuntará a la celda en la que queremos insertar el elemento:

private Celula hallarCelula(int posicion) {

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

    Celula 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 a otro. El elemento de la izquierda debe apuntar al nuevo, y éste al de la derecha. Entonces en código hacemos:

public void adicionar(int posicion, Object elemento) {

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

De esta manera obtenemos la Celda de la izquierda (anterior) y la nueva en lugar de la siguiente (anterior.getNext). Finalmente, simplemente haga que el anterior sea el nuevo y agregue 1 al número total de elementos:

public void adicionar(int posicion, Object elemento) {

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

El método aún necesita implementarse para cuando la lista esté vacía o cuando la posición "intermedia" sea, en realidad, la última:

public void adicionar(int posicion, Object elemento) {

    if(posicion == 0) {
        adicionaNoComeco(elemento);
    } else if (posicion == this.totalDeElementos) {
        adiciona(elemento);
    } else {
        Celula anterior = this.pegaCelula(posicao - 1);
        Celula nova = new Celula(elemento, anterior.getProximo();
        anterior.setProximo(nova);
        this.totalDeElementos++;
}

Probémoslo haciéndolo en main:

lista.adicionar(2, "gabriel");
System.out.println(lista);

Lo que devuelve:

[guilherme,paulo,gabriel,mauricio,marcelo,]

Método Pegar

Para el método Pegar:

public Object pegar(int posicion) {
    return this.pegarCelula(posicion).getElemento();
}

En la Main:

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

Devuelve:

gabriel

Método Tamaño

Para el tamaño:

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

En la Main:

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

Lo que devuelve:

5

Método remove

Antes de implementar el método "remove", hagamos el "removeDelComienzo":

public void removeDelComienzo() {
    if(this.totalDeElementos == 0) {
        throw new IllegalArgumentException("lista vacia");
    }

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

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

Verificando:

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

Lo que devuelve:

[paulo,gabriel,mauricio,marcelo]

Se eliminó el elemento en la primera posición (Guilherme).

Listas doblemente enlazadas

Ya hemos aprendido sobre las Listas Enlazadas, cuya idea era que una celda estuviera vinculada a la siguiente celda en una matriz. Ella nos lo facilitó en términos de implementación y velocidad de ejecución.

Ahora, veamos las Listas doblemente enlazadas, cuyos elementos no sólo apuntan a la siguiente, sino también a la anterior.

Entonces, volviendo a nuestra clase de celda, creemos un nuevo parámetro con su Getter y Setter:

private Celula anterior;

...

public Celula getAnterior() {
    return anterior;
}

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

Y creemos un Constructor que nos ayudará a la hora de implementar el primer método:

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

A partir de ahora repensaremos nuestro código implementado en la clase anterior para adaptarlo a los nuevos parámetros.

Método adicionaEnElComienzo

En la Clase "ListaLigada", el primer método que implementamos fue "adicionaEnElComienzo". Reescribámoslo:

public void adicionaEnElComienzo(Object elemento) {
    if(this.totalDeElementos == 0) {
        Celula nueva = new Celula(elemento);
        this.primera = nova;
        this.ultima = nova;
    } else {
        Celula nova = new Celula(this.primeira, elemento);
        this.primera.setAnterior(nueva);
        this.primera = nueva;
    }
    this.totalDeElementos++;
}

Entendamos este código:

• Si la lista está vacía creamos una celda y la siguiente celda es nula y lógicamente la anterior también. Esto ya lo habíamos hecho anteriormente;
• Creamos una nueva celda cuyo siguiente es el primero. Y el anterior a este es el nuevo. Y el primero es el nuevo.

Método Adiciona(En el Final)

public void adicionar(Object elemento) {
    if(this.totalDeElementos == 0) {
        adicionaEnElComienzo(elemento);
    } else {
        Celula nueva = new Celula(elemento);
        this.ultima.setProxima(nova);
        nova.setAnterior(this.ultima);
        this.ultima = nueva;
        this.totalDeElementos++;

Muy similar al método implementado anteriormente. La única diferencia es que nos fijamos en la celda anterior.

¿Recordamos lo que hicimos?

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

Método Adicionar (En una posición cualquiera)

public void adicionar(int posicion, Object elemento) {

    if(posicion == 0) {
        adicionaEnElComienzo(elemento);
    } else if (posicion == this.totalDeElementos) {
        this.adicionar(elemento);
    } else {
        Celula anterior = pegarCelula(posicao - 1);
        Celula proxima = anterior.getProxima();

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

Método Remove (Del Final)

Ahora que conocemos la lista doblemente enlazada, podemos utilizar el método de eliminación desde el final.

Si la matriz tiene un solo elemento, llamamos al método "removeDelComienzo":

public void removeDelFinal() {
    if(this.totalDeElementos == 1) {
        this.removeDelComienzo();
    }

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

public void removeDelFinal() {
    if(this.totalDeElementos == 1) {
        this.removeDelComienzo();
    } else {
        Celula penultima = this.ultima.getAnterior();
        penultima.setProxima(null);
        this.ultima = penultima;
        this.totalDeElementos--;
    }
}

Probemos el método. Antes en la lista estaban mauricio, cecilia, paulo. Llamando a la función:

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

El resultado será:

[mauricio, cecilia]

Método Remove (De Cualquier Posición)

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

public void remove(int posicion) {
    if(posicion == 0) {
        this.removeDelComienzo();
    } else if (posicion == this.totalDeElementos - 1) {
        this.removeDelFinal();
    }
}

Pero ahora tenemos que pensar en cómo quitar el elemento del medio. Naveguemos y nombremos los elementos y establezcamos sus anteriores y siguientes:

public void remove(int posicion) {
    if(posicion == 0) {
        this.removeDelComienzo();
    } else if (posicion == this.totalDeElementos - 1) {
        this.removeDelFinal();
    } else {
        Celula anterior = this.pegaCelula(posicion - 1);
        Celula atual = anterior.getProximo();
        Celula proxima = atual.getProximo();

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

        this.totalDeElementos--;
    }
}

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

[mauricio, cecilia, jose, joao]

Ahora hacemos, por ejemplo:

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

Los que nos devuelve:

[mauricio, cecilia, joao]

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

Método Contiene

Este método será similar a Vector. Usemos while, que es otro enfoque de bucle.

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

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

El método escaneará toda la matriz hasta encontrar, (verdadero) o no (falso), el elemento mencionado.

Vamos a probar:

System.out.println(lista.contiene("mauricio"));
System.out.println(lista.contiene("danilo"));

El programa devolverá:

true
false

Maurício está en la lista y Danilo no.

Pilas

Ya hemos aprendido sobre listas enlazadas y doblemente enlazadas. Estas listas tenían celdas que apuntaban 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 punto veremos otra estructura de datos cuya principal diferencia, en relación a otro tipo de estructuras de datos, es almacenar los diferentes estados de una aplicación para que en el futuro, si es necesario, sea posible volver a dichos estados. A esta estructura la llamamos Pilha.

Creemos un paquete y, dentro de él, la Clase "Stack". Las operaciones que tendremos sobre esta pila son:

package ed.pila

public class Pila {

    public void insertar(String nombre) {

    }

    public String remove() {
        return "";
    }

    public boolean vacia() {
        return false;
    }
}

El Stack sigue la regla de insertar elementos uno tras otro y eliminarlos funciona de la misma forma, desde el último hasta el primer elemento. Para empezar a implementar, no empezamos desde cero. Ya tenemos parte del código hecho, tal como lo hicimos en los estudios de listas. Utilicemos la implementación que nos ofrece Java.

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 comenzar a implementar los métodos:

package ed.pila

public class TestDeLaPila {

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

Lo que también deberíamos implementar es toString:

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

Método Inserir

Implementar el método utilizando el concepto Stack es sencillo, ya que siempre seguiremos un orden. Entonces el método de inserción se verá así:

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

Probando:

pila.inserir("Mauricio");
System.out.println(pila);

pila.inserir("Guilherme");
System.out.println(pila);

Lo que devuelve:

[Mauricio]
[Mauricio, Guilherme]

Método Remove

Aquí simplemente llame a "eliminar" de LinkedList pasando el elemento en el cuadro nombres.size()-1:

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

Para probar, pediremos imprimir cada elemento que será eliminado y luego la lista final:

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

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

System.out.println(pila);

Nos devolverá:

Guilherme
Mauricio
[]

Los elementos se han eliminado comenzando desde el final de la lista.

Método Vacio

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

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

O usando la función LinkedList:

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

Para probar, imprimamos el comando booleano System.out.println(pila.empty()); antes y después de insertar elementos en la lista. Veremos que devolverá:

true
false

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

Java también tiene su propia clase para pilas, llamada Stack. Reemplazando los nombres de nuestros métodos por los de la Clase Java, tenemos:

• insertar -> push
• eliminar -> pop

Podemos escribir en el archivo de prueba:

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

System.out.println(stack);

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

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

Lo que imprime [Mauricio].

Método Peek

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

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

Nos devuelve Marcelo.

Usabilidad de las Pilas

El concepto de pilas es muy utilizado por compiladores y autómatas, por lo tanto, podemos decir que esta estructura de datos tiene mucha usabilidad en informática. El muy conocido comando "Deshacer" en editores de texto, código, imágenes, etc. Se basa en baterías. También podemos jugar con las palabras e invertir el orden de sus letras utilizando las pilas.

Colas

Ahora conozcamos las colas, que están estructuradas de forma similar a las pilas. Sin embargo, a diferencia de las pilas, en las que el primer elemento en entrar es el último en salir, en las colas el primero en entrar es el primero en salir.

Creemos la clase "Queue", que será compatible con LinkedList y tendrá algunos métodos y también el método toString.

package ed.cola;

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

public class Cola {

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

    //métodos

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

}

También creamos, como siempre, el método principal para probar las funciones de la cola:

package ed.cola

public class TestDeCola {

    public static void main(String[] args) {
        Cola cola = new Cola();

    }
}

Método Adiciona

Este método funciona igual que la pila:

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

Hacemos para probar:

cola.adiciona("Mauricio");
cola.adiciona("Guilherme");

System.out.println(cola);

Lo que nos devuelve:

[Mauricio, Guilherme]

Método Remove

Recuerda que, en la estructura de Cola, el primer elemento del array siempre será eliminado, así que hacemos:

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

Probando:

String x1 = cola.remove();
System.out.println(x1);
System.out.println(cola);

Lo que devuelve:

Mauricio
[Guilherme]

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

Método Vacio

Todavía nos falta este método. Lo implementamos de la siguiente manera:

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

Queue

De la misma manera que la estructura Stacks se llamaba Stack, la estructura Queue se llama Queue:

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

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

• agregar: add
• eliminar: poll

Lo implementamos de la siguiente manera:

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

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

Si imprimimos x2, nos devuelve Mauricio.

Conclusión

En este artículo, vimos vectores, listas enlazadas, listas doblemente enlazadas, pilas y colas en la práctica. Es muy importante entender cómo funciona una estructura bajo el capó y, por lo tanto, el estudio de las estructuras de datos es una parte fundamental de la programación y la formación de profesionales en el campo. Al aprender esto, estará preparado para optar por la mejor solución.

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

• Estructura de Datos: Introducción
• Formación Java y Orientación a Objetos