Programación General > C/C++

 [C] Listas enlazadas.

(1/1)

The Swash:

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: C++ ---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: C++ ---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: C++ ---_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: C++ ---_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: C++ ---_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: C++ ---_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: C++ ---_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: C++ ---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: C++ ---_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.

Navegación

[0] Índice de Mensajes