Sincronización.

    Los hilos se comunican principalmente compartiendo el acceso a los campos y los objetos a los que hacen referencia dichos campos. Aunque este esquema es extremadamente eficiente, lleva implícito dos errores potenciales:

1. Interferencia de hilos (Thread interference).
2. Errores de consistencia de memoria (Memory consistency errors).
   

    Con la sincronización se pueden prevenir estos dos errores, pero también se puede incurrir en la contención de hilos, que ocurre cuando dos o más hilos tratan de acceder al mismo recurso de manera simultánea (condición de competencia) provocando que el entorno de la máquina virtual ejecute uno o más hilos más lentamente, o incluso que llegue a suspender su ejecución. 

    La inanición y el interbloqueo de hilos son dos formas de contención y su análisis y tratamiento quedan fuera de los alcances de este blog. Aquí sólo se proporcionarán los elementos básicos relacionados con la sincronización de hilos y la prevención de los dos errores mencionados con anterioridad.

Interferencia de hilos.

    El planteamiento iniciará con el análisis de una clase extremadamente simple (Ejemplo Contador) que implementa un contador, así como su respectivo incremento, decremento y acceso a través de los métodos correspondientes.

    Si sólo un hilo accede a los métodos para la modificación de c: todo trabaja como se espera; pero si un objeto de la clase Contador es referido por múltiples hilos, la interferencia entre ellos hará que las cosas se salgan de control.

    La interferencia acontece cuando dos operaciones, ejecutándose en diferentes hilos pero accediendo a los mismos datos, se intercalan. Las operaciones de alto nivel que se escriben en los lenguajes de programación, por simples y sencillas que parezcan, habitualmente consisten de múltiples pasos o suboperaciones, y cuando estos pasos de traslapan o superponen los problemas emergen (condiciones de competencia).

    Los detalles precisos respecto a la exactitud de cómo se descompone una operación tan simple como el incremento de una variable (c++) no son relevantes, basta con saber por ahora que dicha operación podría ser descompuesta en tres pasos (ocurre lo análogo y correspondiente para c--):

1. Obtener o recuperar el valor actual de c (fetch).
2. Incrementar dicho valor en 1.
3. Almacenar el valor incrementado nuevamente en c.
   

    Con base en lo anterior, supongamos ahora la existencia de dos hilos, y que el Hilo A invoca a incrementa y que casi al mismo tiempo el Hilo B invoca a decrementa. Si el valor inicial de c es 0, una posible secuencia de acciones traslapadas podría ser la siguiente:

1. Hilo A: Recupera c.
2. Hilo B: Recupera c.
3. Hilo A: Incrementa valor recuperado; resultado: 1.
4. Hilo B: Decrementa valor recuperado; resultado: -1.
5. Hilo A: Almacena resultado en c; c vale ahora 1.
6. Hilo B: Almacena resultado en c; c vale ahora -1.
   

    Como puede observarse, el resultado del Hilo A se pierde: es sobre escrito por el resultado del Hilo B. Este planteamiento es sólo una combinación posible, bajo distintas circunstancias, podría ser que ahora el resultado del Hilo B sea el que se pierda o también podría darse el caso de que todo resulte bien como se espera; el resultado final es impredecible (condición de competencia).

    El Ejemplo PruebaContador muestra la situación de interferencia de hilos en una ejecución con dos hilos: uno (main) incrementando 100 000 veces el contador y el otro (h) decrementando la misma cantidad de veces ¿Cuál es el resultado esperado y cuál es el que se obtiene? ¿Se generan los mismos valores o resultados en distintas ejecuciones? ¿Por qué no son cero?

Errores de consistencia de memoria.

    Este tipo de errores ocurren cuando hilos diferentes tienen vistas inconsistentes de lo que deberían ser los mismos datos. Las causas de este tipo de errores son muchas y muy variadas y su análisis queda fuera de los alcances de este blog. Por ahora basta con saber que el programador debe tener consciencia de este tipo de errores para que pueda emplear una estrategia para anularlos.

    La clave para anular este tipo de errores de consistencia de memoria es entender una relación denominada "sucede antes" (happens-before). Dicha relación es simplemente una garantía de que las escrituras de memoria realizadas por una declaración específica, son visibles para otra declaración específica. Para visualizar mejor esto, considere lo siguiente:

int contador = 0;

. . . 

Hilo A: contador++;

. . . 

Hilo B: System.out.println(contador);

    Suponga que dicho contador es compartido por dos hilos A y B, y suponga también que A incrementa el contador y que poco después B imprime en la salida estándar el contador. El valor impreso por B puede ser 0 o 1, es decir: no hay garantía de que el cambio a contador por parte del hilo A sea visible para el hilo B, a menos de que el programador establezca una relación happens-before entre estas dos sentencias. La sincronización es una de las formas de crear este tipo de relación.

    Java proporciona dos formas de sincronización:

1. Métodos sincronizados.
2. Sentencias sincronizadas.
   

     Para que un método sea sincronizado, basta con añadir la palabra reservada synchronized a su definición, tal y como se muestra en el Ejemplo ContadorSincronizado. El hacer que los métodos sean sincronizados, tiene dos efectos para las instancias de la clase:

1. No es posible el traslape para dos invocaciones de métodos sincronizados que se realicen sobre el mismo objeto. Cuando un hilo está ejecutando un método sincronizado para un objeto determinado, todos los demás hilos que invoquen métodos sincronizados para el mismo objeto se bloquean, es decir, se suspende su ejecución, hasta que el primer hilo haya terminado.
   
