En esta entrada realizaremos la implementación de un ArrayList de Strings desde 0. La implementación la realizaremos de forma totalmente artesanal, es decir, no utilizaremos métodos de la clase ArrayList estándar de Java. Los métodos que vamos a implementar son los siguientes:
- El método «add», que nos servirá para añadir elementos a nuestro ArrayList
- El método «get», que nos servirá para obtener un elemento en una determinada posición.
- El método «size», que nos devolverá el número de elementos que tenemos ocupados en nuestro ArrayList.
- El método «getCapacity», que nos devolverá el número máximo de elementos que podemos almacenar en un momento determinado. Cabe destacar que esta estructura de datos se va a redimensionar de forma automática y transparente para quien vaya a ser usuario de nuestra clase.
- El método «remove», que servirá para eliminar una determinada cadena de nuestro ArrayList.
- El método «replace», que utilizaremos para eliminar una determinada cadena de nuestro ArrayList.
- El método «indexOf», que nos devolverá la posición de un determinado elemento si existe en nuestro ArrayList.
- El método «contains», que nos devolverá «true» o «false» en función de si existe un determinado elemento en nuestro ArrayList.
- El método «clear», que permitirá borrar todo el contenido de nuestro ArrayList.
- El método «isEmpty», que nos permitirá saber si nuestro ArrayList está vacío.
- Por último, el método «toString», que nos permitirá imprimir todo el contenido.
La idea es implementar los métodos principales de la clase ArrayList de Java:
https://docs.oracle.com/javase/8/docs/api/java/util/ArrayList.html
¿ Qué atributos de clase vamos a utilizar ?
Vamos a utilizar los siguientes atributos de clase, veamos el código:
private final static int INITIAL_SIZE = 10;
private String [] strings;
private int usedElements = 0;
private int capacity;
- INITIAL_SIZE será una constante que utilizaremos para dar un tamaño inicial a nuestro ArrayList en el constructor
- strings será nuestra estructura de datos interna para almacenar los elementos.
- usedElements será el índice que utilizaremos para saber en que posición tenemos que insertar un determinado elemento.
- capacity será el número máximo de elementos que podemos almacenar antes de redimensionar nuestra estructura de datos.
Veamos el constructor de nuestra estructura de datos
public MiArrayListCadenas() {
strings = new String[INITIAL_SIZE];
capacity = INITIAL_SIZE;
}
En el constructor realizamos principalmente 2 acciones:
- Instanciamos el Array de memoria estática «strings» utilizando la constante «INITIAL_SIZE» que inicialmente tiene un valor de 10.
- Asignamos a capacity el valor de la constante. Es decir, al inicio, la máxima capacidad de elementos que tenemos son 10.
El método add
El método «add» nos permite añadir elementos a nuestra estructura de datos.
public void add(String nuevaCadena) {
//Primero comprobamos si tenemos espacio y si es necesario redimensionar el array
if (usedElements < capacity - 1) {
//No hace falta redimensionar
strings[usedElements] = nuevaCadena;
}else {
//Es necesario redimensionar, incrementamos el tamaño actual por 2
capacity = capacity * 2;
String [] stringsAux = new String[capacity];
//Ahora copiamos todos los elementos
for (int i = 0; i < usedElements; i++) {
stringsAux[i] = this.strings[i];
}
this.strings = stringsAux;
this.strings[usedElements] = nuevaCadena;
}
usedElements++;
}
Vamos a explicar el funcionamiento de este método, ya que es el método que inserta elementos y redimensiona nuestra estructura de datos.
- Lo primero que realizamos es comprobar si tenemos tamaño suficiente para almacenar nuestro nuevo elemento. En este punto pueden pasar 2 cosas, si tenemos tamaño insertamos el elemento, si no tenemos tamaño redimensionamos la estructura. Ahora vemos en detalle la redimensión.
- Para redimensionar nuestra estructura de datos lo primero que hacemos es multiplicar el valor de la variable capacity por 2, es decir, en la primera redimensión sería 10 * 2 = 20.
- Posteriormente creamos un nuevo Array de memoria estática de capacidad de «capacity».
- Copiamos todos los elementos que tenemos actualmente en el Array.
- Intercambiamos los punteros, jajaja, sí, en Java también existen los punteros pero nos referimos a ellos como referencias de memoria.
- Como ya tenemos tamaño, almacenamos el elemento.
- Por último incrementamos la variable de «usedElement» en una unidad.
La redimensión y su ciclo de vida la podemos ver en la siguiente imagen:
El método get
El método get nos permite obtener un elemento de nuestra estructura de datos mediante un entero que marcará su posición.
public String get(int position) {
return this.strings[position];
}
Este método es muy sencillo, simplemente devolvemos la posición que nos llega por parámetro de entrada.
El método size
El método «size» nos sirve para saber cuantos elementos tenemos ahora mismo ocupados en nuestro ArrayList.
public int size() {
return this.usedElements;
}
Es muy sencillo, simplemente devolvemos nuestro índice interno que marca cuantos elementos tenemos ocupados.
El método getCapacity
El método «getCapacity» nos sirve para saber en un momento determinado cuantos elementos como máximo sin redimensión podríamos almacenar.
public int getCapacity() {
return this.capacity;
}
Este método también es muy sencillo, devolvemos el valor de nuestro atributo «capacity».
El método remove
El método «remove» nos permite eliminar un elemento pasado por parámetro de entrada. Este método tiene algo de historia y por lo tanto lo explicaremos en detalle.
public boolean remove(String stringToRemove) {
boolean found = false;
for (int i = 0; i < this.usedElements; i++) {
if (this.strings[i].equals(stringToRemove)) {
//Hemos encontrado el elemento
this.strings[i] = this.strings[i + 1];
found = true;
}else if (found) {
this.strings[i] = this.strings[i + 1];
}
}
if (found) {
this.strings[usedElements - 1] = null;
usedElements--;
}
return found;
}
- Lo primero que hacemos es declarar una variable de tipo boolean «found» que utilizaremos para 2 cosas principalmente, por una parte para devolver el resultado en caso de que el elemento que estamos intentando borrar exista y por otra parte para saber cuando debemos realizar el desplazamiento de elementos que veremos posteriormente.
- Mediante un bucle for recorremos nuestra estructura de datos interna hasta que encontremos el elemento a borrar.
- Una vez encontrado, para borrarlo lo que hacemos es asignar en la posición a borrar la posición del siguiente elemento.
- Para todos los elementos posteriores al borrado los desplazamos una posición hacía la izquierda, veamos un ejemplo: tenemos el siguiente array [ 1 2 3 4 5 6 ], queremos borrar el elemento cuyo valor es «4», [ 1 2 3 ] se quedan como están, en «4» ponemos «5», en «5» ponemos «6» y en «6» ponemos «null». Resultado: [1 2 3 5 6 null ], hemos borrado el elemento «4».
- Por último, reducimos el número de elementos ocupados en 1.
El método replace
El método «replace» es bastante sencillo y nos sirve para reemplazar un elemento por otro en una posición determinada.
public boolean replace(int position, String newString) {
boolean result = false;
if (position < this.usedElements) {
this.strings[position] = newString;
}
return result;
}
Simplemente si no nos salimos de los límites sobrescribimos el elemento.
El método indexOf
El método «indexOf» nos devuelve la posición de un determinado elemento en caso de que exista o -1 en caso de que no exista.
public int indexOf(String stringToSearch) {
int result = -1;
boolean found = false;
for (int i = 0; i < this.usedElements && !found; i++) {
if (this.strings[i].equals(stringToSearch)) {
found = true;
result = i;
}
}
return result;
}
Recorremos nuestra estructura de datos interna buscando el elemento y en caso de encontrarlo asignamos su posición a result, que es la variable que devuelve nuestro método.
El método contains
El método «contains» es igual que el método anterior pero en este caso se devuelve «true» o «false» en caso de que exista o no el elemento
public boolean contains(String stringToSearch) {
boolean found = false;
for (int i = 0; i < this.usedElements && !found; i++) {
if (this.strings[i].equals(stringToSearch)) {
found = true;
}
}
return found;
}
El método clear
El método «clear» nos permite borrar el contenido de todo nuestro Array.
public void clear() {
this.usedElements = 0;
this.strings = new String [INITIAL_SIZE];
}
- Seteamos el valor de la variable «usedElements» a 0.
- Volvemos a inicializar nuestra estructura de datos interna a una capacidad de 10.
- Resultado: Hemos borrado todo el contenido. El recolector de basura ya realizará el trabajo por nosotros para borrar todos los elementos que antes teníamos.
El método isEmpty
El método «isEmpty» nos permite conocer si nuestro ArrayList está vacio o no.
public boolean isEmpty() {
return (this.usedElements == 0);
}
Tan simple como devolver si «usedElements» es igual a 0.
El método toString
El método «toString» nos sirve para poder imprimir el contenido de nuestro ArrayList de una forma cómoda y legible de forma humana.
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("[ ");
for (int i = 0; i < this.usedElements; i++) {
sb.append("{" + this.strings[i] + "} ");
}
sb.append("]");
return sb.toString();
}
Lo devolvemos en formato [ {elemento1} {elemento2} {elemento3} …]
¿ Cómo vamos a probar nuestra clase ?
Las pruebas que vamos a realizar van a ser las siguientes:
- Inicializamos nuestra clase.
- Comprobamos si nuestra estructura está vacía.
- Insertamos 15 elementos.
- Volvemos a comprobar si nuestro ArrayList está vacío.
- Mostramos el contenido de nuestro ArrayList.
- Mostramos el número de elementos que tenemos ahora mismos ocupados.
- Borramos 4 elementos.
- Mostramos el contenido de nuestro ArrayList.
- Añadimos 3 nuevos elementos.
- Mostramos de nuevo el contenido de nuestro ArrayList.
- Comprobamos si existe un elemento que sabemos que existe.
- Comprobamos si existe un elemento que sabemos que NO existe.
- Localizamos la posición de un elemento que sabemos que existe.
- Localizamos la posición de un elemento que sabemos que NO existe.
- Limpiamos nuestro ArrayList.
- Imprimimos su contenido de nuevo para ver que realmente no hay ningún elemento.
El código de nuestras pruebas
MiArrayListCadenas cadenas = new MiArrayListCadenas();
System.out.println("Comprobamos si nuestro ArrayList está vacia: " + cadenas.isEmpty());
System.out.println("Insertamos 15 elementos:");
cadenas.add("1");
cadenas.add("2");
cadenas.add("3");
cadenas.add("4");
cadenas.add("5");
cadenas.add("6");
cadenas.add("7");
cadenas.add("8");
cadenas.add("9");
cadenas.add("10");
cadenas.add("11");
cadenas.add("12");
cadenas.add("13");
cadenas.add("14");
cadenas.add("15");
System.out.println("Comprobamos si nuestro ArrayList está vacia: " + cadenas.isEmpty());
System.out.println("Mostramos el contenido de nuestro ArrayList: " + cadenas);
System.out.println("Mostramos el numero de elementos que tenemos ocupados: " + cadenas.size());
System.out.println("Borramos los elementos 1,6,7,15");
cadenas.remove("1");
cadenas.remove("6");
cadenas.remove("7");
cadenas.remove("15");
System.out.println("Mostramos el contenido de nuestro ArrayList despues del borrado: " + cadenas);
System.out.println("Añadimos 3 nuevos elementos");
cadenas.add("nuevo elemento 1");
cadenas.add("nuevo elemento 2");
cadenas.add("nuevo elemento 3");
System.out.println("Mostramos el contenido de nuestro ArrayList despues de insertar 3 elementos más: " + cadenas);
System.out.println("Comprobamos si existe el 5 en nuestro ArrayList: " + cadenas.contains("5"));
System.out.println("Comprobamos si existe el 555 en nuestro ArrayList: " + cadenas.contains("555"));
System.out.println("Localizamos la posicion del 5 en nuestro ArrayList: " + cadenas.indexOf("5"));
System.out.println("Localizamos la posicion del 555 en nuestro ArrayList: " + cadenas.indexOf("555"));
System.out.println("Limpiamos nuestro ArrayList");
cadenas.clear();
System.out.println("Mostramos el contenido de nuestro ArrayList despues del borrado: " + cadenas);
La salida de nuestro programa
Comprobamos si nuestro ArrayList está vacia: true
Insertamos 15 elementos:
Comprobamos si nuestro ArrayList está vacia: false
Mostramos el contenido de nuestro ArrayList: [ {1} {2} {3} {4} {5} {6} {7} {8} {9} {10} {11} {12} {13} {14} {15} ]
Mostramos el numero de elementos que tenemos ocupados: 15
Borramos los elementos 1,6,7,15
Mostramos el contenido de nuestro ArrayList despues del borrado: [ {2} {3} {4} {5} {8} {9} {10} {11} {12} {13} {14} ]
Añadimos 3 nuevos elementos
Mostramos el contenido de nuestro ArrayList despues de insertar 3 elementos más: [ {2} {3} {4} {5} {8} {9} {10} {11} {12} {13} {14} {nuevo elemento 1} {nuevo elemento 2} {nuevo elemento 3} ]
Comprobamos si existe el 5 en nuestro ArrayList: true
Comprobamos si existe el 555 en nuestro ArrayList: false
Localizamos la posicion del 5 en nuestro ArrayList: 3
Localizamos la posicion del 555 en nuestro ArrayList: -1
Limpiamos nuestro ArrayList
Mostramos el contenido de nuestro ArrayList despues del borrado: [ ]
Y esto es todo queridos compis de la programación, si os ha gustado dejad un comentario para mostrar vuestro apoyo. En la próxima entrada modificaremos esta estructura de datos para que sea genérica y sirva para almacenar cualquier tipo de objeto y no solo cadenas.
Recordad que esto es una implementación personalizada, y que por lo tanto, no es conveniente utilizarla, si queréis utilizar Arrays con memoria dinámica utilizar los ArrayList estándar de Java. Aquí en el blog tenéis un buen artículo sobre su utilización.
Os dejo el código fuente por aquí: