Pues en esta ocasion veremos la implementacion de una lista ligada en c, solomente sera como un ejemplo ilustrativo pero las ideas desarrolladas aqui podran extenderse hacia horizontes mas amplios.

Una lista es un tipo de dato abstracto, se le llama asi porque es un tipo de dato definido por el programador a diferencia de los tipos de datos que nos ofrece el lenguaje C que ya son “nativos” del lenguaje por ejemplo los tipo int, float,char..etc

Imaginemos a la lista como una longaniza =), la longaniza esta compuesta por muchos trozos de carne unidos uno tras otro, las longanizas tienen un fin y un inicio. Imagina que todos los trozos que forma la longaniza son iguales, pues ahora la lista es como la longaniza y esos trozos de carne de la longaniza les llamaremos los nodos de la lista. Cada uno de los nodos puede almacenar informacion para fines practicos los nodos de nuestra lista almacenaran un entero, y podemos realizar varias operaciones sobre una lista, por ejemplo ver si la lista esta vacio o dicho de otra forma si la lista no tiene nodos, tambien recorrer los nodos de la lista buscando dentro de su informacion por algun valor en especifico, podremos insertar nuevos nodos a la lista, eliminar nodos …etc

Hagamos una especificacion de las operaciones que definiremos sobre nuestra lista.

• Inicializar una lista
• Insertar un nodo
• Eliminar un nodo
• consultar un nodo
• Desplegar todos los elementos de la lista

He recordado que como preparacion para un examen de la universidad implemente una lista con todas las operacion anteriores, ademas de las versiones recursivas de cada una de las operaciones. Si sabes usar punteros y puedes implementar una lista con todas sus operaciones por ti mismo, seguramente seras un buen programador de C.

Como habiamos dicho nuestra lista contendra nodos, entonces deberemos definir una estructura que llamaremos nodo, un nodo es como una capsula que contendra informacion en este caso cada nodo debe contener una referencia hacia el siguiente nodo de la lista y una variable de tipo entero que hara el papel de campo de informacion.

1
2
3
4
5

struct nodo{
	int info;
	struct nodo *sig;
};
typedef struct nodo nodo;

Esa es la definicion de nuestro nodo, es una estructura que contiene dos campos info que almacenara un entero y el otro campo es sig que es un apuntador a la estructura nodo, los nodos de la lista pueden almacenar muchas cosas mas, aqui solo almacenaremos un entero, y ademas le ponemos un alias a struct nodo, que sera nodo, esto es util para no tener que teclear simpre “struct nodo”, en vez de eso solo escribiremos nodo.

Para la lista necesitaremos tener una operacion mas inehrente a la estructura de dato lista, es la operacion para crear un solo nodo, como habiamos dicho los nodos contienen 2 cuantos o campos de informacion, un campo es la referencia hacia el siguiente nodo y el otro es el campo informacion representada por una variable entero.

Cuando creamos un nuevo nodo debemos crear una variable del tipo struct nodo e inicializar sus campos, necesariamente debes asignarle en entero a su campo info y su campo sig debera apuntar a la constante NULL.

1
2
3
4
5
6
7
8
9
10
11
12

/*
*funcion para crear un nuevo nodo
*@param int
*@return nodo
*/
nodo * creaNodo (int elem){
	nodo *aux;
	aux = (nodo *)malloc(sizeof(nodo));
	aux->valor = elem;
	aux->sig = NULL;
	return aux;
}

La funcion anterior no devolvera el nuevo nodo creado con sus campos ya inicializados.

Las siguientes operaciones que incluyan modificaciones a la lista recibiran la lista completa como parametro y la modificaran por referencia como en el caso de la funcion para insertar un nuevo nodo. las operaciones como consultar un nodo recibiran a la lista por valor.

Por regla general una lista debe tener un inicio y un final, nosotros identificaremos el inicio de la lista con un simple apuntador a nodo llamado inicio que servirar para identificar el inicio de la lista, el apuntador inicio debe apuntar al primer nodo de la lista, si la lista esta vacio el apuntador inicio apuntara a null.

Unas de las primeras operacion a crear es la operacion para inicializar una lista, lo unico que hara esta funcion es recibir el puntero inicio y asignarle la constante NULL;

1
2
3
4
5
6
7
8

/*
*inicializa una lista
*@param &nodo
*@return void
*/
void iniciaLista (nodo *lista){
	lista = NULL;
}

Ahora vemos una funcion mas interesante, la funcion para insertar un nuevo nodo. al insertar un nuevo nodo se presentan los siguientes casos

