Implementación de listas (C++).

   La implementación de una lista enlazada se muestra en el Ejemplo lista. Note que con base en lo descrito en el diagrama de clases UML de la siguiente figura y a lo definido en el código fuente de dicho ejemplo, se hace uso de las clases Nodo y excepcion_ED_vacia, mismas que ya han sido explicadas y analizadas en secciones anteriores, por lo que ya no se presentan ni se describen aquí (si el lector desea una descripción de dichas clases, refiérase a la sección Pilas (implementación)).

Diagrama de clases UML para una lista enlazada.

 

    Adicionalmente a lo anterior, el Ejemplo lista muestra la definición de los métodos esta_vacia e imprime, los cuales también han sido ya presentados y descritos en ejemplos anteriores; de hecho, se han reutilizado aquí con toda la intención, ya que el comportamiento representado por ellos cumple con los requerimientos necesarios para una lista enlazada.

   Con base en lo anterior, únicamente se describirán los siguientes métodos:

• inserta_al_inicio (líneas 105-111) como su nombre lo indica, el método inserta elementos en la parte referida por inicio

   Si la estructura de datos está vacía (línea 107), se crea el nodo (objeto) con el elemento correspondiente, el cual será referido tanto por inicio como por fin (línea 108). En caso contrario, se inserta el elemento siguiendo la misma idea que se utilizó para la pila (líneas 109-110).

• inserta_al_final (líneas 113-121) como su nombre lo indica, el método inserta elementos en la parte referida por fin.

   Si la estructura de datos está vacía (línea 115), se crea el nodo (objeto) con el elemento correspondiente, el cual será referido tanto por inicio como por fin (línea 116; observe que hasta aquí se hace exactamente lo mismo que para el método anterior: inserta_al_inicio). En caso contrario, se inserta el elemento siguiendo la misma idea que se utilizó para la cola de espera (líneas 117-120).

• elimina_del_inicio (líneas 124-140) como su nombre lo indica, este método elimina elementos en la parte referida por inicio.

   Si la estructura de datos está vacía (línea 126), se lanza la excepción excepcion_ED_vacia (línea 127). En caso contrario, se procede a la eliminación del elemento de manera análoga a como se hizo para la cola de espera (líneas 129-139).

• elimina_del_final (líneas 142-164) como su nombre lo indica, elimina elementos en la parte referida por fin.

   Si la estructura de datos está vacía (línea 144), se lanza la excepción excepcion_ED_vacia (línea 145). En caso contrario, se procede a la eliminación del elemento correspondiente, para ello:

1. Si sólo existe un elemento (línea 151), se actualizan las referencias (línea 152). En caso contrario (línea 153):
2. Se realiza un recorrido (líneas 154-156) por la estructura de datos desde el inicio (línea 154), para determinar el elemento anterior al referido por fin (¿Por qué?).
3. Se actualizan las referencias correspondientes (líneas 158-159).

   El programa principal se muestra en la función main (209-237). Note que en general se insertan diez números enteros, y que para los números pares se utiliza el método inserta_al_inicio, mientras que para los números impares se utiliza el método inserta_al_final.

 

    Para el caso de la eliminación se realiza lo correspondiente pero se ha modificado el tipo de eliminación aplicado, es decir, primero se eliminan los números impares (insertados al final) y de manera intercalada los números pares (insertados al inicio).

   Finalmente, se muestra a continuación la salida del ejemplo en cuestión:

La Lista genérica es: 0
La Lista genérica es: 0 1
La Lista genérica es: 2 0 1
La Lista genérica es: 2 0 1 3
La Lista genérica es: 4 2 0 1 3
La Lista genérica es: 4 2 0 1 3 5
La Lista genérica es: 6 4 2 0 1 3 5
La Lista genérica es: 6 4 2 0 1 3 5 7
La Lista genérica es: 8 6 4 2 0 1 3 5 7
La Lista genérica es: 8 6 4 2 0 1 3 5 7 9

Elemento eliminado de la lista: 9
La Lista genérica es: 8 6 4 2 0 1 3 5 7
Elemento eliminado de la lista: 8
La Lista genérica es: 6 4 2 0 1 3 5 7
Elemento eliminado de la lista: 7
La Lista genérica es: 6 4 2 0 1 3 5
Elemento eliminado de la lista: 6
La Lista genérica es: 4 2 0 1 3 5
Elemento eliminado de la lista: 5
La Lista genérica es: 4 2 0 1 3
Elemento eliminado de la lista: 4
La Lista genérica es: 2 0 1 3
Elemento eliminado de la lista: 3
La Lista genérica es: 2 0 1
Elemento eliminado de la lista: 2
La Lista genérica es: 0 1
Elemento eliminado de la lista: 1
La Lista genérica es: 0
Elemento eliminado de la lista: 0
Vacia: Lista genérica