Listas, Pilas y Colas en Java: Estructuras de Datos Explicadas

Estructuras de Datos en Java: Listas, Pilas y Colas

1. Listas con Arrays (AbstractList)

• Añadir (add): Para hacer hueco, el bucle debe ser decreciente (de derecha a izquierda) moviendo elementos +1 posición.

• Borrar (remove): Para quitar el hueco, el bucle debe ser creciente (de izquierda a derecha) moviendo elementos -1 posición.

2. Nodos y Listas Enlazadas

• Estructura Nodo Simple: Solo tiene referencias al item y al nodo next.

• Estructura Nodo Doble: Tiene referencias al item, al nodo previous y al nodo next.

• Lista Doblemente Enlazada (Variables): Necesita punteros head y tail, y la variable size.

• Costes Lista Doble: El borrado del último elemento mejora enormemente respecto a las listas simples, costando siempre O(1). El acceso o búsqueda en posiciones intermedias cuesta O(n).

• Lógica de Inserción/Borrado (Posición i): Las operaciones por el medio exigen localizar y modificar dos nodos clave: el de la posición i (nodo current) y el de la posición i-1 (nodo previous).

3. Pilas (LIFO mediante ArrayList)

• Posición de la Cima: La cima de la pila debe ubicarse obligatoriamente al final de la lista (en data.size()) para asegurar que las operaciones cuesten O(1).

• Iterador Clásico 1: Se crea un índice que empieza al final y en el método next() se resta primero (index--) para luego devolver el dato con data.get(index).

• Iterador Clásico 2 (ListIterator): Se inicializa al final (data.size() - 1) y recorre la pila hacia atrás utilizando los métodos hasPrevious() y previous().

4. Dobles Colas Circulares (CircularArrayDQueue)

• Estructura y Conflicto: Se usan los índices first y last, siendo vital utilizar la variable size para distinguir matemáticamente cuándo está vacía o llena.

• Constructor: Se instancia el array con casting ((E[]) new Object[capacity]) y se inicializan first y last a 0 (aunque last podría ser -1).

• Extracción (Ej. removeFirst): Hay que rescatar el dato y luego hacer obligatoriamente data[first] = null para la recolección de basura.

• Circularidad al extraer: Si la cola se vacía al borrar (size == 1 antes de restar), se resetean first y last a 0. Si no, first avanza con aritmética modular (first + 1) % data.length o haciendo un simple first++ seguido de un if para volver a 0 si alcanza el máximo.

• Retroceso circular (addFirst o removeLast) siempre es: (indice - 1 + length) % length.