Lenguaje C Listas

Listas:
Pre-requisitos

Los tipos de datos
Las estructuras
El uso de typedef
Los punteros
Las funciones usuario
I. Introducción

El objetivo de este artículo es el de comprender el uso de las listas enlazadas simples.
Las listas enlazadas pueden ser utilizadas cuando se necesitan hacer varias operaciones de inserción y eliminación de elementos.
II. Definición

Las listasenlazadas son estructuras de datos semejantes a los array salvo que el acceso a un elemento no se hace mediante un indice sino mediante un puntero.
La asignación de memoria es hecha durante la ejecución.

En una lista los elementos son contiguos en lo que concierne al enlazado.

En cambio, mientras que en un array los elementos están contiguos en la memoria, en una lista los elementos estándispersos.
El enlace entre los elementos se hace mediante un puntero.
En realidad, en la memoria la representación es aleatoria en función del espacio asignado.

El puntero siguiente del último elemento debe apuntar hacia NULL (el fin de la lista).

Para acceder a un elemento, la lista es recorrida comenzando por el inicio, el puntero siguiente permite el desplazamiento hacia el próximoelemento.
El desplazamiento se hace en una sola dirección, del primer al último elemento.
Si deseas desplazarte en las dos direcciones (hacia delante y hacia atrás) deberás utilizar las [ listas doblemente enlazadas]
III. Construcción del modelo de un elemento de la lista

Para definir un elemento de la lista, será utilizado el tipo struct.
El elemento de la lista contendrá un campo datoy un puntero siguiente.
El puntero siguiente debe ser del mismo tipo que el elemento, si no, no podrá apuntar hacia el elemento.
El puntero siguiente permitirá el acceso al próximo elemento.

typedef struct ElementoLista {
char *dato;
struct ElementoLista *siguiente;
}Elemento;

Para tener el control de la lista es preferible guardar ciertos elementos:
El primer elemento, el últimoelemento, el número de elementos.

Para ello será utilizado otra estructura (no es obligatorio, pueden ser utilizadas variables)

typedef struct ListaIdentificar {
Elemento *inicio;
Elemento *fin;
int tamaño;
}Lista;

El puntero inicio contendrá la dirección del primer elemento de la lista.
El puntero fin contendrá la dirección del último elemento de la lista.
La variable tamañocontiene el número de elementos.

Cualquiera que sea la posición en la lista, los punteros inicio y fin apuntan siempre al primer y último elemento.
El campo tamaño contendrá el numero de elementos de la lista cualquiera que sea la operación efectuada sobre la lista.
IV. Operaciones sobre las listas enlazadas

Para la inserción y la eliminación, una solo función bastará si está bienconcebida de acuerdo a lo que se necesite.
Debo recordar que este artículo es puramente didáctico.
Por esta razón he escrito una función para cada operación de inserción y eliminación.
A. Inicialización

Modelo de la función:

void inicializacion (Lista *lista);

Esta operación debe ser hecha antes de cualquier otra operación sobre la lista.
Esta inicializa el puntero inicio y el punterofin con el puntero NULL, y el tamaño con el valor 0.

La función

void inicializacion (Lista *lista){
lista->inicio = NULL;
lista->fin = NULL;
tamaño = 0;
}
B. Inserción de un elemento en la lista

A continuación el algoritmo de inserción y registro de los elementos:
declaración del elemento a insertar
asignación de la memoria para el nuevo elemento
rellenar el contenido delcampo de datos
actualizar los punteros hacia el primer y ultimo elemento si es necesario.
Caso particular: en una lista con un solo elemento, el primero es al mismo tiempo el último.
Actualizar el tamaño de la lista

Para añadir un elemento a la lista hay varios casos:
1. Inserción en una lista vacía
2. Inserción al inicio de la lista
3. Inserción al final de la lista
4. Inserción...