Información general:Las listas enlazadas son un recurso dinámico muy potente que nos permite realizar tareas que generalmente podríamos requerir con arrays, pero se impide en objetos estáticos y en dinámicos sería muy complicado.
Una lista enlazada se basa en una estructura, la cual será el esqueleto o prototipo del contenido, y al final requerirá tener un puntero hacia la siguiente estructura del mismo tipo, es decir están enlazadas por su ubicación (dirección de memoria).
Funcionamiento y estructura:Primero debemos tener la estructura o prototipo en el cual definiremos los datos que emplearemos y como debe ser, un puntero a otra estructura del mismo tipo:
typedef struct _nodo
{
int valor;
struct _nodo * pNext;
}_Nodo;
Utilizamos typedef para evitar estar utilizando struct _nodo para todo, así abreviamos y hacemos el código más legible.
Hay unas bases a tener en cuenta para trabajar con listas enlazadas:
- El final de una lista será determinada por un puntero con valor NULL, es decir el último elemento tendrá como siguiente elemento a NULL.
- Los elementos se pueden recorrer en un solo sentido (Inicio - Final), debido a que solo tenemos un apuntador al siguiente y no al anterior, las listas que cuentan con esta opción se conocen como doblemente enlazadas. Las trataremos en otro tema.
- Es muy importante mantener siempre el valor inicial de la lista, en caso de perderle sería muy difícil de recuperar.
- Es muy importante controlar muy bien los punteros hacia los elementos, un simple número distinto y podríamos causar perdida de control sobre el programa.
Recordemos, cada elemento tiene un apuntador al siguiente, por ello se llaman enlazados:
Para trabajar con listas, deberemos implementar una serie de funciones y procedimientos para el manejo de sus elementos entre ellas:
- Crear lista nueva.
- Insertar elemento (Al inicio, al final y posterior al otro elemento).
- Buscar elemento.
- Eliminar elementos(El primer elemento, un elemento en base a su dirección).
- Imprimir contenido de listas (Este uso ya depende del usuario).
Creación de una lista nueva:Para crear una nueva lista teniendo en cuenta el prototipo lo que utilizaremos son punteros, por lo cual suele ser más cómodo utilizar un typedef para más comodidad. En cuanto a teoría para crear una nueva lista deberíamos:
- Crear una función cuyo tipo de valor de retorno será el mismo del prototipo.
- La función creará una estructura dinámica con el tamaño del prototipo (malloc).
- Se establecerá un valor inicial para los elementos de la estructura.
- El apuntador al siguiente elemento será NULL, esto identificará la lista como vacía.
- La función retornará la dirección de la lista creada (valor retornado por malloc).
_pNodo CrearLista(int valor)
{
_pNodo Lista;
Lista = (_pNodo) malloc (sizeof(_Nodo));
Lista->valor = valor;
Lista->pNext = NULL;
return Lista;
}
Para insertar nuevos elementos deberemos tener una lista previamente creada y contar con su referencia para acceder a ella, además se deberán hacer múltiples comparaciones con fines de prevenir errores, como cuando la lista está vacía, o el lugar donde se va a ingresar el nuevo elemento, etc.
Insertar elemento al final:- La función requerirá el valor del elemento a ingresar y el inicio de la lista.
- Crear un nuevo prototipo de estructura, lo llamaremos Nodo.
- Comprobar si la lista está vacía, en tal caso simplemente modificar la dirección a la que apunta por el nodo creado (NULL x Dirección nuevo Nodo). En caso de no estar vacía deberemos recorrer todos los elementos hasta reconocer al que apunta al NULL y editar por la dirección del nuevo Nodo.
- En caso de recorrer la lista no olvidar utilizar una variable auxiliar para no perder la lista principal.
- Al ser un elemento que va al final, estará obligado a tener su campo de siguiente estructura a NULL.
- En mi caso bajo utilice la idea de retornar la dirección del nuevo elemento insertado, muchos códigos retornan la misma lista ingresada, cuando en realidad esta no sufre modificaciones y no es útil.
_pNodo InsertarElementoAlFinal(int valor, _pNodo ListaInicial)
{
_pNodo NuevoNodo;
_pNodo Auxiliar = ListaInicial;
NuevoNodo = malloc(sizeof(_Nodo));
NuevoNodo->valor = valor;
NuevoNodo->pNext = NULL;
if (ListaInicial->pNext == NULL)
{
ListaInicial->pNext = NuevoNodo;
}
else
{
while(Auxiliar->pNext != NULL)
{
Auxiliar = Auxiliar->pNext;
}
Auxiliar->pNext = NuevoNodo;
}
return NuevoNodo; /* Retornamos dirección del elemento insertado */
}
- La función requerirá el valor del elemento a ingresar y el inicio de la lista.
- Crear un nuevo Nodo, asignar el valor correspondiente.
- El valor del campo siguiente elemento del Nodo creado deberá ser correspondiente al valor principal de la lista.
- Retornamos el nuevo inicio de lista, correspondiente al nuevo Nodo.
_pNodo InsertarElementoAlInicio(int valor, _pNodo ListaInicial)
{
_pNodo NuevoNodo;
NuevoNodo = malloc(sizeof(_Nodo));
NuevoNodo->valor = valor;
NuevoNodo->pNext = ListaInicial;
return NuevoNodo; /* Retornamos nueva lista inicial */
}
- La función requerirá el valor del elemento a ingresar y la dirección del elemento anterior a donde ingresaremos el nuevo.
- Creamos el nuevo nodo y asignamos los valores correspondientes.
- El nuevo Nodo creado ahora apuntará al elemento que apuntaba el Nodo anterior a este.
- El Nodo anterior apuntará al nuevo Nodo insertado.
- Retornamos la dirección del nuevo Nodo.
_pNodo InsertarElementoPosterior(int valor, _pNodo ElementoAnterior)
{
_pNodo NuevoNodo;
NuevoNodo = malloc(sizeof(_Nodo));
NuevoNodo->valor = valor;
NuevoNodo->pNext = ElementoAnterior->pNext;
ElementoAnterior->pNext = NuevoNodo;
return NuevoNodo; /* Retornamos dirección del elemento insertado */
}
La eliminación de elementos también es una función muy importante a la hora de trabajar con listas, sus implementaciones pueden ser muchas debido a la gran cantidad de casos posibles, como eliminar el primer o último elemento, eliminar un elemento según su dirección, posterior a otro, o buscando por valor (Eliminar primero, último o todos). Yo mostraré 2 casos, eliminando el primer elemento y eliminando por dirección del elemento.
Eliminación del primer elemento:- Para esta función únicamente necesitaremos el inicio de lista.
- Usaremos una variable auxiliar la cual nos ayudará a almacenar datos temporalmente.
- Comprobamos si la lista está vacía, en tal caso dejamos todo igual.
- Almacenamos el elemento inicial de lista en la variable auxiliar.
- Ahora el inicio de lista apuntará tendrá como valor el elemento al cual apuntaba.
- Liberamos el espacio de memoria que contiene la variable auxiliar con free().
_pNodo EliminarPrimerElemento(_pNodo Lista)
{
_pNodo Auxiliar;
Auxiliar = Lista;
if (Auxiliar->pNext == NULL)
{
return Lista; /* Si no hay más elementos dejamos todo igual */
}
Lista = Auxiliar->pNext;
free(Auxiliar);
return Lista; /* Retornamos la nueva base de la lista */
}
- Necesitaremos inicio de lista y dirección del elemento a eliminarla.
- Utilizamos una variable auxiliar para buscar el elemento anterior al elemento a eliminar recorriendo toda la lista.
- En caso de no encontrar el elemento comparando su dirección retornamos 0 (FALSE)
- Comprobamos si el elemento a eliminar es el último, en tal caso el elemento anterior apuntará a NULL, de lo contrario el elemento anterior al que eliminamos apuntará al elemento que apuntaba el elemento que eliminamos.
- Liberamos la memoria del elemento a eliminar.
- Retornamos 1(TRUE).
int EliminarElemento(_pNodo Elemento, _pNodo Lista)
{
_pNodo Auxiliar;
Auxiliar = Lista;
while (Auxiliar != NULL)
{
if (Auxiliar->pNext == Elemento)
{
break;
}
Auxiliar = Auxiliar->pNext;
}
if (Auxiliar == NULL)
{
return 0;
}
else
{
if (Elemento->pNext == NULL)
{
Auxiliar->pNext = NULL;
}
else
{
Auxiliar->pNext = Elemento->pNext;
}
free(Elemento);
return 1;
}
}
La búsqueda de elementos generalmente se realiza para localizar la posición de un objeto comparando su valor, ya que si se tiene su dirección simplemente haciendo referencia podríamos acceder a su contenido.
Búsqueda por valor:- Necesitaremos el valor a buscar y el inicio de lista.
- Utilizaremos una variable auxiliar para no perder el inicio de la lista.
- Recorremos toda la lista y vamos comparando si cada elemento es igual al buscado.
- Una vez localizado simplemente retornamos la dirección del elemento.
- Si no se lo encuentra se retornará NULL.
_pNodo BuscarElemento(int valor, _pNodo Lista)
{
_pNodo Auxiliar;
Auxiliar = Lista;
while(Auxiliar != NULL)
{
if (Auxiliar->valor == valor)
{
break;
}
Auxiliar = Auxiliar->pNext;
}
return Auxiliar; /* Retornamos dirección del elemento encontrado */
}
Bueno, espero hayan comprendido el articulo y prometo trabajar más estructuras de datos.
Hasta la próxima.
Saludos.