2. Cuando un método sincronizado termina, automáticamente establece una relación happens-before para cualquier invocación subsecuente de un método sincronizado para el mismo objeto, lo que garantiza que los cambios al estado del objeto sean visibles para todos los hilos. 

    Los constructores no pueden ser sincronizados y no tendría sentido, porque sólo el hilo que crea el objeto debería tener acceso a él. De hecho esta situación se identifica como un error de sintaxis.

    Los métodos sincronizados habilitan una estrategia simple para prevenir la interferencia de hilos y los errores de consistencia de memoria. Como regla general podría decirse que: si un objeto es visible por más de un hilo, todas las lecturas o escrituras a las variables (atributos) del objeto deberían ser por métodos sincronizados, con excepción quizá de los atributos final (los cuales no pueden ser modificados una vez que el objeto ha sido construido).

    El Ejemplo PruebaContadorSincronizado muestra cómo podría utilizarse la clase ContadorSincronizado. Analice ambas clases y compárese con sus contra partes de la sección anterior.

Candados intrínsecos y sentencias sincronizadas.

    La sincronización se construye al rededor de una entidad conocida como candado intrínseco o candado de monitor (o simplemente monitor) misma que juega un rol fundamental en dos aspectos relacionados con la sincronización:

1. Hace cumplir el acceso exclusivo al estado del objeto (exclusión mutua).
2. Establece y garantiza la relación happens-before esencial para la visibilidad y coherencia (consistencia de memoria).
   

    Cada objeto tiene asociado un candado intrínseco (lo mismo que cada clase cuando se habla de métodos estáticos). Por convención, si un hilo necesita acceso exclusivo y consistente a los campos de un objeto, tiene que apropiarse de dicho candado antes de hacerlo y liberarlo al terminar.

    Mientras un hilo posea el candado intrínseco, ningún otro hilo puede adquirirlo por lo que se bloqueará. Por otro lado, cuando un hilo libera un candado intrínseco, se establece una relación happens-before entre dicha acción y cualquier adquisición subsecuente del mismo candado.

    Cuando un hilo invoca un método sincronizado, automáticamente adquiere el candado intrínseco para dicho objeto y lo libera cuando el hilo en cuestión termina de ejecutar el método, aun cuando la terminación se dé por una excepción no atrapada.

    En este sentido, sucede que no siempre conviene que todo el método esté sincronizado debido a que se merma la concurrencia (contención de hilos); en algunos casos conviene que se sincronice sólo un bloque de código, debido a que el método podría tener también sentencias que no necesariamente acceden a datos compartidos, o que acceden a datos compartidos distintos, en cuyo caso un enfoque basado en sentencias sincronizadas sería entonces más apropiado (consulte el Ejercicio 8 de los Ejercicios selectos).

    Aunque para el ejemplo que se ha venido desarrollando en esta entrada no tendría mucho sentido utilizar las sentencias sincronizadas, con la finalidad de mostrar su uso y equivalencia para este caso particular, se propone al lector la revisión, comparación y análisis del Ejemplo ContadorSincronizado2 así como su correspondiente clase de prueba del Ejemplo PruebaContadorSincronizado2.

Conclusión.

    Como conclusión general es importante resaltar la importancia de la sincronización al trabajar con hilos y recursos compartidos por éstos.

    De los ejemplos comentados es importante también enfatizar y no perder de vista que una clase tan simple como Contador, utilizada en un contexto de hilos compitiendo por acceso a los datos puede derivar, sin la debida sincronización, en un potencial desastre respecto a la consistencia de la memoria y la coherencia de los datos derivada de la interferencia de hilos.

    Por otro lado, conviene también el tener presente que un abuso de la sincronización, pueden incurrir en la nada deseable contención de hilos, haciendo que las potenciales ventajas de la concurrencia no sólo desaparezcan sino que sean absurdas.

    Finalmente aquí, como en otras tantas instancias, se manifiestan dos de esas importantes y perennes lecciones de vida:

1. "Las nuevas soluciones traen consigo nuevos problemas".
2. "Todo viene con su precio".
   

Pilas (implementación).

   La representación de una pila, como una secuencia de nodos, se muestra en la siguiente figura. Los detalles de su implementación se desarrollarán a continuación.

Abstracción de una pila como una secuencia de nodos.

 Pila primitiva.

   Esta sección describe la implementación de una pila primitiva. Se ha denominado de esta forma debido a que implementa una estructura de datos que almacena un tipo de dato primitivo: int.

   La definición de la clase fundamental para la implementación de la estructura de datos se muestra en el Ejemplo NodoPrimitivo. Los detalles de este tipo de implementación de clases autorreferidas se han discutido con anterioridad en la entrada Abstracción de estructuras de datos y no se repetirán aquí, por lo que se sugiere al lector que la revise nuevamente y se tome el tiempo necesario para comparar el Ejemplo NodoPrimitivo con el Ejemplo Nodo antes de continuar.

   La implementación de la estructura de datos pila se muestra en el Ejemplo PilaPrimitiva, y su explicación se centrará únicamente en los métodos push, pop, estaVacia e imprime.

   El método estaVacia (líneas 37-39) realiza una verificación bastante simple: si el tope de la pila es igual a null, regresa verdadero (está vacía), si no, regresa falso (existe al menos un elemento).

   El método push por su parte (líneas 18-23), recibe como argumento el elemento a insertar en la pila (elemento), y se apoya del método estaVacia y de los constructores para realizar la inserción:

