Semana 2 - TAD Lista. Vectores y listas enlazadas simples

✔️ Objetivos

  • Distinguir entre las dos regiones de memoria más importantes en C++: pila y heap.

  • Conocer las operaciones básicas del TAD Lista.

  • Saber implementar un TAD Lista mediante vectores redimensionables y mediante listas enlazadas simples.

  • Poder extender las operaciones soportadas por un TAD Lista en cualquiera de las dos implementaciones mencionadas.

  • Identificar los casos en los que es necesario escribir un constructor de copia en C++.

✔️ Tiempo de estudio

  • Vídeos: 1h 13min

  • Total (incluyendo vídeos, cuestionarios y actividades de autoevaluación, pero no los problemas de la sección 2.5): 2h 30min

2.1. Gestión de memoria dinámica en C++

Esta primera sección es importante. Muy importante. Gran parte de los problemas que aparecen cuando programamos en cualquier lenguaje provienen de la compartición entre las distintas estructuras de datos. Si no somos conscientes de esta compartición, los cambios en una estructura de datos podrían afectar a otras estructuras de manera inadvertida para el/la programador/a. Este problema es especialmente llamativo en C++, donde, al contrario que en Java o Python, somos responsables de liberar la memoria que creamos. Si lo hacemos de manera incorrecta, el programa podría provocar un error en tiempo de ejecución y abortar.

En el primer vídeo se introducen las principales regiones de memoria que entran en juego en ejecución: pila y heap. El vídeo es largo, pero es muy importante entenderlo. Ten paciencia y no te lo saltes:

▶️ ️C++ - Objetos y memoria dinámica (16:54)

📄 Código fuente

📝 Ejercicio 2.1

Vamos a poner a prueba los conceptos vistos en el vídeo anterior.

❓ Cuestionario de autoevaluación - Objetos y memoria dinámica

Cuando tenemos objetos que apuntan a otros dentro del heap, puede ser difícil liberar de manera ordenada toda la maraña de objetos. Los destructores de C++ nos facilitan esta tarea:

▶️ ️C++ - Destructores (5:47)

📄 Código fuente

📝 Ejercicio 2.2

Vamos a poner a prueba los conceptos vistos en el vídeo anterior.

❓ Cuestionario de autoevaluación - Destructores

2.2. TAD Lista y su implementación mediante vectores

A continuación os presento uno de los tipos de datos más utilizados en la mayoría de lenguajes de programación: las listas.

Comencemos viendo qué es una lista, y qué operaciones soporta:

▶️ El TAD Lista (6:10)

Ya sabemos las operaciones que ha de soportar este TAD. Ahora nos toca implementarlo. ¿Cómo lo hacemos?. Existen varias maneras:

  1. Utilizando un array unidimensional (es decir, un vector) para almacenar elementos.
  2. Utilizando una lista enlazada simple.
  3. Utilizando una lista doblemente enlazada.
  4. Utilizando una lista doblemente enlazada circular.

La primera de estas maneras se explica en esta misma sección. La segunda se explica en la sección siguiente, y las dos restantes se estudiarán la semana que viene.

La implementación de una lista mediante un array parece una tarea sencilla, pero cuidado: los arrays tienen una longitud fija, por lo que tendremos que tratar de modo especial el caso en que queramos añadir un elemento a la lista (operaciones push_back y push_front), y el array esté "completo". Para ello necesitamos un array que se redimensione a medida que se vaya quedando sin espacio libre.

▶️ Implementación del TAD Lista mediante arrays (9:38)

📄 Código fuente

📝 Ejercicio 2.3

Hasta ahora podemos añadir elementos y eliminar elementos de la lista. Una operación que nos puede interesar es la de actualizar un elemento de la lista. Es decir, reemplazar un elemento de la lista por otro. En el siguiente enlace tienes la implementación de listas que tenemos hasta ahora.

💻 Añadir método update

💻 Solución

Añade el siguiente método a la clase ListArray:

void update(int indice, const std::string &elem);

Este método ha de reemplazar el elemento de la posición indice de la lista por el elemento elem pasado como parámetro.

Aunque un método update como el del ejercicio anterior podría ser útil en un TAD Lista (de hecho, las listas de la biblioteca estándar Java lo implementan), en C++ se utiliza otro enfoque distinto. Para actualizar elementos se hace uso de las referencias, que ya conocéis como mecanismo de paso de parámetros en C++. Se explica en el siguiente vídeo.

▶️ Modificación de listas mediante referencias (9:43)

📄 Código fuente

📝 Ejercicio 2.4

