Es común que en un programa no sepamos de antemano cuántos datos vamos a insertar, ni siquiera al arrancar el programa, si no en el transcurso de la ejecución del mismo. Es por eso que necesitamos una estructura de datos que permita ir agregando de manera ordenada datos, y guardarlos en memoria. Para ello existen una serie de estructuras útiles, pero una de las más simples son las listas doblemente ligadas. En este tutorial mostraremos una implementación libre de este tipo de listas e invitamos a todos los principiantes a revisar la entrada en wikipedia sobre el tema para tener más elementos en esta lectura.

En el presente artículo presentamos nuestra implementación de estas estructuras de datos, para que las puedan usar en sus proyectos o estudiar. Mostraremos las partes básicas para su uso, así como una descripción básica del funcionamiento de una lista de este tipo. Si quieren usar el código fuente está disponible en github

Estas listas requieren una estructura base, que mantenga información sobre el primer nodo de la lista y el último. 

typedef struct dllist
{
    dlnode *start;
    dlnode *end;
    dl_comparator comp;
    dl_print print;
    dl_freefunc free_func;
}dllist;

Como vemos, mantenemos punteros al nodo de inicio y al de fin. También, para generalizar, se usan punteros a funciones, que permitirán al usuario definir funciones bascias cómo liberar memoria, comparar nodos e imprimir un nodo. Ahora bien, cada nodo tendrá un puntero al objeto que contiene, uno al nodo predecesor y otro al nodo posteior. Si el nodo es el primero su valor será NULL, al igual si es el último, su nodo posterior también será NULL. En la siguiente imágen se ilustra cómo es esto:

Tomado de wikipedia.

Para poder verlo con mayor detalle veamos la estructura en C de un nodo de una lista doblemente ligada.

typedef struct dlnode
{
    struct dlnode *next;
    struct dlnode *prev;
    void *data;
}dlnode;

Como ya hemos definido nuestras listas ligadas, necesitamos definir una serie de operaciones básicas. Estas son:

  • Crear lista
  • Agregar alemento a la lista (al inicio de la lista).
  • Agregar un elemento al final de la lista.
  • Buscar un nodo según valor.
  • Eliminar el primer nodo de la lista con el valor indicado.
  • Eliminar el primer elemento de la lista y obtener el nodo en una variable (pop).
  • Realizar un POP al final de la lista.
  • Liberar el espacio al objeto de lista.
  • Imprimir la lista.
  • Eliminar un nodo de la lista.
  • Agregar un nuevo nodo antes del nodo indicado.
  • Agregar un nuevo nodo después del nodo indicado.

Cómo podemos ver, hemos extendido las posibles opercaiones sobre la lista para facilitar su uso. Al ser esto una lista doblemente ligada, podemos modificar también elementos anteriors al actual, cómo le hemos visto en la lista de operaciones posibles. En general se recomienda usar listas doblemente ligadas sobre listas simples. Cada una de estas operaciones se pueden definir de la sigueinte manera:

dllist  *list_new(dl_comparator, dl_print, dl_freefunc);
int     list_add(dllist *, void *);
int     list_add_end(dllist *, void *);
dlnode  *list_search(dllist *, void *);
int     list_remove(dllist *, void *);
void    *list_pop(dllist *);
void    *list_pop_end(dllist *);
void    list_free(dllist *);
void    list_print(dllist *);
void    *list_delnode(dllist *, dlnode *);
int     list_addafternode(dlnode *, void *);
int     list_addbeforenode(dlnode *, void *);

Hemos usado las estructuras antes mencionadas para realizar las operaciones sobre la lista. Tambièn se requieren ciertas funciones. Estas se definen cómo:

typedef int (*dl_comparator)(void *, void *);
typedef int (*dl_print)(void *);
typedef int (*dl_freefunc)(void *);

Pero veamos cómo se usa esta lista doblemente ligada. Vamos a usar como objetos a guardar en la lista, simples números enteros. Pero al ser una lista general, se pueden usar cualquier tipo de objetos. Vamos a definir nuestras tres funciones, antes de crear la lista.

// Function that compares two objects. Returns 1 if equal, 0 if not. 
int 
comparator(void *a, void *b)
{
  if((int *)a == (void *)b)
    return 1;
  else;
    return 0;
}

//Function that print a object
int 
print(void *a)
{
  printf("%d\n", *((int *)a));
}

//Function that free object
int
free_o(void *a)
{
  free(a);
}

Esto es necesario, dado que necesitamos indicarle al compilador cómo manejar los punteros void *. Ahora ya podemos crear nuestra lista.

  dllist *list;
list = list_new(&comparator, &print, &free_o);

La función reserva el espacio en memoria por nosotros. Ahora agregemos algunos elementos a la lista. 

  int a=1,b=2,c=3,d=4;
list_add(list, &a); list_add(list, &b); list_add(list, &c);

Para ver lo que ha pasado, podemos impirmir la lista.

  list_print(list);

Y obtendremos:

0: 3
1: 2
2: 1

Lo cual significa que primero hemos agregado a, luego b, y c. El primer elemento a, que contiene al uno permite al segundo elemento ocupar la primera posición de la lista y así subsecuentemente. Si quisiéramos agregar un elemento al final de la lista se necesita hacer lo siguiente:

  list_add_end(list, &d);

Con el nuevo resultado:

0: 3
1: 2
2: 1
3: 4

Ahora bien. Para buscar un nodo que contenga un valor dadao, digamos que 2, y recuperar el nodo que lo contiene, realizaremos la siguiente operación:

  node = list_search(list, &b); 
  print(node->data);

Hemos también impreso el dato que se contiene en ese nodo, que es 2 en la salida. Una vez que tenemos un nodo, es posible manipularlo o eliminarlo. Para ello:

  list_delnode(list, node);
  list_print(list);

Y ahora ya no está el elemento 2:

0: 3
1: 1
2: 4

 También podemos eliminar el primer elemento de la lista mediante la operación pop. Obtendremos el nodo como resultado de la función. Veamos cómo hacerlo:

  node = list_pop(list);
  list_print(list);

 Con la lista resultante:

  node = list_pop(list);
  list_print(list);

La librería que hemos presentado maneja listas doblemente ligadas. Si quieres saber cómo se realizaron estas operaciones, te invitamos a ver el código fuente del programa, que está en github. Esperamos esta presentación de listas ligadas ha sido útil y el código pueda ser usado en sus proyectos. 

Código Fuente

 

 

Share This