• Si la pila está vacía (línea 19), se crea un nuevo nodo con el elemento correspondiente (línea 20) para el atributo dato, y null en su atributo siguiente.
• Si la pila no está vacía (línea 21), se crea un nuevo nodo con el elemento correspondiente para el atributo dato y con el tope actual en su atributo siguiente (línea 22). Así mismo, note que el tope es actualizado para hacer referencia al nodo recién creado.

   Ahora bien, observe que el método pop (líneas 26-34) posee una característica particular: el método lanza (throws) una excepción ExcepcionEDVacia (línea 26) lo cual quiere decir que, en determinadas condiciones, el método puede lanzar una excepción; para el caso del método pop, la condición consiste en intentar eliminar un elemento de la pila cuando ésta está vacía.

   La excepción ExcepcionEDVacia definida en el Ejemplo ExcepcionEDVacia es en realidad bastante simple, ya que delega toda la responsabilidad a RuntimeException que es la clase de la que deriva, y lo único que hace es establecer un identificador para la excepción a través de sus constructores, los cuales en realidad utilizan el constructor de la super clase (clase padre) a través de la cláusula super. Es importante que el lector recuerde esta excepción, ya que será la excepción que utilizarán todas las estructuras de datos que se implementan en el blog.

   Ahora bien, cuando el programador se enfrenta a la necesidad de lanzar una excepción cabe la pregunta ¿y de qué tipo? Se puede utilizar una excepción escrita por alguien más o se puede hacer una propia. Se debería hacer clases de excepción propias cuando se responda de manera afirmativa a alguna de las siguientes preguntas, de otra forma, debería usarla una excepción escrita por alguien más (vea Creating Exception Classes):

• ¿Necesita un tipo de excepción que no está representada en el API de Java?
• ¿Sus usuarios se verán beneficiados si pueden diferenciar sus excepciones de aquellas lanzadas por clases escritas por alguien más?
• ¿Su código lanza más de una excepción relacionada?
• Si utiliza una excepción escrita por alguien más, ¿sus usuarios tendrán acceso a esas excepciones?
• ¿Su paquete de clases debería ser independiente y auto contenido?

   Continuando con el Ejemplo PilaPrimitiva, el método pop verifica (línea 27) si la pila está vacía, si lo está, crea y lanza la excepción correspondiente (línea 28); en caso contrario, recupera el dato almacenado (línea 30), y desecha el nodo correspondiente al hacer que el tope haga ahora referencia al elemento siguiente del tope actual (línea 31), para finalmente regresar el dato recuperado (línea 33). En Java no hay una eliminación o liberación explícita de memoria, dicha labor es delegada al recolector de basura el cual se encarga, grosso modo, de identificar aquellos objetos que no estén siendo referidos para entonces liberar la memoria que utilizan.

   Por último, en el método imprime (líneas 42-57), si la estructura de datos está vacía (línea 43), se reporta (línea 44); en caso contrario, se realiza un recorrido por todos los nodos de la estructura para imprimir su contenido (líneas 47-54).

   La clase de prueba para la pila primitiva del Ejemplo PilaPrimitiva, se presenta en el Ejemplo PruebaPila. Observe cómo en la línea 6 se crea la pila y se utiliza un constructor sin argumentos.

   Las líneas 9-12 realizan la inserción en la pila de los números del cero al nueve; por cada inserción se imprime todo el contenido de la pila, como se muestra en la siguiente figura:

Ejemplo de inserción de elementos en la pila primitiva. Se muestra la salida del Ejemplo PruebaPila.

    Por otro lado, las líneas 15-24 realizan la eliminación de los elementos de la pila. Dicho fragmento de código intenta eliminar once elementos (líneas 17-18) de la pila (recuerde que sólo fueron insertados diez elementos, por lo que al intentar eliminar el décimo primero, se generará la excepción ExcepcionEDVacia), y dado que el método pop puede lanzar una excepción, el código involucrado en la eliminación debe estar dentro de una cláusula try-catch-finally, la cual permite atrapar (cachar) las excepciones que un método pudiera lanzar.

   Si se genera un excepción ExcepcionEDVacia, ésta es atrapada y el flujo de control se envía al ámbito de la cláusula catch en donde se realiza el correspondiente tratamiento de la excepción. Para el caso del Ejemplo PruebaPila el manejo de la excepción consiste únicamente en imprimir la secuencia de eventos (en forma de pila) que dieron lugar a la excepción; sin embargo, es importante aclarar que el manejo de una excepción puede ser tan elaborado como en un momento dado se requiera.

   La salida correspondiente a la eliminación de elementos de la pila primitiva, se muestra en la siguiente figura:

Ejemplo de eliminación de elementos en la pila primitiva. Se muestra la salida del Ejemplo PruebaPila.

Pila genérica.

   Esta sección generaliza la implementación de una pila de tal forma que la estructura de datos tenga la capacidad de almacenar objetos genéricos; es decir, objetos de cualquier clase.

   Como primer paso, es preciso que el lector se tome el tiempo que considere necesario para comparar el Ejemplo NodoPrimitivo discutido en la sección anterior, con el Ejemplo NodoG. Es importante resaltar que, aunque distintos, ambos ejemplos son esencialmente equivalentes.

