Listas con Arreglos en Java

Las Listas con Arreglos en Java permiten que estas estructuras de datos se desarrollen usando memoria estática, con lo cual se requerirá operaciones de redimensionado de los arreglos cada vez que se cambie el tamaño, este post detalla el funcionamiento y el código de esta estructura de datos.

Acceda al código de las listas con memoria dinámica o enlazadas usando este link.

1. Lista con arreglos

Como se había mencionado anteriormente la lista con arreglos puede ser una implementación de la misma interface IList.

La ventaja en este caso es la facilidad para posicionarse en cualquier punto, sin embargo, al estar la lista conformada con arreglos, tiene las desventajas del uso de arreglos que se menciono al principio de esta sección.

El arreglo es muy óptimo para indexare, pero cuando se acaba el tamaño es necesario crear otro nuevo con más tamaño y hacer un copiado de los elementos del arreglo original en el nuevo con mayor capacidad, esta operación ralentiza los métodos de la lista.

Por esta razón las listas con arreglos deben tener mínimamente dos conceptos incluidos: el tamaño (que comúnmente se refiere al tamaño ocupado) y la capacidad (que es la máxima cantidad de elementos que puede tener el arreglo utilizado en la lista). A continuación, se presenta el código de la lista enlazada usando arreglos.

package lists;
import java.util.Iterator;
/**
 * Lista que usa arreglos nativos para implementar las operaciones de una lista
 * @author ochoscar
 * @param < T > Tipo genérico que contra los item de la lista
 */
