Mes: agosto 2022 (Página 2 de 3)

Las colas son estructuras de datos similares a las pilas pero con un comportamiento diferente, esta también es una estructura básica puesto que se usa en muchos algoritmos y situaciones en programación.

Visita la página de listas para mayor detalle sobre esta estructura básica.

1. ¿Qué es una cola?

Una cola es una estructura de datos enlazada que sigue una disciplina FIFO (First In, First Out – Primero en entrar, Primero en salir) en la cual el primer elemento que entra es el primero en ser retirado, adicionalmente la estructura, aunque continua siendo una estructura lineal no se puede manipular cualquier elemento como sucedía con las listas, en las colas solamente se puede acceder al elemento que esta en la parte frontal, de manera que si se quiere alcanzar el último elemento, primero se requerirá desencolar todos los otros elementos. La siguiente figura muestra gráficamente una cola.

Las colas tienen muchos usos en informática, un ejemplo sencillo consiste en la representación de una fila de un banco o el procesamiento secuencial de una serie de actividades, por ejemplo el envío de notificaciones de correo electrónico en una aplicación transaccional.

2. Implementación de una cola

La implementación de una cola enlazada utiliza la misma clase Node que se utilizó en las listas enlazadas, la diferencia radica que en los métodos que se utilizan para manipular la cola y que se resumen a continuación:

• add: este método se encarga de agregar un nuevo elemento en la parte de atrás (último) de la cola.
• remove: este método remueve el elemento del frente de la cola (primer elemento) y lo devuelve.

2.1. Interface

A continuación se muestra el código correspondiente a las operaciones de una cola con su respectiva documentación.

package queues;
/**
 * Provee las acciones que se pueden realizar con una cola
 * @author ochoscar
 * @param < T > Tipo genérico de los cuales se almacenaran elementos dentro de la cola
 */
public interface IQueue< T > {
    /**
     * Método que verifica si la cola esta vacía
     * @return Devuelve true si la cola esta
     * vacía y false en caso contrario
     */
    public boolean isEmpty();
    /**
     * Método que determina el tamaño de la cola
     * @return Devuelve un entero que indica el tamaño de la cola
     */
    public int size();
    /**
     * Agrega un elemento al final de la cola
     * @param item Item de tipo genérico a ser agregado a la cola
     * @return Devuelve la misma cola que llamo al método
     */
    public IQueue add(T item);
    /**
     * Remueve un elemento del frente de la cola y lo devuelve para su manipulación
     * @return El elemento que se encontraba al frente de la cola
     */
    public T remove();
}

2.2. Clase Cola en Java

Las Colas de datos en Java se pueden implementar con la clase y consideraciones que se muestran a continuación.

La implementación de la interface anterior se encuentra en el siguiente código. Observe que se referencia tanto el primer como el último elemento a fin de realizar las operaciones de agregado y eliminación de forma óptima en cuanto a rendimiento se refiere. Algo importante también es que las operaciones de la cola no requieren de ciclos, por lo tanto la estructura se vuelve supremamente eficiente y así mismo no aporta mayor valor realizar una cola con arreglos, aunque es perfectamente posible.

package queues;
/**
 * Clase que encapsula las diferentes acciones de una cola enlazada
 * @author ochoscar
 * @param < T > Tipo genérico que contra los item de la cola
 */
public class Queue< T > implements IQueue< T > {
    ////////////////////
    // Atributos
    ////////////////////
    /** Referencia al primer nodo de la cola */
    private Node< T > front;
    /** Referencia al ultimo elemento de la cola */
    private Node< T > back;
    /** Tamaño de la cola */
    private int queueSize = 0;
    ////////////////////
    // Métodos
    ////////////////////
    /**
     * Método que verifica si la cola esta vacía
     * @return Devuelve true si la cola esta
     * vacía y false en caso contrario
     */
    @Override
    public boolean isEmpty() {
        return queueSize == 0;
    }
    /**
     * Método que determina el tamaño de la cola
     * @return Devuelve un entero que indica el tamaño de la cola
     */
    @Override
    public int size() {
        return queueSize;
    }
    /**
     * Agrega un elemento al final de la cola
     * @param item Item de tipo genérico a ser agregado a la cola
     * @return Devuelve la misma cola que llamo al método
     */
    @Override
    public IQueue add(T item) {
        Node< T > newNode = new Node(item, null);
        if(queueSize == 0) {
            front = back = newNode;
        } else {
            back.setNext(newNode);
            back = newNode;
        }
        queueSize++;
        return this;
    }
    /**
     * Remueve un elemento del frente de la cola y lo devuelve para su manipulación
     * @return El elemento que se encontraba al frente de la cola
     */
    public T remove() {
        if(queueSize == 0) return null;
        T item = front.getItem();
        front = front.getNext();
        if(front == null) back = null;
        queueSize--;
        return item;
    }
}