La primera diferencia que salta a la vista, además del nombre de la clase, es la notación <T>. Dicha notación se utiliza en Java para especificar que la clase gestiona objetos genéricos, es decir, que el tipo o la clase de los objetos que almacena no está especificada en la definición de la misma, sino que se especifica en el momento de la instanciación del objeto (observe la línea 6 del Ejemplo PruebaPilaGenerica).

   La línea 7 del Ejemplo NodoG define que la clase del atributo dato es T, es decir, un genérico, y por lo tanto el atributo siguiente es una referencia a un objeto que almacena objetos genéricos.

   Observe cómo ahora los constructores y los métodos de tipo set reciben como argumentos objetos genéricos T (líneas 10, 14 y 19), y referencias a objetos que a su vez almacenan objetos genéricos (líneas 14 y 27); mientras que los métodos de tipo get regresan genéricos (línea 23), o referencias a objetos que almacenan objetos genéricos (línea 31).

   Ahora bien, las consideraciones hechas para el Ejemplo NodoG respecto a los genéricos, son las mismas que debe tomar en cuenta para el Ejemplo Pila, por lo que una vez más se pide encarecidamente al lector que compare este último con el Ejemplo PilaPrimitiva discutido en la sección anterior tomando en consideración lo explicado hasta este momento para los genéricos.

   Observe que en ninguna parte del Ejemplo Pila se hace explícita una clase específica para el genérico T, por lo que también aquí se hace una gestión de genéricos en directa relación con los genéricos utilizados en el Ejemplo NodoG.

   En resumen, la clase NodoG del Ejemplo NodoG define nodos que almacenan objetos genéricos (nodos genéricos), los cuales son utilizados de manera conveniente por la clase Pila del Ejemplo Pila para conformar una estructura de datos dinámica que almacena objetos o nodos genéricos en forma de pila.

   El Ejemplo PruebaPilaGenerica muestra la clase de prueba para la pila genérica del Ejemplo Pila. La línea más importante del Ejemplo PruebaPilaGenerica es la línea 6, ya que es en ella en donde finalmente se define la clase de objetos que contendrá (almacenará) la pila: Integer.

   Consulte la sección Genéricos de la entrada Ejemplos selectos de transición para ampliar un poco más la información y los detalles acerca de los genéricos en Java. En el Ejemplo PilaC se muestra la implementación alternativa de una pila utilizando un ArrayList del API de Java; mientras que en el EjemploPruebaPilaC se presenta su correspondiente clase de prueba. Adicionalmente, se proporcionan al lector dos ejemplos adicionales que utilizan colecciones (estructuras de datos) del API: Stack y ArrayDeque (Deque); tómese el tiempo de estudiarlos y revisar la información correspondiente en el API.

   Finalmente, asegúrese de comprobar que la salida del Ejemplo PruebaPilaGenerica corresponde, en esencia, con la salida del Ejemplo PruebaPila para la inserción de datos (push), y que lo correspondiente ocurre también para la eliminación de elementos (pop).

ABB (eliminacion).

   La eliminación de un elemento de un árbol binario de búsqueda consiste básicamente en, dado un elemento a eliminar:

• Identificar si dicho elemento se encuentra en el ABB (identificación de duplicados), si no existe, se podría regresar un valor que indique dicha situación y dejar el ABB sin cambios.
• Si el elemento existe en el ABB, entonces existen tres posibilidades:
1. Si el elemento está almacenado en un nodo hoja, la eliminación es directa.
2. Si el elemento está almacenado en un nodo con un solo hijo, el hijo sustituye al padre y se elimina el nodo correspondiente.
3. Si el elemento está almacenado en un nodo con dos hijos, la regla que se adoptará será la de sustituirlo por el hijo más a la derecha del subárbol izquierdo (el mayor de los menores). También existe la regla simétrica del hijo más a la izquierda del subárbol derecho (el menor de los mayores), pero no se utilizará en el blog, por convención, se utilizará la primera.

Observe también que con el proceso de eliminación descrito con anterioridad:

1. Se conserva la relación de orden que debe mantener un ABB.
2. Se podría incurrir en un intento de eliminación de un ABB vacío lo cual, desde el punto de vista de la implementación generaría una excepción, por lo que sería conveniente tener una forma de verificar dicha situación.

Diagrama de clases UML para un ABB con eliminación (Java).

 

 

Diagrama de clases UML para un ABB con eliminación (C++).

 

    En función de lo anterior, los diagramas de clases UML de las figuras anteriores complementan al presentado en la entrada ABB (representación y diseño). Observe que se han realizado las siguientes modificaciones en la clase ABB:

1. La incorporación de un atributo privado numérico (n) con la finalidad de llevar el control del número de elementos insertados en el ABB. Respecto a la implementación de éste, se debe considerar:
1. Inicializar explícitamente dicho atributo a cero en el constructor.
2. Proporcionar únicamente el método de tipo get para dicho atributo: obtenN( ) (obten_n( )).
2. La adición del método elimina, el cual realiza la eliminación de elemento si éste existe en el ABB devolviendo true como caso de éxito; en caso contrario, el método regresa false. Respecto a la implementación de este método, se debe considerar:
1. Seguir las reglas de eliminación descritas con anterioridad.
2. Lanzar la excepción ExcepcionEDVacia (excepcion_ED_vacia) ante un intento de eliminación de un ABB vacío, tal y como lo describe la relación que se muestra en los diagramas de clases.
3. La incorporación del método estaVacio (esta_vacio( )), el cual regresa true si el ABB está vacío y false en caso contrario.

   La implementación de las clases descritas en el diagrama UML correspondiente al lenguaje que utilice como medio, así como su correspondiente prueba, se dejan como ejercicio para el lector.

Árbol binario de búsqueda (ABB).

   Un árbol binario es una estructura de datos sumamente útil en muchos aspectos, en particular, cuando deben tomarse decisiones en dos sentidos en cada punto de un proceso determinado.

   Con base en lo anterior, suponga que por alguna razón se desea encontrar todos los duplicados de una secuencia de números. Para ello, considere lo siguiente:

1. El primer número de la secuencia se coloca en un nodo que se ha establecido como la raíz de un árbol binario, cuyos subárboles izquierdo y derecho estarán inicialmente vacíos.
2. Cada número sucesivo en la secuencia se compara con el número que se encuentra en la raíz del árbol binario. En este momento, se tienen tres casos a considerar:
1. Si coincide, se tiene un duplicado.
2. Si es menor, se examina el subárbol izquierdo.
3. Si es mayor, se examina el subárbol derecho.
3. Si alguno de los subárboles esta vacío, el número no es un duplicado y se coloca en un nodo nuevo en dicha posición del árbol binario.
4. Si el subárbol correspondiente no está vacío, se compara el número con la raíz del subárbol en cuestión, y se repite todo el proceso nuevamente con dicho subárbol.

   Un árbol binario de búsqueda (ABB) es un árbol binario que no tiene valores duplicados en los nodos, y además, tiene las siguientes características:

1. Los valores en cualquier subárbol izquierdo son menores que el valor en su nodo padre.
2. Los valores en cualquier subárbol derecho son mayores que el valor en su nodo padre.

   Tome en cuenta que un ABB es un árbol binario, pero un árbol binario no es necesariamente un ABB. En este sentido, todo lo que se ha dicho y definido para árboles binarios, es aplicable también a los árboles binarios de búsqueda.

