From Movaxes

Revision as of 20:31, 12 March 2007

Listas

Las listas enlazadas son usadas como base para muchos otros tipos de estructuras de datos como la pila (stacks), cola (queue), etc.

La desventaja de las líneas enlazadas es que su búsqueda es lineal y por lo tanto corre normalmente en O(N). Algunas formas de mejorar esto son por ejemplo mover al principio el nodo cuando es encontrado (útil cuando se trabaja con pequeños cache, que asegura que el más utilizado es encontrado más rápido).

Lista Contigua

Es una lista en la cual los elementos son adyacentes en la memoria y tiene un límite sobre la cantidad de elementos que puede contener. Su implementación e suele hacerce por medio de arreglos (arrays) por lo que se procesa como un array unidimensionales.

Uno de los inconvenientes de usar las listas contiguas es que tienen un límite de elementos posibles.

Listas Enlazadas

Terminología:

• Nodo: se refiere a uno de los elementos en la lista
• Campo: se refiere a uno de los componentes de un nodo (Un nodo tiene al menos dos campos: dato o valor y enlace)

Lista Lineal

Son aquellas en las cuales los elementos no están almacenados de forma adyacente, por lo cual cada elemento almacena la dirección del siguiente elemento de la lista. Esta es mucho más potente y flexible que las listas contiguas, por ejemplo, no requiere el desplazamiento de otros elementos para poder insertar uno nuevo.

El último elemento (nodo) contiene el valor NULL ya que no apunta a ningún elemento por ser este el último. Esta estructura de dato debe contener al menos dos campos, un valor (sea un int, char, etc) y un puntero al siguiente nodo.

Para insertar un nuevo elemento lo único que se hace es cambiar el puntero del elemento anterior al nuevo elemento y este contiene ahora el puntero al siguiente elemento. Así suponiendo que tenemos un elemento número 40 en nuestra lista, este apunta al número 41, si queremos ingresar un nuevo nodo entre estos elementos lo único que necesitamos es que el número 40 ahora apunte al nuevo nodo que ahora es el número.

Implementación de un elemento (nodo):

typedef struct elemento
{
	int dato; //esto puede ser cualquier tipo de dato (o datos)
	struct elemento *siguiente;
} nodo;

Implementación de nuevo_nodo:

void nuevo_nodo(int valor, nodo *enlace)
{
	nodo *s;
	s = (nodo *)malloc(sizeof(nodo));
	s->dato = valor;
	s->siguiente = enlace;
}

Para crear el primer nodo y empezar así la lista usamos:

primero = nuevo_nodo(1,NULL);

Para crear un segundo nodo usamos:

primero = nuevo_nodo(2,primero);

Implementación de Lista Lineal

En este ejemplo se implementa una lista lineal, con las siguientes funciones:

• nuevo_nodo = crea un nodo antes del indicado
• borrar_nodo = borra el nodo pasado como argumento
• buscar_nodo = busca el nodo que tenga el valor pasado como argumento
• es_vacia = devuelve 1 si la lista esta vacia
• mostrar_lista = muestra la lista completa

#include <stdlib.h> //para malloc
#include <stdio.h> //para printf

//nuestra estructura
typedef struct elemento
{
	int dato; //valor
	struct elemento *siguiente; //apunta al siguiente nodo o es NULL
} nodo;

nodo *lista = NULL; //creamos la lista

void mostrar_lista(nodo *list); //muestra lista completa
void nuevo_nodo(nodo **list, int valor); //crea un nuevo nodo al principio de la lista
char es_vacia(nodo *list); //regresa 1 si la lista es vacia
void borrar_nodo(nodo **list); //borra el primer nodo de la lista
nodo **buscar_nodo(nodo **list, int valor); //busca el nodo con este valor

/**************/
int main(void)
{
	int i;
	for(i=1; i<11; i++) nuevo_nodo(&lista, i); //creamos lista del 1 al 10
	borrar_nodo(buscar_nodo(&lista,5)); //borramos el nodo con valor 5
	nuevo_nodo(buscar_nodo(&lista,4),5); //agregamos el nodo con valor 5
	mostrar_lista(lista); //mostramos la lista completa
	return 0;
}

//regresa 1 si está vacia
char es_vacia(nodo *list)
{
	return(list==NULL); //1 si la lista esta vacia
}

//Muestra en pantalla todos los nodos
void mostrar_lista(nodo *list)
{
	if(es_vacia(list)) printf("La lista esta vacia\
");
	while(list!=NULL) //mientras encontremos nodos
	{
		printf("%p es = %i, siguiente es = %p\
", list, list->dato, list->siguiente);
		list = list->siguiente; //apuntamos al siguiente
	}
}

//inserta un nodo al principio de la lista
void nuevo_nodo(nodo **list, int valor)
{
	if(list==NULL) return;
	nodo *nuevo = (nodo *)malloc(sizeof(nodo)); //creamos el nuevo nodo
	nuevo->siguiente = *list; //el nuevo nodo apunta al primero
	nuevo->dato = valor; //ponemos el dato
	*list = nuevo; //el primer nodo es ahora el nuevo
}

//borra el primer nodo de la lista o el nodo indicado
void borrar_nodo(nodo **list)
{
	if(list==NULL) return;
	nodo *primero = *list; //copiamos el nodo
	if(es_vacia(primero)) //esta vacio?
	{
		printf("Error al borrar, lista vacia?\
");
		return; //regresar
	}
	*list = primero->siguiente; //apuntamos al siguiente del que va a ser borrado
	free(primero); //borramos
}

//busca el nodo que contenga este valor y lo regresa al encontrarlo
nodo **buscar_nodo(nodo **list, int valor)
{
	while(*list!=NULL) //mientras encontremos nodos
	{
		if((*list)->dato == valor) return list; //si lo encontramos lo regresamos
		list = &(*list)->siguiente; //apuntamos al siguiente
	}
	printf("No hay nodo con el valor = %i\
",valor);
	return NULL; //no lo encontramos
}

NOTA: por favor indicarme cualquier bug o mejora en la implementación (gracias!!).

Lista Circular

Esta estructura es una modificación de la lista inicial porque el último nodo en lugar de contener NULL apunta al primer nodo.

Algunas de las ventajas que tienen las listas circulares contra las listas lineales enlazadas son:

• Cualquier nodo es accesible desde cualquier nodo.
• Algunas operaciones son más eficientes, como la división de la lista o concatenación.

Algunas desventajas son:

• se pueden producir bucles o lazos infinitos. Para evitarlo se crea un nodo cabecera que contiene algún dato especial que lo diferencia como el primer nodo (bandera, flag).

Lista doblemente enlazada

Funciona de forma parecida a la lista lineal pero en esta cada nodo apunta al anterior (excepto el primero que contiene NULL).

Una de las primeras ventajas de estas listas es que a diferencia de las listas lineales estas pueden ser recorridas de izquierda a derecha y al contrario. Contienen dos punteros, uno a el nodo anterior y otro al siguiente. Se utilizan dos punteros, uno de cabecera y otro de fin para poder recorrerla de principio a fin y al contrario.

Listas doblemente enlazadas circulares

Estas contienen en el primer nodo un puntero (anterior) al último nodo y el último nodo contiene un puntero (siguiente) al primer nodo.

Links

• SimCList: Librería de Listas Enlazadas en C
• Listas enlazadas en la Wikipedia (ingles)
• Listas enlazadas en la Wikipedia