3. Artículos de Interés

Las pilas en Java junto con las listas constituyen una estructura básica de datos puesto que hay muchos comportamientos que obedecen al apilamiento de ítems.

Visite la sección de listas para encontrar detalles de estas estructuras de datos.

1. ¿Qué es una pila?

Una pila es una estructura de datos enlazada que sigue una disciplina LIFO (Last In, First Out – Último en entrar, Primero en salir) en la cual el ultimo elemento que entra es el primero en ser retirado, adicionalmente la estructura, aunque continua siendo una estructura lineal no se puede manipular cualquier elemento como sucedía con las listas, en las pilas solamente se puede acceder al elemento que esta en la cima, de manera que si se quiere alcanzar el elemento de la base, primero se requerirá desapilar todos los elementos. La siguiente figura muestra gráficamente una pila.

Las pilas tienen muchos usos en informática, un ejemplo sencillo consiste en la pila de llamados al sistema, en la cual se apilan y desapilan los llamados a los métodos a medida que se invocan los métodos o se retorna de ellos, respectivamente.2. Implementación de una pila

La implementación de una pila enlazada utiliza la misma clase Node que se utilizó en las listas enlazadas, la diferencia radica que en los métodos que se utilizan para manipular la pila y que se resumen a continuación:

• push: este método se encarga de agregar un nuevo elemento a la cima de la pila.
• pop: este método remueve el elemento de la cima y lo retorna.
• peek: este método se encarga de retornar el elemento de la cima sin eliminarlo de la pila.

1.1. Interface de las Pilas

A continuación se muestra el código correspondiente a las operaciones de una pila con su respectiva documentación.

package stacks;
/**
 * Provee las acciones que se pueden realizar con una pila
 * @author ochoscar
 * @param< T > Tipo genérico de los cuales se almacenaran elementos dentro de la pila
 */
public interface IStack< T > {
    /**
     * Método que verifica si la pila esta vacía
     * @return Devuelve true si la pila esta
     * vacía y false en caso contrario
     */
    public boolean isEmpty();
    /**
     * Método que determina el tamaño de la pila
     * @return Devuelve un entero que indica el tamaño de la pila
     */
    public int size();
    /**
     * Agrega un elemento en la cima de la pila
     * @param item Item de tipo genérico a ser agregado a la pila
     * @return Devuelve la misma pila que llamo al método
     */
    public IStack push(T item);
    /**
     * Remueve un elemento de la cima de la pila y lo devuelve para su manipulación
     * @return El elemento que se encontraba en la cima de pila
     */
    public T pop();
    /**
     * Devuelve un elemento de la cima de la pila sin removerlo
     * @return El elemento que se encontraba en la cima de pila
     */
    public T peek();
}

1.2. Clase Pila en Java

La implementación de la interface anterior se encuentra e n el siguiente código. Observe que solamente es necesario referenciar al elemento top o de la cima de la pila para realizar todas las operaciones. Algo importante también es que las operaciones de la pila no requieren de ciclos, por lo tanto la estructura se vuelve supremamente eficiente y así mismo no aporta mayor valor realizar una Pila con arreglos, aunque es perfectamente posible.

package stacks;
/**
 * Clase que encapsula las diferentes acciones de una pila enlazada
 * @author ochoscar
 * @param< T > Tipo genérico que contra los item de la pila
 */
public class Stack< T > implements IStack< T > {
    ////////////////////
    // Atributos
    ////////////////////
    /** Referencia a la cima de la pila */
    private Node< T > top;
    /** Tamaño de la cola */
    private int stackSize = 0;
    ////////////////////
    // Métodos
    ////////////////////
    /**
     * Método que verifica si la pila esta vacia
     * @return Devuelve true si la pila esta
     * vacía y false en caso contrario
     */
    @Override
    public boolean isEmpty() {
        return stackSize == 0;
    }
    /**
     * Método que determina el tamaño de la pila
     * @return Devuelve un entero que indica el tamaño de la pila
     */
    @Override
    public int size() {
        return stackSize;
    }
    /**
     * Agrega un elemento en la cima de la pila
     * @param item Item de tipo genérico a ser agregado a la pila
     * @return Devuelve la misma pila que llamo al método
     */
    @Override
    public IStack push(T item) {
        top = new Node<>(item, top);
        stackSize++;
        return this;
    }
    /**
     * Remueve un elemento de la cima de la pila y lo devuelve para su manipulación
     * @return El elemento que se encontraba en la cima de pila
     */
    @Override
    public T pop() {
        if(stackSize == 0) return null;
        T item = top.getItem();
        top = top.getNext();
        stackSize--;
        return item;
    }
    /**
     * Devuelve un elemento de la cima de la pila sin removerlo
     * @return El elemento que se encontraba en la cima de pila
     */
    @Override
    public T peek() {
        return top != null ? top.getItem() : null;
    }
}