• Problema:Hay que insertar el nuevo nodo en una lista vacio
  Solucion:Apuntar el inicio de la lista al nuevo nodo creado.

• Problema:Hay que insertar el nodo al inicio de la lista posicion n =1, cuando la lista no esta vacia.
  Solucion:crear un nuevo nodo, apuntar el campo siguiente del nuevo nodo al inicio de la lista, apuntar el inicio de la lista al nuevo nodo creado

• Problema:Hay que insertar el nodo en alguna posicion n, con n distinto de 1
  Solucion: Apuntar el campo siguiente del nuevo nodo al nodo situado en la posicion n, el nodo en la posicion n-1 en su campo siguiente debe apuntar al nuevo nodo creado.

Aqui esta la funcion correspondiente a insertar un nuevo nodo en la lista recibiendo como parametro una posicion de insercion.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

/*
*inserta un nuevo nodo en la lista 
*@param &nodo, int, int 
*@return void
*/
void inserta( nodo **lista, int elem, int pos){
  nodo *aux;
  aux =  creaNodo(elem);
  if ( *lista == NULL){
  	*lista = aux;
  }else{
	if (pos == 1){
		aux->sig = *lista;
		*lista = aux;
	}else{
		nodo *contador;
		int i=1;
		contador = *lista;
		while (contador != NULL){
			if (i == (pos-1) ){
				aux->sig = contador->sig;
				contador->sig = aux;
				break;
			}
			contador = contador->sig;
			i++;
		}
	}
  }
}

En la funcion anterior ya se han implementado los tres casos posibles para la insercion de un elemento en una lista.

Ahora pasemos a la operacion que consiste en eliminar un nodo de la lista a partir de una posicion pasada como parametro. En esta situacion se presentan los siguientes casos.

• Problema:Hay que eliminar el nodo en la posicion 1
  Solucion:apuntar el inicio de la lista al nodo en la posicion 2, eliminar el nodo en la posicion 1

• Problema:Hay que eliminar el nodo en la posicion n, con n>1
  Solucion: en nodo en la posicion n-1 debera apuntar al nodo en la posicion n+1, eliminar el nodo en la posicion n

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

/*
*elimina un nodo de la lista
*@param int, &nodo
*@return void
*/
void borrar(int pos, nodo **lista){
	nodo *aux;
	aux = *lista;
 
	if (pos == 1){
		*lista = (*lista)->sig;
		free(aux);
	}else{
                int i=1;
                struct nodo *aux2;
                while (i < (pos-1) ){
                    i++;
                    aux = aux->sig;
                }
                aux2 = aux->sig;
                aux->sig = aux2->sig;
                free(aux2);
	}
}

La siguiente funcion consiste en consultar el campo informacion de algun nodo en especifico a partir de su posicion en la lista, el proceso sera el siguiente recorreremos la lista secuencialmente hasta situarnos en la posicion que se desea consultar y devolveremos el campo info del nodo en el que nos encontramos.

1
2
3
4
5
6
7
8
9
10
11
12
13

/*
*devuelve el compo info de un nodo
*@param &nodo, int
*@return int
*/
int consulta(nodo *lista, int pos){
	nodo *aux;
	aux = lista;
	for (int i=1;i<pos;i++){
		aux = aux->sig;
	}
	return aux->info;
}

Y por ultimo hablaremos de la funcion que despliega todos los elementos de una lista, la idea es visitar cada uno de los nodos de la lista de manera secuencial, uno tras otro e imprimir en pantalla el contenido de su campo info.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

/*
*Despliega el contenido de la lista
*@param &nodo
*@return void
*/
void desplegar(nodo *lista ){
	nodo *aux;
	aux = pila;
	if (aux == NULL){
		printf("\n\nLista vacia\n\n");
	}else{
        printf("\n\n");
        printf("Contenido de la lista:\n");
        while ( aux != NULL ){
            printf("%d\n", aux->info);
            aux = aux->sig;
        }
        printf("\n\n");
	}
}

Todas la funciones anteriores las he guardado en un archivo llamado lista.c y para probarlas he hecho un archivo de aplicacion llamado aplicacion.c y contiene lo siguiente.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

#include "lista.c"
 
int main(){
 
    nodo *inicio;
    iniciaLista(&inicio);
 
    int i;
    for (i=0;i<10;i++){
        inserta(&inicio, i+1,i+1);
    }
 
    desplegar(inicio);
 
    return 0;
}

pero por si las dudas aqui dejo un archivo comprimido con los archivos creados en este documento enlace