Operaciones primitivas.

   Respecto a las operaciones primitivas, se definen cuatro operaciones primitivas para un ABB:

• inserta: inserta un nuevo nodo al árbol binario de búsqueda. La inserción se realiza de manera ordenada respecto del elemento a insertar, por lo que debe existir una relación de orden definida para el conjunto de datos al que pertenece dicho elemento.

   En resumen, la operación inserta de manera ordenada a elemento en el ABB cuando el objeto abb recibe el mensaje correspondiente, es decir: abb.inserta(elemento).

• recorre en preorden: recorre el ABB no vacío en orden previo, de tal forma que cuando el objeto abb recibe el mensaje: abb.recorrePreorden( ) se imprime en la salida estándar el recorrido en orden previo de abb.

• recorrido en orden: recorre el árbol binario de búsqueda no vacío en orden, de tal forma que cuando el objeto abb recibe el mensaje: abb.recorreEnorden( ) se imprime en la salida estándar el recorrido en orden de abb.

   Note cómo un recorrido en orden, como su nombre lo indica, imprime en la salida estándar los elementos almacenados en el árbol ordenados de manera ascendente.

• recorrido en postorden: recorre el ABB no vacío en orden posterior, de tal forma que cuando el objeto abb recibe el mensaje: abb.recorrePostorden( ) se imprime en la salida estándar el recorrido en orden posterior de abb.

   Para el caso de un árbol binario de búsqueda, también serían deseables otras operaciones, como aquellas que se definieron para los árboles binarios: primitivas, operaciones adicionales que podrían ser útiles y recorridos inversos por ejemplo (vea las entradas Árboles binarios (operaciones primitivas) y Árboles binarios (recorridos)).

   En este sentido, es importante resaltar que siempre que una operación no viole la relación de orden intrínseca a los ABB, es factible de ser implementada y que la decisión final respecto a su implementación estará en directa función de si ésta tiene o no sentido en la aplicación que se esté desarrollando.

Listas doblemente enlazadas.

   Aunque una lista enlazada circular tiene ventajas sobre una lista simplemente enlazada (vea la entrada Listas circulares), también tiene algunas desventajas:

• No es posible recorrer la lista enlazada circular hacia atrás (o hacia la izquierda); es decir, sólo puede recorrerse en un sentido.
• Dada una referencia a un nodo determinado de la lista enlazada circular, no es posible eliminar dicho nodo utilizando únicamente dicha referencia (¿Por qué?).

   En este sentido, una estructura de datos conveniente para subsanar dichas desventajas es precisamente, la lista doblemente enlazada.

Definición, primitivas y representación.

   Una lista doblemente enlazada es una colección lineal de nodos auto referidos en donde cada nodo tiene dos referencias:

1. Una referencia al sucesor del nodo actual (siguiente).
2. Una referencia al antecesor del nodo actual (anterior).

   La representación de una lista doblemente enlazada se muestra en la figura (a). Observe cómo al igual que en una lista enlazada, una lista doblemente enlazada puede ser también doblemente enlazada circular (figura (b)). Esta última, sigue también las mismas consideraciones que se hicieron en su momento para una lista enlazada circular.

(a) Abstracción de una lista doblemente enlazada.

(b) Abstracción de una lista doblemente enlazada circular.

   Adicionalmente, las operaciones primitivas para una lista doblemente enlazada son exactamente las mismas que para una lista simplemente enlazada, por lo que no se repetirán aquí.

   Por otro lado, los diagramas de clases UML para los lenguajes Java y C++ de una lista doblemente enlazada se presentan a continuación. Los diagramas complementan la definición de la estructura de datos a través de su correspondiente diseño de clases:

Diagrama de clases UML para una lista doblemente enlazada (Java).

 

Diagrama de clases UML para una lista doblemente enlazada (C++).

 

    Por ultimo, note que dichos diagramas de clases son sustancialmente distintos de los que en general se han utilizado hasta ahora para el diseño de las anteriores estructuras de datos y que, exceptuando la clases ExcepcionEDVacia (excepcion_ED_vacia), tanto las clases ListaDoble (lista_doble) como las clases NodoDobleG (Nodo_doble) han sufrido cambios significativos. Consulte la sección de ejercicios correspondiente para obtener más detalles al respecto.

Listas (definición).

Definición.

   Una lista es, en general, una colección lineal de elementos; mientras que una lista enlazada es, en el contexto que nos compete, una colección lineal de objetos (nodos) auto referidos.

   Se tiene acceso a una lista enlazada por medio de una referencia al primer nodo de la lista. Aunque resulta más conveniente, por las características inherentes a la implementación de la estructura de datos, que existan dos referencias a la misma: una que refiera el inicio de la lista, y otra que refiera el fin de la lista. El acceso a los nodos intermedios subsecuentes, se realiza a través del enlace o referencia que contiene cada uno de ellos.

   Una lista enlazada es más conveniente que un arreglo estático por ejemplo, cuando no es posible determinar con anticipación el número de elementos a almacenar en la estructura de datos.

   Las listas enlazadas son dinámicas, por lo que se puede aumentar o disminuir a discreción el número de elementos de la lista. Un aspecto importante a considerar respecto a las listas enlazadas es que pueden, simplemente por conveniencia, mantenerse en orden (tome en cuenta el lector que, aunque esto puede resultar sumamente conveniente, no es una característica inherente a la estructura de datos) insertando cada nuevo elemento en el punto apropiado dentro de la lista enlazada.

   Normalmente los nodos de las listas enlazadas no están almacenados en forma contigua en la memoria; sin embargo, lógicamente los nodos aparecen como contiguos. Esto obedece a su representación física y lógica respectivamente.

   Operaciones primitivas.

   Se definen cinco operaciones primitivas sobre una lista enlazada (entre paréntesis aparece la definición para C++):