2. Artículos de Interés

Las listas enlazadas en Java constituyen la base de las estructuras de datos y sustentan una gran cantidad de algoritmos, en este artículo se explicaran estas listas basadas en memoria estática y memoria dinámica.

Repasa los conceptos fundamentales de Java en este vínculo.

1. Necesidad

Las listas enlazadas surgen de la necesidad de manejar de forma más eficiente la memoria, debido a que los arreglos nativos, si bien proporcionan toda la funcionalidad requerida respecto al manejo de listas tiene un gran inconveniente y es que todas sus posiciones se encuentran contiguas (juntas) en memoria, una a continuación de la otra. Suponga entonces que se crea un arreglo de gran tamaño, afortunadamente en Java cada casilla contendrá una referencia a un objeto, es decir cada casilla tiene un tamaño de 32 o 64 bits dependiendo de la arquitectura de la máquina, sin embargo, si el arreglo es muy grande es posible que no se disponga de un gran bloque de memoria contigua para albergar el arreglo.

El problema de encontrar este espacio de memoria disponible empeora con el tiempo que lleve ejecutándose el programa, puesto que la creación de objetos y su recolección ocasionan huecos en la memoria en un fenómeno conocido como fragmentación de la memoria (muy parecido al que sucede en el disco duro, conocido como fragmentación del disco). La Figura 1. muestra un ejemplo de items almacenados en casillas de un arreglo.

La idea tras la lista enlazada es permitir que los items que se almacenan en las casillas no tengan que estar necesariamente uno detrás del otro, y para lograr esto las listas enlazadas se forman usando el concepto de clase autoreferenciada que se muestra a continuación.

2. Clases autoreferencias

Las listas enlazadas y muchas otras estructuras de datos se forman utilizando clases autoreferenciadas que no es otra cosa que una clase que contiene al menos un atributo cuyo tipo coincide con la misma clase, en otras palabras una clase autoreferenciada tiene una referencia a un objeto del mismo tipo de la clase.

En la Figura 2, se muestra un ejemplo de una clase autoreferenciada denominada Node que representa una casilla de una lista enlazada, observe como el nodo tiene un espacio de memoria para referenciar el objeto contenido en la casilla y una referencia al nodo siguiente.

3. Estructura de una Lista Enlazada

Las listas enlazadas aprovechan el concepto de clases autoreferenciadas para encadenar nodos y permitir armar una lista, observe que únicamente se requiere saber cual es el primer nodo de la lista, puesto que avanzando a través de la referencias next de cada nodo se puede llegar a cualquier otro nodo en la lista. El hecho de conocer la primera posición de la lista es algo que nos es familiar, ya que en el caso de los arreglos el nombre del arreglo realmente es un apuntador al primer elemento de la lista.

Observe que la lista tal como se plantea resuelve el problema de memoria mencionado anteriormente, es decir, al estar los nodos desligados los unos de los otros ya no es necesario para grandes arreglos encontrar un bloque contiguo de memoria, infortunadamente esta solución genera un nuevo inconveniente y es el desplazamiento por la lista, supongamos que se desea acceder a la casilla tercera de la lista, será necesario entonces a partir de la primera casilla iterar para posicionar una referencia que termine apuntando a la tercera casilla, esta iteración toma tiempo y empeora con el tamaño de la lista, situación que no sucede con los arreglos puesto que ubicarse en una posición cualquiera es simplemente una operación aritmética, por lo anterior indexar una posición en la lista enlazada es una operación de tiempo lineal con el tamaño de la lista, en cambio en el arreglo es una operación de tiempo constante.

El programador debe elegir adecuadamente su estructura de datos de tal manera que supla las necesidades del algoritmo, teniendo en cuenta también aspectos de rendimiento.

4. Implementación de Lista Enlazada

Basados en el gráfico de la Figura 3, podemos realizar la implementación de una lista enlazada, para ello consideraremos tres clases

• Interface: especifica los métodos públicos que implementaremos para las listas.
• Nodo: implementación de la clase autoreferenciada para representar las casillas de la lista enlazada.
• Lista: implementación de todos los métodos y utilidades de la lista enlazada.

El código que se muestra a continuación implementa las tres clases anteriores. Note que la implementación de la interface pude darse con diversas técnicas y formas, no solo con clases autoreferenciadas, de tal manera que para la misma interface se puede tener diferentes implementaciones, la primera que se mostrará es la lista enlazada, y la segunda la lista implementada con arrays.

