Listas enlazadas en C.

En esta entrada vemos como implementar listas enlazadas en C. Para ello es importante conocer algo de punteros para lo que recomiendo echar un vistazo a esta entrada a aquellos que no manejen nada el tema. Además este ejercicio es muy parecido a la práctica de Gestión de Memoria, incluso más fácil. Aquí os dejo tanto el archivo .h (header) como el .c -> LinkedList.h LinkedList.c

Cada nodo de la lista está formado por :

• Un elemento del tipo deseado, en nuestro caso unsigned.
• Un puntero al próximo nodo, o null si es el último.

Por tanto cada nodo estará definido así.

typedef struct TNodo * TLista; // defino el tipo TLista, que es un puntero a un registro

struct TNodo {
 unsigned valor;
 TLista sig;
 };

Como vemos, hay dos elementos en el registro:

• Un elemento llamado valor de tipo natural.
• Un puntero al próximo nodo, pues TLista es un puntero a un nodo.

El ejercicio nos pide crear los siguientes métodos: 

void crear (TLista * lista); // Crear lista vacia

void rellenar(TLista * lista); // Incluir elementos en la lista (pedir numeros hasta que se inserte un negativo) y que los elementos se inserten por el principio

void destruir(TLista* lista); // Destruir todos los elementos de la lista

void mostrar (TLista lista); // Mostrar los elementos de la lista

Pasamos a ver cada uno de los métodos:
Crear: Simplemente hacemos que el puntero apunte a NULL.

void crear (TLista * lista){ // Crear lista vacia
 *lista = NULL;
}

Rellenar: Mientras los números que introduzcamos sean positivos, creamos un auxiliar con el valor del número introducido cuyo siguiente sea el resto de la lista y posteriormente hacemos que la lista apunte a dicho auxiliar.

void rellenar(TLista * lista){
 int insertado;
 TLista auxiliar;

 printf("Introduce los números de la lista (introducir un número negativo para finalizar): \n");
 fflush(stdout);
 scanf("%d", &insertado);
 while (insertado >= 0) {
  auxiliar = malloc(sizeof(struct TNodo));
  auxiliar->valor=insertado;
  auxiliar->sig=*lista;
  *lista=auxiliar;
  scanf("%d", &insertado);
 }
}

Destruir: Añado dos formas distintas de hacerlo. En ambas se necesita un auxiliar para recorres dicha lista e ir eliminando los nodos, liberando memoria mediante el método free.

void destruir(TLista* lista){// Destruir todos los elementos de la lista
 TLista auxiliar;
 while (*lista != NULL) {
   auxiliar=(*lista)->sig;
   free(*lista);
   *lista=auxiliar;
 }
 /*
  TLista ptr = *lista;
   while(ptr != NULL){
     *lista = ptr-> sig;
     free( ptr);
     ptr = *lista;
   }
 */
}

Mostrar:  Simplemente recorremos la lista mostrando los valores de los nodos.

void mostrar (TLista lista){// Mostrar los elementos de la lista
 TLista ptr = lista;
 printf("[");
 while (ptr != NULL) {
  printf("%u", ptr->valor);
  ptr = ptr->sig;
  if (ptr != NULL) {
   printf(", ");
  }
 }
 printf("]\n");
}

Posteriormente en otra entrada completaré el ejercicio agregando otros métodos como:

int is_empty(Linked_List l); // Devuelve verdadero si la lista está vacía 
int contains(Linked_List l, unsigned v); // Devuelve verdadero si la lista 
contiene el elemento v 
int length(Linked_List l); // Devuelve el número de elementos de la lista 
int insert(Linked_List * ptrL, int pos, unsigned v); // Inserta v en la posición 
pos de la lista (*prtL). Si ok, devuelve verdadero; si pos no está entre 1 y 
length +1, entonces devuelve falso 
int remove(Linked_List * ptrL, int pos); // Borra el elemento pos de la 
lista, devolviendo verdadero o falso según la operación se pueda realizar. 
int getElement(Linked_List l, int pos); // Devuelve el elemento de la 
posición pos. Si esa posición no existe, el comportamiento de la función no 
está definido. 
Linked_List readFromFile(char * filename); // Asumiendo que filename 
contiene N líneas, donde cada línea es un entero, lee el fichero y almacena su 
contenido una lista que es devuelta como resultado. En caso de alguna 
situación de error, la función devolverá NULL. 
int writeToFile(Linked_list list, char * filename); // Escribe el contenido 
de la lista list en el fichero denominado filaneme, almacenando cada elemento 
de la lista una línea del fichero. La función devuelve verdadero o falso según 
se haya realizado con éxito o no

Un saludo ;)