public class ArrayList< T > implements IList< T >, Iterable< T >  {
    ////////////////////
    // Atributos
    ////////////////////
    /** Arreglo nativo de la lista que contiene los elementos y su longitud es
     la capacidad máxima de elementos a almacenar*/
    private T array[];
    /** Tamaño de la lista que refleja la cantidad de casillas del arreglo usadas */
    private int listSize;
    ////////////////////
    // Métodos
    ////////////////////
    /**
     * Constructor por defecto que crea la lista con 10 casillas de capacidad
     */
    public ArrayList() {
        array = (T[]) new Object[10];
        listSize = 0;
    }
    /**
     * Constructor especificando la capacidad inicial
     * @param initCapacity Capacidad inicial
     */
    public ArrayList(int initCapacity) {
        array = (T[]) new Object[initCapacity];
        listSize = 0;
    }
    /**
     * Método que verifica si la lista esta vacía
     * @return Devuelve true si la lista esta
     * vacía y false en caso contrario
     */
    @Override
    public boolean isEmpty() {
        return listSize == 0;
    }
    /**
     * Obtiene el primer item de la lista
     * @return Devuelve la Clase al principio de la lista
     * null en caso que la lista este vacía
     */
    @Override
    public T getFirst() {
        return listSize > 0 ? array[0] : null;
    }
    /**
     * Obtiene el ultimo elemento de la lista
     * @return Devuelve la ultima Clase en la lista
     * null si la lista esta vacía
     */
    @Override
    public T getLast() {
        return listSize > 0 ? array[listSize - 1] : null;
    }
    /**
     * Devuelve el i - esimo elemento de la lista
     * @param i Posición del elemento a devolver (comienza en 0)
     * @return Devuelve la Clase en la posición i
     */
    @Override
    public T get(int i) {
        return listSize > 0 && i > 0 && i < listSize ? array[i] : null;
    }
    /**
     * Método que establece un item de la lista en una posición especifica
     * @param p Objeto que sera establecido en una posición especifica
     * @param i Posición a establecer el objeto
     */
    @Override
    public void set(T p, int i) {
        if(listSize > 0 && i > 0 && i < listSize) {
            array[i] = p;
        }
    }
    /**
     * Método que determina el tamaño de la lista
     * @return Devuelve un entero que indica el tamaño de la lista
     */
    @Override
    public int size() {
        return listSize;
    }
    /**
     * Método que inserta al final de la lista
     * @param p Objeto a insertar
     * @return Devuelve la propia lista enlazada
     */
    @Override
    public IList< T > addLast(T p) {
        if(listSize == array.length) {
            adjustCapacity(2 * listSize);
        }
        array[listSize] = p;
        listSize++;
        return this;
    }
    /**
     * Método que permite agregar un objeto en un posición
     * arbitraria de la lista
     * @param p Objeto que se quiere agregar a la lista
     * @param i posición en la cual se quiere agregar
     * @return Devuelve la propia lista enlazada
     */
    @Override
    public IList< T > add(T p, int i) {
        if(listSize == array.length) {
            adjustCapacity(2 * listSize);
        }
        for(int j = listSize - 1; j >= i; j--) {
            array[j + 1] = array[j];
        }
        array[i] = p;
        listSize++;
        return this;
    }
    /**
     * Método que elimina un elemento dado un objeto
     * @param p Objeto a eliminar
     */
    @Override
    public void remove(T p) {
        for(int i = 0; i < listSize; i++) {
            if(array[i].equals(p)) {
                remove(i);
                break;
            }
        }
    }
    /**
     * Método que remueve un elemento de la lista
     * @param i Posición o índice a eliminar de la lista
     */
    @Override
    public void remove(int i) {
        for(int j = i; j < listSize; j++) {
            array[j] = array[j + 1];
        }
        listSize--;
    }
    /**
     * Devuelve si esta o no
     * @param p Objeto a verificar si esta en la lista
     * @return Devuelve true si p esta en la lista false sino
     */
    @Override
    public boolean contains(T p) {
        for(int i = 0; i < listSize; i++) {
            if(array[i].equals(p)) {
                return true;
            }
        }
        return false;
    }
    /**
     * Implementación de la interface iterable que permite recorrer la lista
     * con ciclos estilo for - each
     * @return Devuelve el iterador para recorrer la lista
     */
    @Override
    public Iterator< T > iterator() {
        // Creación de un objeto anónimo para retornarlo
        return new Iterator< T >() {
            /** Contador para referenciar el elemento que actualmente se itera */
            private int i = 0;
            /**
             * Método que indica si existen mas elementos a recorrer o no
             * @return True si existen mas elementos para recorrer y false en caso contrario
             */
            public boolean hasNext() {
                return i < listSize;
            }
            /**
             * Devuelve el elemento donde se encuentra parado el iterador y lo avanza
             * @return
             */
            public T next() {
                i++;
                return array[i - 1];
            }
            /**
             * Método que le permite al iterador remover un elemento de forma segura
             * En la lista hay que tener cuidado cuando se remueve mientras se itera puesto
             * que la eliminación cambia el tamaño de la lista. Este método
             * no se encuentra soportado en esta version.
             */
            public void remove() {
                throw new UnsupportedOperationException();
            }
        };
    }
    /**
     * Método privado utilitario encargado de asegurar una capacidad en el arreglo
     * haciendo una copia de los elementos del arreglo viejo en el nuevo
     * @param newCapacity Nueva capacidad del arreglo
     */
    private void adjustCapacity(int newCapacity) {
        T newArray[] = (T[]) new Object[newCapacity];
        for(int i = 0; i < listSize; i++) {
            newArray[i] = array[i];
            array[i] = null;
        }
        array = newArray;
    }
}

La siguiente imagen muestra el diagrama correspondiente a la lista implementada con arreglos.

Observe que el tamaño del arreglo, es decir, su capacidad puede verse incrementada en la operación add, en la cual se puede duplicar el tamaño del arreglo; una practica común es reducir también el tamaño del arreglo cuando se remueve, y es común disminuir el tamaño del arreglo a un cuarto del mismo si la mitad del arreglo esta libre.

Es importante con lo anterior evitar que se hagan secuencias de operaciones que dupliquen – recorren el tamaño del arreglo, es decir add – remove – add – remove y así sucesivamente decrementando sustancialmente el rendimiento del arreglo.

2. Artículos de Interés