4.1. Interface

Esta interface representa las operaciones habituales con la lista, observe algo interesante en el caso de los métodos add, los cuales devuelven una lista enlazada, esto a primera vista puede parecer extraño, pero realmente la idea es devolver la misma lista que llamo el método add y de esta forma habilitar el encadenamiento de llamados a métodos de la lista, por ejemplo, se pueden hacer llamados así list.add(obj1).add(obj2) y asi sucesivamente.

package lists;
/**
 * Provee las acciones que se pueden realizar con una lista
 * @author ochoscar
 * @param < T > Tipo genérico de los cuales se almacenaran elementos dentro de la lista
 */
public interface IList< T > {
    /**
     * Método que verifica si la lista esta vacía
     * @return Devuelve true si la lista esta
     * vacía y false en caso contrario
     */
    public boolean isEmpty();
    /**
     * 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
     */
    public T getFirst();
    /**
     * Obtiene el ultimo elemento de la lista
     * @return Devuelve la ultima Clase en la lista
     * null si la lista esta vacía
     */
    public T getLast();
    /**
     * 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
     */
    public T get(int i);
    /**
     * 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
     */
    public void set(T p, int i);
    /**
     * Método que determina el tamaño de la lista
     * @return Devuelve un entero que indica el tamaño de la lista
     */
    public int size();
    /**
     * Método que inserta al final de la lista
     * @param p Objeto a insertar
     * @return Devuelve la propia lista enlazada
     */
    public IList< T > addLast(T p);
    /**
     * 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
     */
    public IList< T > add(T p, int i);
    /**
     * Método que elimina un elemento dado un objeto
     * @param p Objeto a eliminar
     */
    public void remove(T p);
    /**
     * Método que remueve un elemento de la lista
     * @param i Posición o índice a eliminar de la lista
     */
    public void remove(int i);
    /**
     * 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
     */
    public boolean contains(T p);
}

4.2. Nodo

La clase que establece la raíz de la auto referenciación es esta y permite además almacenar el objeto que esta contenido en esta casilla de la lista. El código proporcionado muestra que esta clase no ofrece ninguna operación particular, solamente almacena los atributos para enlazar los nodos y así conformar la lista.

package linkedlist;
/**
 * Clase auto referenciada para construir la estructura
 * tipo lista enlazada que contendrá tanto el item almacenado
 * como la referencia al siguiente elemento de la lista
 * @author ochoscar
 */
public class Node< T > {
    ////////////////////
    // Atributos
    ////////////////////
    /** Referencia al tipo T que ocupa el nodo */
    private T item;
    /** Autoreferencia al siguiente elemento */
    private Node< T > next;
    ////////////////////
    // Métodos
    ////////////////////
    /**
     * Constructor por defecto
     */
    public Node() {
    }
    /**
     * Constructor con parámetros
     * @param pItem Item a almacenar en el nodo
     * @param pNext Siguiente elemento en la lista
     */
    public Node(T pItem, Node< T > pNext) {
        item = pItem;
        next = pNext;
    }
    /**
     * Constructor de copia
     * @param pNode Objeto que servirá para realizar la copia de los
     * atributos del nodo
     */
    public Node(Node< T > pNode) {
        item = pNode.getItem();
        next = pNode.getNext();
    }
    /**
     * Método que devuelve el nodo en su
     * representación de string
     * @return Devuelve la representación en String
     */
    @Override
    public String toString() {
        return item.toString();
    }
    /**
     * @return the item
     */
    public T getItem() {
        return item;
    }
    /**
     * @param item the item to set
     */
    public void setItem(T item) {
        this.item = item;
    }
    /**
     * @return the next
     */
    public Node< T > getNext() {
        return next;
    }
    /**
     * @param next the next to set
     */
    public void setNext(Node< T > next) {
        this.next = next;
    }
}

4.3. Lista Enlazada

La clase lista implementa no solo la interface de lista sino también la interface iterator que permite devolver un objeto Iterador con el cual se recorrerá la lista, este objeto es utilizado automáticamente por java en la instrucción for - each que corresponde a la siguiente sintaxis for(Obj obj : list)

package lists;
import java.util.Iterator;
/**
 * Clase que encapsula las diferentes acciones de una lista enlazada
 * @author ochoscar
 * @param < T > Tipo genérico que contra los item de la lista
 */
