Análisis Interno de ArrayDeque: Implementación de Cola Basada en Arreglo Circular

ArrayDeque es una implementación eficiente de cola (y también de deque) en Java, que utiliza un arreglo subyacante con semántica circular para lograr inserciones y eliminaciones en tiempo constante amortizado. A diferencia de LinkedList, no depende de nodos enlazados, lo que reduce la sobrecarga de memoria y mejora la localidad de referencia.

Estructura fundamental

La clase se declara como:

public final class ArrayDeque<E> extends AbstractCollection<E>
    implements Deque<E>, Cloneable, Serializable

No hereda de AbstractQueue, sino que implementa directamente Deque, lo que le permite soportar operaciones en ambos extremos — aunque su uso típico como Queue se centra en el extremo frontal (head) para extracción y el posterior (tail) para inserción.

Representación interna

Su almacenamiento se basa en tres campos clave:

private transient E[] elements: arreglo genérico que almacena los elementos.
private transient int head: índice del primer elemento válido (el que será retirado primero).
private transient int tail: índice donde se insertará el próximo elemento (no el último ocupado, sino la siguiente posición libre).

El tamaño inicial mínimo es 8 y siempre se redimensiona a la menor potencia de dos mayor o igual que la capacidad solicitada. Esta restricción permite usar operaciones bit a bit para cálculos de envoltura eficientes.

Redimensionamiento inteligente

El método allocateElements(int) calcula la capacidad óptima mediante una secuencia de desplazamientos y operaciones OR:

private void allocateElements(int numElements) {
    int cap = Math.max(MIN_INITIAL_CAPACITY, numElements);
    cap |= cap >>> 1;
    cap |= cap >>> 2;
    cap |= cap >>> 4;
    cap |= cap >>> 8;
    cap |= cap >>> 16;
    cap++;
    if (cap < 0) cap >>= 1; // manejo de overflow
    elements = (E[]) new Object[cap];
}

Este patrón convierte cualquier entero positivo en el menor número de la forma 2<sup>n</sup> − 1, y al incrementarlo se obtiene 2<sup>n</sup>. Por ejemplo, para entrada 9 → binario 1001, tras las operaciones se obtiene 1111, luego 10000 (16). Es más eficiente que un bucle iterativo, especialmente para valores grandes.

Gestión circular mediante máscara bit a bit

La clave del comportamiento circular reside en el uso de la máscara (elements.length - 1). Dado que la longitud siempre es una potencia de dos, length - 1 tiene todos sus bits bajos activos (ej. 15 → 1111). Así, la expresión:

tail = (tail + 1) & (elements.length - 1)

equivale a tail = (tail + 1) % elements.length, pero sin división ni módulo — solo operaciones bit a bit ultrarrápidas. Cuando tail alcanza el final del arreglo (length - 1), la operación lo "envuelve" a 0, simulando un anillo lógico.

Inserción en la cola (offerLast / addLast)

La inserción verifica si la cola está llena comparando tail con head tras actualizarlo:

public void addLast(E e) {
    if (e == null) throw new NullPointerException();
    elements[tail] = e;
    if ((tail = (tail + 1) & (elements.length - 1)) == head) {
        doubleCapacity();
    }
}

Si tras avanzar tail coincide con head, significa que no hay espacio libre: la cola está llena (o vacía, pero la invariante garantiza que head == tail solo ocurre cuando está vacía o llena; aquí se resuelve por el orden de actualización).

Ampliación de capacidad

Cuando se requiere redimensionamiento, doubleCapacity() reubica los elementos manteniendo su orden lógico. Como el arreglo puede estar fragmentado (elementos entre head y el final, y otros desde el inicio hasta tail), se realizan dos copias sucesivas:

private void doubleCapacity() {
    assert head == tail;
    int n = elements.length;
    int r = n - head; // elementos desde head hasta el final
    int newCap = n << 1;
    if (newCap < 0) throw new IllegalStateException("Deque too large");
    Object[] a = new Object[newCap];
    System.arraycopy(elements, head, a, 0, r);      // primera parte
    System.arraycopy(elements, 0, a, r, head);      // segunda parte
    elements = (E[]) a;
    head = 0;
    tail = n;
}

Tras la expansión, el nuevo arreglo comienza vacío desde el índice 0, y tail apunta justo después de la antigua región ocupada, listo para nuevas inserciones.

Extracción desde el frente (pollFirst)

La eliminación recupera el elemento en head, lo nulifica para permitir recolección de basura y avanza head usando la misma máscara:

public E pollFirst() {
    int h = head;
    E result = elements[h];
    if (result == null) return null;
    elements[h] = null;
    head = (h + 1) & (elements.length - 1);
    return result;
}

Este diseño evita desplazaminetos masivos de elementos (como en ArrayList), manteniendo O(1) amortizado para todas las operaciones básicas.

Acceso sin modificación (peekFirst)

La lectura del primer elemento es trivial y segura:

public E peekFirst() {
    return elements[head]; // devuelve null si está vacío
}

No implica mutación ni validación adicional, lo que la hace extremadamente ligera.

En resumen, ArrayDeque combina la simplicidad de arreglos con la flexibilidad de estructuras circulares, aprovechando propiedades matemáticas de potencias de dos y operaciones bit a bit para lograr alto rendimiento y bajo consumo de memoria.

Etiquetas: java collections deque arraydeque data-structures

Publicado el 9-12 06:43

Friki Work