[C] Listas enlazadas.

[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 (cpp) [Seleccionar] Expandir

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 (cpp) [Seleccionar] Expandir

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 (cpp) [Seleccionar] Expandir

_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 (cpp) [Seleccionar] Expandir

_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 (cpp) [Seleccionar] Expandir

_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 (cpp) [Seleccionar] Expandir

_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 (cpp) [Seleccionar] Expandir

_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 (cpp) [Seleccionar] Expandir

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 (cpp) [Seleccionar] Expandir

_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.

[BlackZeroX]

.
Estos temas apenas los estan tocando en mi facultad pero la vdd no tiene mucha ciencia.

https://secure.wikimedia.org/wikipedia/es/wiki/Estructura_de_datos

* Con respecto a tus codigos de ejemplo:
Insisto en que no hay que dejar que las funciones creen memoria asi por que si, mejor pasarle un buffer... y si es nesesario reservar memoria mejor en una clase para evitar los malditos Memory Leak...

Edito:

* Los nodos al igual que siguien un punto al siguiente elemento pueden tener un puntero al elemento anterior... Doblemente enlazada, en tu ejemplo solo tocaste la simple...
* Me parece mas optima la lista Doblemente enlazada!¡... aun que depende mucho de diversos criterios...

P.D.: http://www.calcifer.org/documentos/librognome/glib-lists-queues.html

Dulces Lunas!¡.

[dewolo]

si me habian enseniado sobre las listas simplemente enla<adas y las doblemente enlazadas, osea en un solo sentido o de ida y vuelta, pero casi nunca le encuentro aplicacion 

[CeroX901]

Estoy de acuerdo en eso, en mi U en programación básica fue el programa que me tocó hacer como proyecto final y hasta el día de hoy no le he visto ninguna aplicación ni base a las siguientes materias, he visto Prog Orientada a Objetos, Prog Avanzada y ahora estoy en Modelos I... Cosas mas importantes que deberían ser base en la carrera.

[darkvidhack]

Pienso que las listas enlazadas son una estructura de datos mucho más eficiente que los vectores (por ejemplo) en algunos aspectos, como la inserción de un elemento en algunos casos, mientras que para una lista enlazada, el tiempo del algoritmo para la inserción al principio es de O(1) (se hace directamente), para los arrays es de O(n), (hay que rrecorrer todo el vector para insertar, n=número de elementos), según para lo que las necesitemos... cada una tiene sus pros y sus contras

[brians444]

Creo que las listas enlazadas son muy importantes, son la base para las colas y pilas, estructuras muy usadas, en sistemas y otros.. Las pilas se acceden de manera Last in First Out (LIFO) es decir que el primer elemento en ingresar es el primero en salir.

Dichas pilas se implementan en C en forma de lista enlazada, para las cuales hay que definir varios metodos:

Push: Para insertar un elemento en la cima de la pila
Pop: Para obtener un elemento de la cima
Crear: Para crear la pila
Destruir: Para eliminar la memoria de todos los elementos almacenados

Tambien se puede implementar uno mas para saber si esta vacio, y en cuyo caso crearla.

Las colas colas son similares a las pilas solo que su manera de acceder a los datos es del tipo First In First Out (FIFO), o sea que el primer elemento en entrar es el primero en salir. Para las colas se definen metodos analogos a los de pilas.

Saludos