public class LinkedList< T > implements IList< T >, Iterable< T > {
    ////////////////////
    // Atributos
    ////////////////////
    /** Referencia al primer nodo de la lista */
    private Node< T > first;
    /** Tamaño de la lista */
    private int listSize = 0;
    ////////////////////
    // Métodos
    ////////////////////
    /**
     * 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 first != null ? first.getItem() : 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 ? null : getNode(listSize - 1).getItem();
    }
    /**
     * 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) {
        if(i >= 0 && i < listSize) {
            return getNode(i).getItem();
        }
        return 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(i >= 0 && i < listSize) {
            getNode(i).setItem(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) {
        add(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(i >= 0 && i <= listSize) {
            Node< T > newNode = new Node();
            newNode.setItem(p);
            // La lista esta vacía
            if(first == null) {
                first = newNode;
            } else {
                // La lista no esta vacía, y van a inserta
                // en la posición 0
                if(i == 0) {
                    newNode.setNext(first);
                    first = newNode;
                } else if(i == listSize) {
                    // Se quiere insertar al final de la lista
                    Node< T > last = getNode(listSize - 1);
                    last.setNext(newNode);
                } else {
                    Node< T > previous = getNode(i - 1);
                    Node< T > current = previous.getNext();
                    newNode.setNext(current);
                    previous.setNext(newNode);
                }
            }
            listSize++;
        }
        return this;
    }
    /**
     * Método que elimina un elemento dado un objeto
     * @param p Objeto a eliminar
     */
    @Override
    public void remove(T p) {
        Node< T > aux = first;
        int i = 0;
        boolean find = false;
        if(contains(p)){
            while(true){
                if(aux.getItem().equals(p)){
                    break;
                }else{
                    aux = aux.getNext();
                    i++;
                }
            }
            remove(i);
        }
    }
    /**
     * 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) {
        if(i >= 0 && i < listSize) {
            // La posición a eliminar es valida, se procede a eliminar
            if(i == 0) {
                first = first.getNext();
            } else {
                Node< T > previous = getNode(i - 1);
                previous.setNext(previous.getNext().getNext());
            }
            // Disminuye el tamaño de la lista
            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) {
        Node< T > iterator = first;
        while(iterator != null) {
            if(iterator.getItem().equals(p)) {
                return true;
            }
            iterator = iterator.getNext();
        }
        return false;
    }
    /**
     * Método que verifica si la lista esta vacia
     * @return Devuelve true si la lista esta
     * vacia y false en caso contrario
     */
    @Override
    public boolean isEmpty() {
        return first == null;
    }
    /**
     * Método que devuelve la lista en su
     * representación de string
     * @return Devuelve la representación en String
     */
    @Override
    public String toString() {
        String strToReturn = "[ ";
        Node< T > iterator = first;
        while(iterator != null) {
            strToReturn += iterator.toString() + " ";
            iterator = iterator.getNext();
        }
        return strToReturn + "]";
    }
    /**
     * 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 >() {
            /** Ubica un puntero en el primer elemento de la lista a retornar */
            private Node< T > iteratorNode = first;
            /**
             * 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 iteratorNode.getNext() != null;
            }
            /**
             * Devuelve el elemento dond se encuentra parado el iterador y lo avanza
             * @return
             */
            public T next() {
                T item = iteratorNode.getItem();
                iteratorNode = iteratorNode.getNext();
                return item;
            }
            /**
             * 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 que devuelve un nodo dada una posición
     * @param pos Posición de la lista para retornar el nodo
     * @return Devuelve el nodo indicado en el parámetro pos
     */
    private Node< T > getNode(int pos) {
        int i = 0;
        Node< T > iterator = first;
        while(iterator != null) {
            if(i == pos) {
                return iterator;
            }
            i++;
            iterator = iterator.getNext();
        }
        return null;
    }
}

Las listas enlazadas también se pueden disponer como listas doblemente enlazada, donde cada nodo no solamente mantenga una referencia de su siguiente elemento sino también del elemento anterior. A continuación se muestra la implementación de listas usando nodos doblemente enlazados, note que cada nodo tiene dos referencias una apuntando hacía el elemento siguiente y otra apuntando hacía el elemento anterior.

Algunas ventajas de esta lista es que ciertas operaciones de desplazamiento resultan más óptimas al no tener que recorrer siempre la lista completa desde el principio para posicionarse en cualquier elemento, considere en este sentido, por ejemplo, recorrer la lista en orden inverso. Otra lista importante es la Lista Circular que simplemente es aquella que se forma uniendo el principio de la lista con el final y en este caso es común utilizar un nodo ficticio para determinar un primer elemento de la lista

El programador debe elegir adecuadamente su estructura de datos de acuerdo con la naturaleza de los mismos y de esta forma se le facilitaran las operaciones, concentrarse en la lógica de fondo, realizar códigos menos propensos a errores y finalmente con mayor facilidad de mantenimiento.