1. La operación insertaAlInicio (inserta_al_inicio) agrega un elemento al inicio de la lista enlazada.
2. La operación insertaAlFinal (inserta_al_final) agrega un elemento al final de la lista enlazada.
3. La operación eliminaDelInicio (elimina_del_inicio) elimina un elemento del inicio de la lista enlazada.
4. La operación eliminaDelFinal (elimina_del_final) elimina un elemento del final de la lista enlazada.
5. La operación estaVacia (esta_vacia) regresa verdadero o falso, dependiendo de si la lista enlazada contiene o no elementos respectivamente.

   Tome en cuenta que los elementos de una lista enlazada podrían ser insertados en cualquier parte, y que en función de ellos, podrían ser definidas más operaciones sobre una lista enlazada, por lo que el mecanismo de inserción estará en función directa de las necesidades específicas para la implementación de la estructura de datos.

  En este sentido, si se desea mantener una lista enlazada ordenada por ejemplo, se deberá ir recorriendo la lista enlazada de manera secuencial, hasta encontrar el lugar apropiado para la inserción de cada uno de los elementos que la conformarán.

   Por otro lado, la eliminación de un elemento particular, podría consistir en primer lugar, en la localización de dicho elemento dentro de la lista enlazada. Si existe, se procede a su correspondiente eliminación; en caso contrario, se debería indicar que el elemento que se está intentando eliminar, no existe dentro de la estructura de datos.

   Representación.

   Como se mencionó en la sección anterior, el acceso a una lista enlazada se realiza por al menos una referencia al primer nodo de dicha lista enlazada. Aunque por otro lado, resulta más conveniente, por las características inherentes a la implementación de la estructura de datos, que existan dos referencias hacia la misma: una que refiera el inicio de la lista enlazada, y otra que refiera el fin de la lista enlazada.

   El acceso a los nodos intermedios subsecuentes se realiza a través del enlace o referencia que contiene cada uno de ellos. Por regla convencional, para marcar el fin de la lista enlazada, el enlace al siguiente nodo en el último nodo de la lista enlazada se establece a null (nullptr).

   La representación mostrada en la siguiente figura es una abstracción de la implementación que se realizará en una entrada posterior. También coincide con la representación lógica de una lista enlazada.

Abstracción de una lista enlazada como una secuencia de nodos.

 

    Observe cómo la figura anterior luce muy similar a la figura correspondiente a las colas de espera, ya que también hace uso de dos referencias: inicio y fin, mismas que denotan respectivamente el primero y el último de los elementos almacenados en la lista enlazada. Note también que, para el caso de un solo elemento, dichas referencias harán referencia, valga la redundancia, al mismo nodo.

   Por otro lado, los diagramas de clases UML que se presentan a continuación, muestran el diseño de clases de la lista enlazada que se desea implementar. Dicho diseño complementa, en conjunción con la definición hecha con anterioridad, el concepto de lista enlazada.

Diagrama de clases UML para la lista enlazada (Java).

  

Diagrama de clases UML para la lista enlazada (C++).

 

    Los diagramas de clases UML de las figuras anteriores muestran también la relación que existe entre las clases más importantes que se involucrarán durante la implementación de la lista enlazada. Tome el lector el tiempo que considere necesario para revisar, analizar y comprender dichos diagramas de clases antes de avanzar a la implementación correspondiente.

Colas de prioridad.

   La cola de prioridad es una estructura de datos en la que el ordenamiento intrínseco de los elementos, determina el resultado de la aplicación de sus operaciones básicas o primitivas.

   En este sentido, existen dos tipos de colas de prioridad:

1. Cola de prioridad ascendente.
2. Cola de prioridad descendente.

   Ambas estructuras de datos redefinen la forma de operación convencional respecto de una cola de espera, por lo que serán estudiadas de manera separada.

Cola de prioridad ascendente.

   La cola de prioridad ascendente es un tipo de estructura de datos en el que la inserción de los elementos se realiza de manera convencional, pero la eliminación se realiza en base al menor de los elementos almacenados en ella. Para que ésto sea posible, los elementos que almacena la estructura de datos deben tener una relación de orden; es decir, deben poseer algún mecanismo que permita compararlos entre sí.

   La siguiente figura muestra la relación de clases en UML para una cola de prioridad ascendente con la redefinición o sobre escritura (override) del método elimina. Observe cómo se ha instrumentado la redefinición de dicho método por medio del mecanismo de la herencia, y que las relaciones previamente existentes se conservan (compare con el diagrama de clases presentado para las colas de espera en la entrada Colas de espera (definición)).

 

Diagrama de clases UML para una cola de prioridad ascendente con la redefinición (override) del método elimina.

    Otro tipo de representación para la cola de prioridad ascendente, consiste en mantener ordenados los elementos de manera ascendente durante la inserción y conservar la operación de eliminación de la forma convencional. Dicha representación se expresa en UML como se muestra en la siguiente figura:

 

Diagrama de clases UML para una cola de prioridad ascendente con la redefinición (override) del método inserta.

    En resumen, en una cola de prioridad ascendente los elementos se recuperan (eliminan) en orden ascendente respecto de la relación de orden que guarden entre sí. Ahora bien, para objetos con una relación de orden inherente a ellos, como un objeto de la clase Integer o de la clase Float por ejemplo, la comparación es posible pero, ¿qué ocurre con objetos de la clase String del API de Java, o con las clases Persona y Cientifico definidas en la entrada POO (herencia) por ejemplo?

   Implementación.

   En la orientación a objetos existe un concepto relacionado con la herencia: la herencia múltiple. La herencia múltiple básicamente es la capacidad de una clase de heredar los atributos y métodos de más de una clase; sin embargo, el lenguaje de programación Java no incluye en su gramática dicha capacidad, aunque por otro lado, incorpora un mecanismo que permite que una clase se comprometa, a través de una especie de contrato, a implementar en métodos las operaciones declaradas o establecidas en una interfaz (interface). La interfaz Comparable del API de Java compromete u obliga a las clases que la implementan, a establecer una relación de orden entre los objetos que la implementen. Dicha relación de orden es arbitraria y está en función únicamente del interés o de las necesidades específicas de la clase en cuestión.

   Para ilustrar lo anterior, considere el Ejemplo ColaAscendente el cual implementa una cola de prioridad ascendente sobre escribiendo o redefiniendo (override) el método inserta tal y como se propone en el diagrama de clases UML de la figura anterior. Note el uso de la interfaz Comparable. Observe con detenimiento la línea 6 la cual, en el contexto de lo anterior, podría interpretarse de la siguiente manera:

La clase ColaAscendente es una subclase, clase hija o clase derivada de la clase Cola, gestiona objetos genéricos T que definan o establezcan una relación de orden a través de la implementación del método compareTo declarado en la interfaz Comparable.

   Observe que el mensaje o la invocación del método compareTo ocurre en la línea 21 del Ejemplo ColaAscendente, y que la idea general del método inserta (líneas 15-35) consiste en recorrer la secuencia de nodos (líneas 21-24) mientras haya nodos por procesar y no se haya encontrado el lugar correspondiente para el elemento a insertar (línea 21). En este sentido, el método compareTo compara el objeto receptor del mensaje con el objeto proporcionado como argumento; dicho método regresa uno de tres posibles valores (consulte en el API de Java la interfaz Comparable para ampliar y complementar la información al respecto):

1. Un entero negativo (< 0) si el objeto receptor del mensaje es menor que el objeto proporcionado como argumento.
2. Cero (0) si el objeto que recibe el mensaje es igual al objeto proporcionado como argumento.
3. Un entero positivo (> 0) si el objeto receptor del mensaje es mayor que el objeto proporcionado como argumento.

   Es importante que el lector comprenda que el método compareTo es definido en la clase que quiera establecer una relación de orden para sus objetos, es decir, los objetos de la clase genérica T deberán tener la definición (código) de dicho método.

   Continuando con la explicación del método inserta del Ejemplo ColaAscendente, note que el método hace uso de objetos auxiliares (líneas 16, 18 y 19), para poder realizar el ajuste de las referencias correspondientes en las líneas 26-34. Aquí cabe mencionar que, aunque dichos objetos pudieron haber sido definidos como atributos de la clase ColaAscendente, en realidad no representan una característica o cualidad inherente a los objetos que se deriven de dicha clase, sino que más bien son entidades útiles para la manipulación de la estructura de datos dentro del método, por lo que de ser atributos, aunque la implementación trabajaría de la misma manera, el enfoque sería inapropiado, esto es: sería un diseño inadecuado. El análisis y los detalles del ajuste de las referencias de las líneas 22-23 y 26-34 se dejan como ejercicio para el lector, a quien se insta amablemente a comprender completamente su funcionamiento antes de continuar.

   Por último, la clase de prueba para la cola de prioridad ascendente del Ejemplo ColaAscendente se muestra en el Ejemplo PruebaColaAscendente.

   Tómese el lector el tiempo que considere necesario para comparar el Ejemplo PruebaColaAscendente con el Ejemplo PruebaCola y advierta que son, esencialmente iguales.

   Note también que los objetos a almacenar en la cola de prioridad ascendente son objetos de la clase Integer (línea 6) por lo que, para que no haya ningún problema en la compilación, dicha clase deberá tener la implementación (implements) de la interfaz Comparable, y en consecuencia, la definición del método compareTo. En este sentido, se invita al lector para que realice dicha comprobación en el API de Java antes de compilar y ejecutar el Ejemplo PruebaColaAscendente.

   Con base en lo anterior, todos los objetos que se deseen almacenar en la cola de prioridad ascendente definida en el Ejemplo ColaAscendente, deberán implementar dicha interfaz, así como definir el comportamiento requerido (código) por el método compareTo.

   Por último, observe que a diferencia del Ejemplo PruebaCola, el Ejemplo PruebaColaAscendente inserta intencionalmente nueve números de manera desordenada, ya que la implementación de cola de prioridad propuesta (Ejemplo ColaAscendente) los mantiene ordenados dentro de la estructura de datos, mientras que la eliminación (líneas 18-26) se realiza de manera convencional. La salida del Ejemplo PruebaColaAscendente se muestra en la siguiente figura:

Salida del Ejemplo PruebaColaAscendente. 

 

Cola de prioridad descendente.

   La cola de prioridad descendente es análoga en lo general a la cola de prioridad ascendente.

   La cola de prioridad descendente es un tipo de estructura de datos en el que la inserción de los elementos se realiza también de la manera convencional, pero la eliminación se realiza en base al mayor de los elementos almacenados en ella. Al igual que para la cola de prioridad ascendente, para que ésto último sea posible, es necesario que los elementos que almacena la estructura de datos tengan una relación de orden, es decir, es preciso que incorporen algún mecanismo que les permita compararlos entre sí.

   La siguiente figura muestra la relación de clases en UML para una cola de prioridad descendente con la redefinición o sobre escritura (override) del método elimina. Una vez más, note cómo se ha instrumentado la redefinición de dicho método por medio del mecanismo de la herencia, y que las relaciones (compare con el diagrama de clases presentado para las colas de espera en la entrada Colas de espera (definición)) previamente existentes se conservan.

 

Diagrama de clases UML para una cola de prioridad descendente con la redefinición (override) del método elimina.

    Al igual que para la cola de prioridad ascendente, otro tipo de representación para la cola de prioridad descendente consiste en mantener ordenados los elementos de manera descendente durante la inserción y conservar la operación de eliminación de la forma convencional, tal y como lo sugiere la representación del diagrama de clases UML de la siguiente figura:

 

