Autor: ochoscar (Página 5 de 7)

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

Los miembros Estáticos y Constructores en Java son muy útiles en el momento de desarrollar código el primero permite establecer una característica de la membresía y el segundo como se inicializan los atributos de los objetos y esto se logra con los constructores, en este post aprenderás ambos conceptos.

Si quieres aprender sobre la historia de Java da clic en este enlace.

1. Miembros estáticos Atributos y Métodos

Los miembros Estáticos en Java utilizan la palabra reservada static y permiten vincular un atributo o método con la clase directamente, en este punto es conveniente notar que los atributos son independientes entre los objetos, de tal manera que cada objeto tiene su propia copia de los atributos, sin embargo con los atributos estáticos no ocurre lo mismo ya que solamente existe una copia de los mismos para todas las instancias de una clase (objetos).

Con los métodos pasa algo similar, de por si los métodos tienen una sola copia ya que todos los objetos acceden a las mismas instrucciones, sin embargo las variables que utilizan si son independientes por objeto, con un método estático se limita el acceso de dicho método solo a atributos estáticos, esta regla impide por ejemplo que un método estático acceda a un miembro no estático.

Al estar asociado los miembros estáticos a la clase los mismos pueden acceder a través del operador punto y utilizando el nombre de la clase, alternativamente puede usarse en objetos.

1.1 Ejemplos de miembros estáticos Atributos y Métodos

Conceptos básicos para escribir código en java que incluyen Clases Métodos y Atributos. Tipos de datos palabras reservadas y escritura básica de código.

A fin de ejemplificar el uso de métodos y atributos estáticos consideremos el siguiente código

public class DemoStatic {
    public int i;
    public static void staticMethod() {
        i = 2;
    }
}

Aquí el acceso a la variable i no esta permitido dentro del método estático y la razón es simple: el atributo no es estático, piense en ello un momento ya que lo anterior implica que se pueda hacer un llamado a staticMethod desde la clase, algo como: DemoStatic.staticMethod(), pero al intentar acceder a la variable i ¿cuál valor de variable se debe usar? sabiendo que el llamado se hizo desde la propia clase, por lo anterior no esta permitido acceder a miembros no estáticos desde métodos estáticos. Lo anterior ocurre con frecuencia cuando se comienza a programar en situaciones como la siguiente.

public class DemoStatic {
    public int i;
    public static void main(String args[]) {
        i = 2;
    }
}

En esencia es el mismo código anterior, excepto que se esta haciendo uso del método main, para subsanar lo anterior hay dos alternativas: convertir la i en atributo estático o instanciar un nuevo objeto de la clase, ambas soluciones se muestran a continuación.

public class DemoStatic {
    public static int i;
    public static void main(String args[]) {
        i = 2;
    }
}

public class DemoStatic {
    public int i;
    public static void main(String args[]) {
        DemoStatic ds = new DemoStatic();
        ds.i = 2;
    }
}

2. Constructores, bloques y ámbitos en Java

Los Constructores en Java son métodos especiales diseñados para inicializar los atributos y se caracterizan por tener el mismo nombre de la clase y retornar nada.

Random r = new Random();

La variable r se encarga de referenciar en memoria a un objeto recién creado de la clase Ramdom y usando el método constructor por defecto.

2.1. Constructores

Existen tres tipos de constructores tradicionales que son:

1. Los constructores por defecto no reciben ningún parámetro, Java incluye automáticamente en caso que el programador no especifique de forma explicita un constructor.
2. Constructor con parámetros, que recibe parámetros referentes a los atributos y normalmente los asigna a los mismos.
3. Constructor de copia, que recibe un objeto de la misma clase y realiza una copia de los atributos del parámetro en el nuevo objeto creado.

Según las reglas de sobrecarga de métodos pueden existir varios constructores, ya que un constructor es un método más.

Las reglas de sobrecarga establecen que los métodos pueden tener el mismo nombre y tipo de retorno siempre y cuando las firmas de los métodos difieran bien sea en tipos de datos de los parámetros o cantidad de parámetros u orden de los mismos o excepciones que arroje el método.

2.2. Inicializaciones de objetos

Un constructor inicializa los atributos que en general pueden inicializarse de tres formas.

• Inicialización en línea: ocurre cuando en la misma línea de la declaración se inicializa el atributo, esta es la primera inicialización que tiene un atributo..
• Inicialización en constructor: ocurre cuando se agrega lógica al constructor que inicializa la variable, esta es la última inicialización de un atributo.
• Inicialización de instancia: ocurre en un bloque de inicialización, estas inicializaciones junto con las inicializaciones en línea se ejecutan en el orden que se encuentren en el código.

Recuerde que no es posible referirse a una variable que no ha sido inicializada. El siguiente código muestra cada uno de estos esquemas de inicialización.

public class InitExamples {
    public InitExamples() {
        // Inicialización en constructor
        i = 5;
    }
    public static void main(String[] args) {
        InitExamples ie = new InitExamples();
        System.out.println(ie.i);
    }
    // Inicialización en línea
    private int i = 3;
    // Bloque de inicialización de instancia
    { i = 4; }
}

¿Qué valor cree que se imprime? Si respondió 5 esta en lo correcto. Observe el bloque de inicialización el cual no tiene etiquetas, ni firmas de prototipos, en este bloque se puede incluir la lógica necesaria para inicializar la variable.

2.3. Ámbitos y variables

Respecto a los bloques de código es importante que el programador reconozca que los bloques son trozos de código encerrados entre llaves y que el ámbito se refiere a los bloques de código donde se puede referir alguna variable.

• Variables locales: son aquellas declaradas dentro de los métodos y se pueden utilizar en el bloque fueron declaradas y en todo caso no antes de su declaración.
• Variables de instancia: estas también son conocidas como atributos y se pueden usar en el bloque de su declaración o desde su objeto siempre y cuando cumpla con las reglas de los modificadores de acceso. Una variable de instancia solo se encuentra en memoria al igual que el objeto al cual pertenece, por lo tanto cuando un objeto se queda sin referencias es liberado de la memoria mediante el recolector de basura sucede lo mismo con las variables de instancia.
• Variables de clase: estas variables son las conocidas como atributos estáticos y esta disponible en el bloque de su declaración y desde los objetos y clases siempre y cuando cumpla con las reglas de los modificadores de acceso. Una variable de clase esta disponible hasta que el programa termina.

Las variables de clase o de instancia pueden no ser inicializadas Java inicializa las variables según el tipo con los siguientes valores por defecto.

2.4. Inicializaciones estáticas

Finalmente, y con respecto al tema de inicializaciones y bloques es importante para el programador tener en cuenta que los bloques de inicialización pueden ser marcados con la palabra reservada static de la siguiente manera static { }, este código se ejecutará cuando se cargue la clase y sirve para inicializar atributos estáticos, de manera que en un bloque de inicialización estático solo pueden referenciar en miembros estáticos, similar a como sucede con los método estáticos.

3. Artículos de Interés