5. 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.

6. Artículos de Interés

Según el tipo de aplicación, por ejemplo web, escritorio o móvil se debe seguir una serie de pasos para ejecutar un programa, en este artículo se aborda la ejecución de programas en Java de escritorio desde terminal o consola.

1. Ejecución de programas Java

1.1. Verificación de instalación de Java

Cuando pensamos en ejecutar programas Java para el escritorio requerimos hacerlo desde una consola o terminal, es importante para el ambiente cuente con el comando java instalado y sea accesible desde el lugar o directorio donde se ejecute el comando. En la figura 1 se muestra un ejemplo de ejecución del comando java -version que muestra la versión de la máquina virtual de Java que ejecutará el comando.

Es importante reconocer que también existen otros comandos para compilar como javac o algunas utilidades para revisar la carga de memoria o el comportamiento del procesador y que estas utilidades están disponibles en la carpeta bin de la instalación.

Para este punto lo más normal es compilar y ejecutar los archivos java utilizando un Entorno Integrado de Desarrollo o IDE como Eclipse, NetBeans o IntelliJ.

1.2. Ejecución de programa en Java desde la consola

Ahora, una vez que el comando java se encuentra disponible se podrán ejecutar programas java simplemente pasando el archivo .class como parámetro de Java y teniendo presente la jerarquía de paquetes donde se almaceno nuestra clase, por ejemplo la figura 2 muestra la ejecución del programa HolaMundo mostrado en el listado de código 1.

public class HolaMundo {
    public static void main(String args[]) {
        System.out.println("Hola mundo");
    }
}

Aquí se puede comprender el método main que es el punto de entrada para la ejecución de instrucciones en Java y el mismo debe ser estático para que la JVM pueda llamar el método sin necesidad de instanciar la clase HolaMundo, también debe ser público para que la JVM pueda ver el método, debe llamarse main específicamente puesto que con este nombre lo buscará la JVM.

Finalmente pueden pasarse una serie de parámetros a manera de arreglo e String, estos parámetros son enviados en el momento de la ejecución en la línea de comandos, y simplemente mencionar que si se envían parámetros que contengan espacios y estos van a ser interpretados como un solo ítem en el arreglo args deberá escribirse entre comillas dobles.

Para mayor información de clases métodos y atributos de Click aquí.

Alternativamente se pueden ejecutar los programa java si el proyecto es empaquetado como un jar, es decir, como un archivo comprimido java el cual contiene un conjunto de archivos .class y un archivo manifiesto que indica cual de las clases es la principal y que a su vez contiene un método main que será utilizado para iniciar la ejecución de instrucciones. El comando necesario para ejecutar un jar es el siguiente: java -jar ArchivoJAVAJAR.jar. Si el archivo jar no contiene un manifiesto o la clase principal no contiene un main con las consideraciones descritas nos será posible ejecutarlo.

2. Artículos de Interés

Si bien el encapsulamiento es uno de los pilares de la programación orientada a objetos en este artículo se expone las consideraciones especificas para el lenguaje Java.

1. Encapsulamiento

El encapsulamiento en java y es uno de los pilares de la programación orientada a objetos que establece la posibilidad de ocultar la información de las propiedades de un objeto de forma que las mismas no se accedan directamente.

Hasta este momento ya se conoce acerca de la forma de escribir clases y crear objetos, además se ha vinculado la sintaxis de la programación estructurada en el sentido que se cuenta con estructuras para controlar el flujo de un algoritmo, ahora entenderemos como las propiedades (recuerde que también se llaman atributos o campos) pueden ser ocultados para que los objetos no puedan modificarlos directamente.

1.1. Ocultamiento de la información

El objetivo entonces será ocultar la información de la implementación de forma que los usuarios programadores que utilicen la clase no puedan acceder a estos detalles, lo anterior mejorará la abstracción permitiendo que los programadores se enfoquen en usar atributos y métodos seguros con los cuales no puedan generar inadvertidamente daños.

2. Ejemplos

Para comprender estos conceptos consideremos la clase Tiempo.

class Tiempo {
    //////////////////////////
    // Atributos
    //////////////////////////
    private int hora;
    private int minutos;
    //////////////////////////
    // Métodos
    //////////////////////////
    public int getHora() {
        return hora;
    }
    public void setHora(int hora) {
        hora = this.hora;
    }
    public int getMinutos() {
        return minutos;
    }
    public void setHora(int minutos) {
        minutos = this.minutos();
    }
}