Diagrama de clases UML para una cola de prioridad descendente con la redefinición (override) del método inserta.

    Por último, recuerde que en una cola de prioridad descendente los elementos se recuperan (eliminan) en orden descendente respecto de la relación de orden que guardan entre sí. Los detalles de la implementación, se dejan como ejercicio para el lector.

Colas de espera (definición).

Definición.

   Una cola de espera o simplemente cola, es un conjunto ordenado de elementos del que se pueden eliminar dichos elementos de un extremo (llamado inicio de la cola), y en el que pueden insertarse elementos en el extremo opuesto (llamado fin de la cola).

   El primer elemento insertado en una cola es el primer elemento en ser eliminado, mientras que el último elemento insertado es el último en ser eliminado. Por esta razón, se dice que una cola es una estructura de datos de tipo FIFO (First In First Out).

   En el mundo real abundan ejemplos de este tipo de estructuras:

• Líneas aéreas.
• Líneas de autobuses.
• Colas de espera en los supermercados.
• Colas de espera en los bancos.
• Etcétera, etcétera, etcétera.

   La siguiente figura muestra en (a) una representación de una cola de espera que permite visualizar los elementos almacenados en la misma:

Inserción y eliminación de elementos en una cola de espera.

   La eliminación de uno de los elementos (A) se muestra en la figura anterior en (b), mientras que la inserción de los elementos D y E se muestra en (c). Observe también cómo las referencias al inicio y fin de la cola son modificadas en cada inserción y eliminación respectivamente.

Operaciones primitivas.

   Se definen tres operaciones primitivas sobre una cola de espera:

1. La operación inserta agrega un elemento en la parte final de la cola. También se dice que esta operación forma o encola un elemento en la estructura de datos.
2. La operación elimina suprime un elemento de la parte inicial de la cola. Esta operación despacha o atiende al elemento que se encuentra al inicio de la cola.
3. La operación estaVacia (esta operación fue definida como opcional o deseable para la pila. Para el caso de la cola dicha operación es ahora una primitiva, por lo que su implementación es requerida) regresa verdadero o falso dependiendo de si la cola de espera contiene o no elementos respectivamente.

   Una operación deseable para una cola de espera, sería la de imprimir todos los elementos de la cola, la cual se denotará como imprime.

Representación.

   La representación mostrada en la siguiente figura es una abstracción de la implementación que se realizará en la entrada correspondiente a la implementación:

Abstracción de una cola de espera como una secuencia de nodos.

 

    Observe cómo la figura anterior luce muy similar a la de la pila. Sin embargo, esta figura muestra el uso de dos referencias: inicio y fin, las cuales denotan, respectivamente, el primero y último de los elementos almacenados en la cola de espera. Note también que, para el caso de un solo elemento, dichas referencias harán referencia, valga la redundancia, al mismo nodo.

   Por otro lado, los diagramas de clases UML siguientes muestran el diseño de clases para la cola de espera que se desea implementar. Dicho diseño complementa, en consecuencia, la definición de dicha estructura de datos. A su vez, los diagramas de clases muestran también la relación que existe entre las clases más importantes que se involucrarán durante la implementación de la estructura de datos en cuestión.

Diagrama de clases UML para la cola de espera (Java).

Diagrama de clases UML para la cola de espera (C++).

    En este sentido valdría la pena hacer una aclaración: lo más deseable sería generar un diagrama de clases que representara la idea general del diseño de la estructura de datos con independencia del lenguaje de implementación; sin embargo, con la finalidad de enfatizar las diferencias a considerar en la implementación, se ha optado por manejar dos diagramas de clases que, aunque esencialmente iguales, especifican diferencias sutiles con respecto a los lenguajes de programación utilizados para los ejemplos.

Pilas (definición y operaciones primitivas).

Definición.

   La pila es un objeto dinámico en constante cambio.

   Una pila es un conjunto ordenado de elementos en el cual se pueden insertar y eliminar elementos únicamente por un extremo: el tope de la pila.

   La característica más importante de una pila es que el último elemento insertado en ella es el primero en eliminarse, mientras que el primero que fue insertado es el último en eliminarse. Por esta razón se dice que una pila es una estructura de datos de tipo LIFO (Last In First Out).

   El proceso de inserción y eliminación de elementos puede observarse en la siguiente figura en donde se muestra, por medio de una flecha, la representación del tope de la pila. Observe cómo con cada inserción o eliminación se modifica el tope de la pila.

Crecimiento y decrecimiento de una pila.

 

    La representación mostrada en la figura anterior permite visualizar todos los elementos de la pila, sin embargo, es importante señalar que en un momento dado únicamente se tiene acceso al elemento que está siendo referido por el tope de la pila, los demás elementos permanecen ocultos, tapados por decirlo de alguna manera, por el conjunto de elementos que se encuentran encima de cada uno de ellos, con excepción del que está en el tope de la pila.

Operaciones primitivas.
   Las operaciones primitivas o fundamentales definidas sobre una pila son la inserción (push) y la eliminación (pop).

1. El comportamiento definido para la operación push consiste en insertar un nuevo elemento en la pila, mismo que constituirá el nuevo tope de la pila.
2. El comportamiento definido para la operación pop elimina el elemento referido por el tope de la pila modificando en consecuencia el tope de la pila. El nuevo tope de la pila se refiere ahora al elemento (si existe) que fue insertado inmediatamente antes que el elemento eliminado.

   Existen otras operaciones útiles al usar pilas, como por ejemplo, antes de aplicar la operación pop a una pila, sería conveniente verificar que la pila no esté vacía (operación ¿Está vacía?).

   Otro comportamiento deseable sería la operación "ojeada" (peek), la cual hecha un vistazo al elemento que se encuentra en el tope de la pila y lo regresa pero no lo elimina.

   Las operaciones push, pop y peek, son muy comunes para la estructura de datos pila, por lo que se recomienda conservar dichos nombres en la implementación.