8.1.1 Descripción informal

Una lista encadena es una secuencia de nodos, encadenados por apuntadores, como se ve en la figura .

Figure: Lista encadenada

La flechas representan los apuntadores, cada uno de estos dice cual es el siguiente nodo, por ello al apuntador de la llama sig. El TDA Lista es una tupla que tiene dos elementos: el apuntador al elemento inicial de la lista y un apuntador al elemento actual, este último es usado por muchas de las operaciones de lista.

La Lista comienza estando vacia, esto es, elem a nulo y actual a nulo. En una lista se puede adicionar una nueva información, esto es, poner como último elemento de la lista, además este queda como actual; insertar después del elemento actual es una operación más ganeral . También se puede retirar el elemento actual de la lista, retornando la información. Otra operación retorna la información del elemento actual. Son muy importantes también las operaciones que modifican el elemento actual, que son: colocar primero como actual, colocar último como actual, colocar siguiente como actual y colocar el elemento x-ésimo como actual.

Un Nodo está compuesto de dos campos la información inf y un apuntador al siguiente Nodo llamado sig. Las operaciones de Nodo son muy sencillas, solo se necesitan dos operaciones que obtengan los valores de los dos campos y dos operaciones que permitan modificarlos.