En esta clase se puede apreciar como los atributos son privados, lo cual indica que los objetos que creemos de dicha clase no podrán acceder directamente a los atributos, estos objetos aunque si contienen los atributos (hora y minutos) no podrán utilizarlos ya que al ser privados solamente se podrán usar en el mismo archivo y más concretamente en la misma clase donde fueron declarados.

Al parecer no existiría ninguna ventaja al tener los atributos privados puesto que sería mejor tenerlos públicos y evitarse el paso por un método para establecerlo (set) y obtenerlo (get) compare las siguientes dos líneas de código que muestran estas dos posibilidades.

Tiempo t = new Tiempo();
t.setHora(20);
t.hora = 40;

2.2. Comparación privado y público

El primer set de la variable Hora se realiza con el atributo encapsulado y privado mientras que el segundo se realiza con el atributo público, observe que en el segundo caso no existe ninguna forma de evitar asignar un valor inválido tal como esta sucediendo con el valor 40, de esta forma el encapsulamiento ayuda a evitar que los objetos tengan valores inconsistentes.

3. Utilidad del encapsulamiento

Algo adicional que debe conservar en mente y que es algo esencial del encapsulamiento es el hecho de que aísla la representación interna del objeto de su interface, en palabras más sencillas la representación interna dada por los atributos, sus valores y estados están tras una capa de métodos getter y setter, de forma que en una aplicación podría pensar en cambiar la forma como se guarda internamente las horas y decidir.

Por ejemplo, guardarlo con un solo entero, este cambio mejoraría el desempeño de la memoria afectando el desempeño en tiempos, sin embargo quienes hayan usado las clase Tiempo no se verán afectados y seguirán utilizando los mismos métodos getter y setter sin importar que internamente se guarden dos enteros para representar la hora y los minutos o un solo atributo para guardar, por ejemplo la cantidad de minutos que hayan pasado desde la media noche.

Repasa los fundamentos de las clases, métodos y atributos de java.

3. Artículos de Interés

Cuando se desarrollan algoritmos se debe considerar tanto las estructuras de datos como los controles de flujo cuya sintaxis en Java se recopila en este artículo.

1. Control de flujo: instrucciones condicionales

En Java las instrucciones de la programación estructurada están disponibles para controlar el flujo y determinar que instrucciones ejecutar o cuantas veces repetirlas.

Visita la página de historia de java para más detalles introductorios.

La primera instrucción de control es el condicional cuya forma compuesta se muestra a continuación.

// Forma simple del condicional
if(expresión booleana) {
    // Bloque en caso que la expresión sea verdadera
}
// Forma compuesta del condicional
if(expresión booleana) {
    // Bloque en caso que la expresión sea verdadera
} else {
    // Bloque en caso que la expresión sea verdadera
}
// Condicional en escalera
if(expresión booleana 1) {
    // Bloque en caso que la expresión 1 sea verdadera
} else if(expresión booleana 2) {
    // Bloque en caso que la expresión 2 sea verdadera
} else if(expresión booleana 3) {
    // Bloque en caso que la expresión 3 sea verdadera
} else{
    // Bloque en caso que ninguna expresion sea verdadera
}

Los puntos clave a resaltar sobre la instrucción condicional son los siguiente:

• Los paréntesis en la expresión booleana son obligatorios.
• No es requerido el uso de la parte del else en el código.
• Es supremamente importante tener en cuenta que el código dentro de un bloque debe tener sangría aplicada.
• En la tercera forma del condicional (en escalera) aunque varias expresiones booleanas sean verdaderas solamente se ejecuta el bloque correspondiente a la primera expresión booleana verdadera, así mismo puede haber un número indefinido de segmentos else if.
• Tenga presente que en muchas ocasiones el operador ternario simplifica la escritura del código, sin embargo, debe balancear dicha simplicidad con la dificultad de leer expresiones muy crípticas.
• En caso que los bloques tengan una sola instrucción no es necesario usar llaves, no obstante lo anterior es muy recomendado por legibilidad siempre usar llaves.

1.1. Instrucción swtich

Otra instrucción condicional es switch cuya sintaxis se puede apreciar en el siguiente segmento de código.

switch(variable) {
    case CONSTANTE1:
        // código 1
        break;
    case CONSTATE2:
        // código 2
        break;
    default:
        // código por defecto
}

En el caso de la instrucción switch se puede apreciar que la misma es utilizada de forma similar a un if en escalera, estos permiten realizar el control de flujo las bifuraciones del código . Hay que recordar que las instrucciones que se ejecutaran corresponden a la primera comparación verdadera de la variable con las diferentes constantes, igualmente solo se ejecuta un bloque de código que esta marcado desde los dos puntos y hasta el siguiente break, en ocasiones y dado que la instrucción break es opcional, se pueden juntar varios segmentos case para ejecutar un mismo código para cualquiera de las constantes que acompañen dichos segmentos case.

