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:
Código
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.
Código
typedef _Nodo * _pNodo;
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).
Código
_pNodo CrearLista(int valor) { _pNodo Lista; Lista = (_pNodo) malloc (sizeof(_Nodo)); Lista->valor = valor; Lista->pNext = NULL; return Lista; }
Inserción de elementos:
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.
Código
_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 */ }
Inserción de elementos al principio:
- 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.
Código
_pNodo InsertarElementoAlInicio(int valor, _pNodo ListaInicial) { _pNodo NuevoNodo; NuevoNodo = malloc(sizeof(_Nodo)); NuevoNodo->valor = valor; NuevoNodo->pNext = ListaInicial; return NuevoNodo; /* Retornamos nueva lista inicial */ }
Inserción de un elemento posterior a otro:
- 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.
Código
_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 */ }
Eliminación de elementos:
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().
Código
_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 */ }
Eliminar elemento por su dirección:
- 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).
Código
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; } }
Búsqueda de elementos:
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.
Código
_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.