En el siguiente programa podrás poner en práctica las referencias. Echa un vistazo al método main y sigue las instrucciones que aparecen allí.

💻 Prácticas con referencias

💻 Solución

2.3. TAD Lista y su implementación mediante listas enlazadas simples

A continuación viene una de las implementaciones más importantes del TAD Lista: la implementación mediante listas enlazadas. Ojo a esta versión, porque vamos a ir profundizando en ella a lo largo de las siguientes semanas.

▶️ Implementación del TAD Lista mediante listas enlazadas (13:09)

📄 Código fuente

📝 Ejercicio 2.5

Ahora que conoces dos implementaciones del TAD Lista, vamos a comparar los costes de sus operaciones:

❓ Cuestionario de autoevaluación - Coste de operaciones en el TAD lista

ℹ️ Sobre el invariante de representación (opcional)

En el vídeo anterior (minuto 3:55) no soy demasiado preciso en lo que respecta al invariante de representación. Es cierto que este invariante no impone ninguna restricción sobre el atributo head, pero también hay que tener en cuenta la información de los nodos. En particular, los atributos next de los nodos definen la "forma" de la lista enlazada, y están sujetos a una serie de restricciones:

  1. Si un nodo x pertenece a la lista, el nodo x->next ha de ser nullptr o apuntar a un nodo que también debe pertenecer a la lista enlazada.

  2. Si partimos del nodo head y seguimos la cadena de nodos next, en algún momento debemos llegar a nullptr. Es decir, la secuencia de punteros next no puede formar ningún ciclo.

  3. Un nodo pertenece a una única lista. Es decir, no se puede tener dos instancias de ListLinkedSingle tales que, si seguimos la cadena de nodos desde sus respectivos punteros head, ambas confluyen en un nodo común.

Estas tres restricciones no se pueden expresar mediante una fórmula lógica simple. Dado que la verificación formal no es uno de los objetivos principales del curso, decidí no mencionar estas tres restricciones en el vídeo, pero deben satisfacerse en todo caso.

La segunda restricción podría expresarse fácilmente con ayuda de un predicado auxiliar recursivo. Sin embargo, para expresar las restricciones 1 y 3 necesitamos un concepto adicional, que es el footprint de un TAD. Si te interesa el área de la verificación formal de programas, puedes consultar las siguientes referencias:

2.4. El constructor de copia en C++

Descansamos un poco del mundo de los TADs para ver una característica de C++ que no se encuentra en otros lenguajes orientados a objetos. C++ nos permite personalizar la forma en la que se inicializa un objeto a partir de otro. Para ello tenemos que implementar el constructor de copia:

▶️ C++ - Constructores de copia (8:39)

📄 Código fuente

📝 Ejercicio 2.6

Las implementaciones del TAD Lista que hemos visto hasta ahora piden a gritos un constructor de copia, para evitar compartición no deseada. Es tu turno: ¿puedes implementarlo en ambas?

💻 Añadir constructor de copia a implementación mediante arrays

💻 Añadir constructor de copia a implementación mediante listas enlazadas

En el siguiente vídeo se muestra una posible forma de implementar el constructor de copia para los TAD vistos hasta ahora:

▶️ Constructores de copia en el TAD Lista (3:04)

📄 Código fuente (implementación mediante vectores)

📄 Código fuente (implementación mediante listas enlazadas)

ℹ️ Información adicional sobre Java (opcional)

En Java existe el constructor de copia como tal, pero es tratado como un constructor cualquiera. Por ejemplo, supongamos la siguiente clase:

class MiClase { ... }

Si asignamos un objeto c1 a un objeto c2,

MiClase c1 = new MiClase();
MiClase c2 = c1;

en realidad estamos haciendo que c2 apunte al mismo objeto que c1. Es decir, en Java no se llama a ningún constructor de copia.

Es posible implementar un constructor de copia en Java, declarándolo como un constructor que recibe otra instancia de MiClase.

class MiClase {
    public MiClase() {/* constructor por defecto */}
    public MiClase(MiClase other) {/* constructor de copia */}
    // ...
}

En este caso, tendríamos que llamar al constructor explícitamente para hacer uso de él

MiClase c1 = new MiClase();
MiClase c2 = new MiClase(c1);  // Llama al constructor de copia

Una alternativa al constructor de copia en Java es la clase Cloneable y el método clone() de la clase Object.

2.5. Problemas de laboratorio

📝 Ejercicio 2.7

💻 Repetir los elementos de una lista

📝 Ejercicio 2.8

💻 Escamochar una lista