Note también que hay un segmento por defecto y es opcional, este se ejecuta cuando ninguna de las comparaciones con las constantes arrojo un resultado verdadero. Los tipos de datos soportados para la variable son: int, Integer, byte, Byte, short, Short, char, Character, String, y enum.

De otra parte las constantes, deben ser o bien literales o variables marcadas con la palabra reservada final, el tipo de dato de las constantes debe coincidir con el tipo de dato de la variable, además observe que final hace que la variable se convierta en constante y únicamente pueda recibir valor en el momento de su creación, sin embargo el código no compilara si usa una variable como constante y la misma es un parámetro de una función, así esta última este marcada como final.

2. Control de flujo: ciclos

Los ciclos son otra forma de realizar control de flujo en java al repetir o iterar una serie de isntrucciones.

2.1. Ciclo while

El ciclo más sencillo y fácil de utilizar es el while, el cual repite las instrucciones mientras una condición sea verdadera, en este sentido observe que en sintaxis se parece mucho al condicional if. A continuación se presenta su sintaxis.

while(condición booleana) {
    // Código
}

2.2. Ciclo do while

De forma similar, se encuentra el ciclo do - while el cual es similar al anterior, excepto que este se repite al menos una vez ya que la condición se evalúa al final del ciclo y no al principio. Su sintaxis se muestra a continuación.

do {
    // Código
} while(condición booleana);

2.3. Ciclo for

El tercer ciclo y de hecho uno de los más comunes es el ciclo for el cual en su presentación básica se muestra a continuación

for(inicialización, expresión booleana, actualización) {
    // Código
}

Las tres partes del ciclo for son opcionales y si todas se omiten el ciclo sería un ciclo infinito. También es posible separar múltiples sentencias de inicialización o actualización utilizando comas.

Es importante recordar que la inicialización no puede realizar ocultamiento de variables, es decir, si la variable declarada en la inicialización ya fue declarada antes del ciclo for el compilador arrojará un error indicando que se tiene una doble declaración de la variable, de esta manera las variables declaradas en la inicialización pertenecerán al ámbito del cuerpo del ciclo y no se podrán usar por fuera de este. El último ciclo disponible en Java es el ciclo for - each el cual se muestra a continuación.

for(TipoDato variable : colección) {
    // Código
}

En este caso la colección debe ser una implementación de java.lang.Iterable y el ciclo se ejecuta una vez por cada ítem de la colección, asignando en cada repetición un valor de la colección.

Algo importante a tener en cuenta con los diferentes ciclos es que los bloques de código pueden omitir las llaves cuando solo se trate de una sola línea, en estos casos es importante mantener la tabulación o poner la línea de código al frente de la estructura de control. En cualquier caso esta práctica no es muy recomendable puesto que es más propensa a introducir errores en el código.

3. Etiquetas, continue y break

Las sentencias (if, while, do while, for, switch) de Java pueden ser iniciadas con una etiqueta, normalmente escrita en mayúsculas y terminada en dos puntos. Estas etiquetas sirven para marcar los puntos donde se puede devolver el código mediante una sentencia break o continue, estas dos instrucciones permiten o romper un ciclo con la finalidad de salirse del mismo y no continuar su ejecución o en el caso de continue continuar de inmediato con la siguiente iteración del ciclo sin importar que falten instrucciones por ejecutar. La sintaxis de estas etiquetas es:

break etiquetaOpcional;
continue etiquetaOpcional;

Estas instrucciones están disponibles para los ciclos, adicionalmente las sentencia switch soporta el uso de break. El uso de estas instrucciones es particularmente útil cuando en un ciclo se detecta que no se requiere seguir ejecutando, por ejemplo, si se esta realizando una búsqueda y se encuentra el ítem deseado no se requeriría seguir iterando para buscar, en este caso se puede recurrir a la instrucción break o si la iteración ya no se requiere hacer se usaría continue.. Un ejemplo del uso de etiquetas junto con una sentencia break y continue se muestra a continuación.

PRIMERO: for( ... ) {
    SEGUNDO: for( ... ) {
        if( ... ) {
            // Rompe el ciclo actual terminándolo y haciendo
            // un salto a la etiqueta PRIMERO
            break PRIMERO;
        }
        if( ... ) {
            // Deja de ejecutar la iteración actual del ciclo
            // interno y brinca a la etiqueta SEGUNDO,
            // en este caso no es necesario el uso de etiquetas
            // puesto que la instrucción continue esta en el
            // cuerpo del segundo ciclo
            continue SEGUNDO;
        }
        // ... código ...
    }
}

4. Artículos de Interés