RocketTheme Joomla Templates
     
Inicio Noticias SW Dev Lista enlazada simple en C
Lista enlazada simple en C PDF Imprimir Correo electrónico
swdev
Escrito por Jorge Riquelme Santana   
Martes 08 de Mayo de 2007 17:06

Con este artículo quiero comenzar una serie de aportes filantrópicos (sin ánimo de lucro) a otros compañeros samurais de la informática, que en algún momento de su esforzada vida académica deben enfrentar cierto tipo de problemas típicos.

En C, una lista enlazada simple es una estructura de datos compuesta por una serie de nodos, unidos a través de punteros. La lista se denomina “simple” porque cada nodo apunta al siguiente, pero no al que lo precede, por lo que sólo se puede recorrer la estructura de datos de manera unidireccional. Es evidente que el mayor bemol de este tipo de listas es que hay que pasar por los K primeros nodos para llegar al K-ésimo. Una buena opción es hacerle una “cabecera” a la lista, donde guardar cosas como el número de elementos y un puntero al último nodo; así se evitan recorridos innecesarios al agregar nuevos nodos y al averiguar el largo de la lista. Un esquema clarifica la situación:

 

Lista enlazada simple
Lista enlazada simple

 

La cabecera guarda 3 datos:

  • cantidad de nodos
  • puntero al primer nodo
  • puntero al ultimo nodo

Cada nodo guarda:

  • puntero al dato guardado
  • puntero al siguiente nodo

Entonces, son necesarias dos estructuras: una que represente a la cabecera (ListHeader) y otra que represente al nodo (ListNode).

  1.  
  2. typedef struct ListNode
  3. {
  4.         void* data;
  5.         struct ListNode* next;
  6. }ListNode;
  7.  
  8. typedef struct ListHeader
  9. {       
  10.         int size;
  11.         ListNode* first,*last;
  12. }ListHeader;
  13.  
  14. typedef ListHeader* List;
  15.  
  16.  
  

El último typedef tiene por objetivo mejorar la legibilidad del código y esconder a ojos del usuario la estructura interna de la lista. La idea es que el usuario en todo momento sólo interactúe con una variable de tipo “List”; nunca debería tener que manejar las estructuras ListHeader o ListNode directamente; recuerda uno de los dogmas del evangelio de Igeniería/Arquitectura de Software: Alta cohesión y bajo acoplamiento.

Las operaciones más comunes sobre una lista, que implementaremos mediante funciones, son:

  • crear una lista
  • agregar un dato al final
  • insertar un dato en cierta posición
  • borrar un dato
  • ver cuantos datos tiene la lista
  • recuperar el primer dato
  • recuperar el ultimo dato
  • recuperar el i-ésimo dato
  • verificar si existe un dato
  • borrar la lista

Con esto “las hacemos todas” tongue. Sin embargo, nuestros sentidos ninja nos indican que recorrer la lista haciendo sucesivas llamas  a “recuperar el i-ésimo dato” sería muy ineficiente... “eso no es bueno” (pues pasaríamos una y otra vez los primeros nodos de la lista). Lo deseable en esta situación sería tener una especie de puntero con el cual ir avanzando sin perder la posición actual entre cada “salto”. Acá es donde entra en escena el patrón Iterator. Un iterador es una variable que nos permitirá realizar un recorrido eficiente, manteniendo oculta la estructura interna de la lista al usuario.  Entonces, agregamos un nuevo tipo (ListIterator) y unas cuantas funciones más:

  1.  
  2. typedef ListNode* ListIterator;
  3.  
  4.  
  

  • Crear iterador
  • recuperar dato al que apunta el iterador
  • avanzar el iterador

Otra manera común de operar sobre todos los elementos de una lista es evaluar alguna función (que generalmente se denomina callback) con cada dato. La ventaja de este método es que el usuario sólo se preocupa de hacer la funcion callback y la lista es la que realiza el recorrido. Agregamos un nuevo tipo (puntero a callback) y una nueva función:

  1.  
  2. typedef void (*ListCallback)(void* data,void* userData);
  3.  
  4.  
  

  • evaluar una función con cada dato

Ahora, hay que implementar cada operación think. Primero, haré una función que simplemente construye un nodo y lo inicializa con cierto valor:

  1.  
  2. ListNode* newNode(void* data)
  3. {
  4.         ListNode* node=malloc(sizeof(ListNode));
  5.         node->data=data;
  6.         node->next=NULL;
  7.         return node;
  8. }
  9.  
  

 

Crear una lista

Una lista vacía en nuestro caso es simplemente una estructura ListHeader con el campo size en 0 y los punteros first y last en NULL.

  1.  
  2. List ls_create()
  3. {
  4.         ListHeader* list=malloc(sizeof(ListHeader));
  5.         list->size=0;
  6.         list->first=NULL;
  7.         list->last=NULL;
  8.         return list;
  9. }
  10.  
  

Agregar un dato al final

Creamos una estructura ListNode y la incializamos. Debemos tener cuidado de tratar correctamente el caso en que la lista está vacía, situación en la que hacemos que first y last apunten al nuevo nodo. Si la lista ya tiene elementos, hacemos que el ultimo nodo actual apunte al nuevo, luego dejamos al nuevo nodo como último haciendo que last lo apunte.

  1.  
  2. void ls_append(List list,void* data)
  3. {
  4.         ListNode* node=newNode(data);
  5.         list->size++;
  6.         
  7.         if(list->last)
  8.         {
  9.                 list->last->next=node;
  10.                 list->last=node;
  11.         }
  12.         else
  13.         {
  14.                 list->first=node;
  15.                 list->last=node;
  16.         }
  17. }
  18.   
  

Insertar un dato en cierta posición

En el caso que el usuario desee insertar el nodo al inicio la tenemos fácil porque usamos el puntero “first” de la cabecera. En cambio, para insertar el nodo en cierto indice i>0 debemos recorrer la lista hasta el nodo i-1, el cual quedará apuntando al nuevo nodo cuando modifiquemos su campo next. En ambos casos, finalmente, hacemos que el nuevo nodo apunte al ex nodo i.

  1.  
  2.  void ls_insert(List list,int index,void* data)
  3. {
  4.         list->size++;
  5.  
  6.         if(index==0)
  7.         {
  8.                 ListNode* node=newNode(data);
  9.                 node->next=list->first;
  10.                 list->first=node;
  11.         }
  12.         else if(index<list->size)
  13.         {
  14.                 int i;
  15.                 ListNode* p=list->first;
  16.                 ListNode* node=newNode(data);
  17.                 for(i=0;i<index-1;i++)
  18.                         p=p->next;
  19.                 node->next=p->next;
  20.                 p->next=node;
  21.         }
  22. }
  23.    
  

Borrar un dato

Para borrar un dato debemos posicionarnos en el nodo correspondiente de la misma forma que lo hicimos en la función ls_insert. En esta oportunidad el nodo i-1 debe quedar apuntando al nodo i+1, o sea hacer que el campo next del nodo i-1 guarde el valor del campo next del nodo i. Luego se hace un free del nodo i.

  1.  
  2. void ls_remove(List list,int index)
  3. {
  4.         if(index==0)
  5.         {
  6.                 if(list->first)
  7.                 {
  8.                         ListNode* p=list->first;
  9.                         if(list->first==list->last)
  10.                                 list->last=NULL;
  11.                         list->first=list->first->next;
  12.                         free(p);
  13.                         list->size--;
  14.                 }
  15.         }
  16.         else if(index<list->size)
  17.         {
  18.                 int i;
  19.                 ListNode* p,*q;
  20.                 p=list->first;
  21.                 for(i=0;i<index-1;i++)
  22.                         p=p->next;
  23.                 q=p->next;
  24.                 p->next=p->next->next;
  25.                 if(list->last==q)
  26.                         list->last=p->next;
  27.                 free(q);
  28.                 list->size--;
  29.         }
  30. }
  31.    
  

Ver cuantos datos tiene la lista

Simplemente retornamos el campo size de la cabecera.

  1.  
  2.  int ls_size(List list)
  3. {
  4.         return list->size;
  5. }
  6.    
  

Recuperar el primer dato

Si first no es NULL, retornamos el valor que guarda.

  1.  
  2. void* ls_first(List list)
  3. {
  4.         if(list->first)
  5.                 return list->first->data;
  6.         else
  7.                 return NULL;
  8. }
  9.   
  

Recuperar el ultimo dato

Si last no es NULL, retornamos el valor que guarda.

  1.  
  2.  void* ls_last(List list)
  3. {
  4.         if(list->last)
  5.                 return list->last->data;
  6.         else
  7.                 return NULL;
  8. }
  9.    
  

Recuperar el i-ésimo dato

Hay que buscar el nodo i de la misma manera que en la funciones ls_insert se buscó el i-1, y retornar el campo data. Podemos aprovechar los punteros first y last para los casos en que el indice es 0 o size-1. También debemos tener cuidado de tratar correctamente el caso en que el parámetro i es inválido. 

  1.  
  2.  void* ls_dataAt(List list,int index)
  3. {
  4.         if(index==0)
  5.         {
  6.                 if(list->first)
  7.                         return list->first->data;
  8.                 else
  9.                         return NULL;
  10.         }
  11.         else if(index==list->size-1)
  12.         {
  13.                 return list->last->data;
  14.         }
  15.         else if(index>=list->size)
  16.                 return NULL;
  17.         else
  18.         {
  19.                 int i;
  20.                 ListNode* p=list->first;
  21.                 for(i=0;i<index;i++)
  22.                         p=p->next;
  23.                 return p->data;
  24.         }
  25. }
  26.    
  

Verificar si existe un dato

Sólo debemos recorrer la lista avanzando desde el nodo first al last, y verificar en cada iteración si el valor guardado por el campo data corresponde con el parámetro data.

  1.  
  2.  int ls_find(List list,void* data)
  3. {
  4.         ListNode* p=list->first;
  5.         while(p)
  6.         {
  7.                 if(p->data==data)
  8.                         return 1;
  9.                 p=p->next;
  10.         }
  11.         return 0;
  12. }
  13.    
  

Borrar la lista

En este caso se recorre la lista, pero en cada paso se va liberando la memoria usada por el nodo actual, teniendo cuidado de no perder el resto de la lista.

  1.  
  2.  void ls_delete(List list,int freeData)
  3. {
  4.         ListNode* p=list->first;
  5.         while(p)
  6.         {
  7.                 list->first=list->first->next;
  8.                 if(freeData)
  9.                         free(p->data);
  10.                 free(p);
  11.                 p=list->first;
  12.         }
  13.         free(list);
  14. }
  15.    
  

Crear iterador

Como un iterador es sólo un puntero a nodo, buscamos el i-ésimo nodo y lo retornamos.

  1.  
  2. ListIterator ls_iterator(List list,int index)
  3. {
  4.         if(index>=list->size)
  5.                 return NULL;
  6.         else
  7.         {
  8.                 int i;
  9.                 ListNode* p=list->first;
  10.                 for(i=0;i<index;i++)
  11.                         p=p->next;
  12.                 return p;
  13.         }
  14. }
  15.    
  

Recuperar dato al que apunta el iterador

Retornamos el campo data del iterador. Siempre cuidamos de que no nos pasen un gol con un puntero NULL.

  1.  
  2. void* ls_data(ListIterator it)
  3. {
  4.         if(it)
  5.                 return it->data;
  6.         else
  7.                 return NULL;
  8. }
  9.     
  

Avanzar el iterador

Verificamos la validez del puntero al iterador y que el iterador mismo no sea NULL. Hacemos que el iterador quede apuntando a su campo next.

  1.  
  2. void ls_next(ListIterator* it)
  3. {
  4.         if(it && *it)
  5.                 (*it)=(*it)->next;
  6. }
  7.     
  

Evaluar una función con cada dato

Por último, la función encargada de recorrer la lista llamando a un callback, donde la única novedad es el llamado a la función provista por el usuario (con el campo data como parámetro, además de userData) que tiene el prototipo definido al principio.

  1.  
  2. void ls_callback(List list,ListCallback callback,void* userData)
  3. {
  4.         ListNode* p=list->first;
  5.         while(p)
  6.         {
  7.                 (*callback)(p->data,userData);
  8.                 p=p->next;
  9.         }
  10. }
  11.      
  

 

Programa ejemplo

Ahora, a poner en acción nuestra super lista cool. La función printLength es nuestra callback de prueba, que se limita a tirar por pantalla el largo de string que espera recibir en el parámetro data. 

  1.  
  2. #include <stdio.h>
  3. #include <string.h>
  4. #include "list.h"
  5.  
  6. void printLength(void* data,void* userData)
  7. {
  8.     printf("largo de \"%s\" es %d\n",(char*)data,strlen((char*)data));
  9. }
  10.  
  11. int main()
  12. {
  13.     char* sz1="uno";
  14.     char* sz2="dos";
  15.     char* sz3="tres";
  16.     char* sz4="cuatro";
  17.  
  18.     List list;
  19.     ListIterator it;
  20.  
  21.     list=ls_create();
  22.     ls_append(list,sz1);
  23.     ls_append(list,sz3);
  24.     ls_insert(list,1,sz2);
  25.     ls_append(list,sz4);
  26.  
  27.     printf("hay %d elementos\n",ls_size(list));
  28.     printf("el primer elemento es \"%s\"\n"
  29.                                     ,(char*)ls_first(list));
  30.     printf("el elemento con indice 1 es \"%s\"\n"
  31.                                     ,(char*)ls_dataAt(list,1));
  32.     printf("el elemento con indice 2 es \"%s\"\n"
  33.                                     ,(char*)ls_dataAt(list,2));
  34.     printf("el ultimo elemento es \"%s\"\n"
  35.                                     ,(char*)ls_last(list));
  36.  
  37.     printf("\nborrando el elemento con indice 2\n");
  38.     ls_remove(list,2);
  39.  
  40.     printf("\n***Listando con iterador:\n");
  41.     it=ls_iterator(list,0);
  42.     while(it)
  43.     {
  44.         printf("%s\n",(char*)ls_data(it));
  45.         ls_next(&it);
  46.     }
  47.  
  48.     if(!ls_find(list,sz3))
  49.     {
  50.         ls_insert(list,2,sz3);
  51.         printf("\ninsertando sz3 en indice 2\n");
  52.     }
  53.  
  54.     printf("\n***Recorriendo con callback\n");
  55.     ls_callback(list,printLength,NULL);
  56.  
  57.     ls_delete(list,0);
  58.  
  59.     return 0;
  60. }
  61.      
  

El programa produce la siguiente salida en nuestro amigo valgrind: 

totex@trauko ~/work/list $ valgrind --leak-check=yes ./test
==28663== Memcheck, a memory error detector.
==28663== Copyright (C) 2002-2007, and GNU GPL'd, by Julian Seward et al.
==28663== Using LibVEX rev 1732, a library for dynamic binary translation.
==28663== Copyright (C) 2004-2007, and GNU GPL'd, by OpenWorks LLP.
==28663== Using valgrind-3.2.3, a dynamic binary instrumentation framework.
==28663== Copyright (C) 2000-2007, and GNU GPL'd, by Julian Seward et al.
==28663== For more details, rerun with: -v
==28663==
hay 4 elementos
el primer elemento es "uno"
el elemento con indice 1 es "dos"
el elemento con indice 2 es "tres"
el ultimo elemento es "cuatro"

borrando el elemento con indice 2

***Listando con iterador:
uno
dos
cuatro

insertando sz3 en indice 2

***Recorriendo con callback
largo de "uno" es 3
largo de "dos" es 3
largo de "tres" es 4
largo de "cuatro" es 6
==28663==
==28663== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 7 from 1)
==28663== malloc/free: in use at exit: 0 bytes in 0 blocks.
==28663== malloc/free: 6 allocs, 6 frees, 52 bytes allocated.
==28663== For counts of detected errors, rerun with: -v
==28663== All heap blocks were freed -- no leaks are possible.

Aunque uno no debe confiar ciegamente en este tipo de herramientas, al menos es un buen indicio de que las cosas funcionan relativamente bien. Cualquier falla, me la indicas discretamente por email o me dejas en verguenza públicamente con un comentario dotsmile

 

Archivos adjuntos:
Descargar este archivo (linked_list.tar.gz)linked_list.tar.gz[implementación lista enlazada simple en C]1 Kb
Tags Lista enlazada - Linked List - C - iterator - callback
Compartir
Hits: 5878
Comentarios (5)add comment

meriadox said:

...
Chuaa!... te esmeraste!... yo no anhelo los tiempos en que tenía que programar... a mi me enseñaron Java... ahora que existe MatLab invertir una matriz es más fácil que fingir un eructo...

Saludos!
mayo 09, 2007

kamonn said:

...
Ta bueno el aporte para los tipicos despistados que no estan cachando una en estructura de datos ;D ;D
mayo 12, 2007

kamonn said:

...
pd: retoca el template pues esta faltando un poco de fondo blanco a la derecha
mayo 12, 2007

ToTeX said:

...
no me había dado cuenta, con el firefox no se nota porque usa una fuente más pequeña al parecer. Ahora en el opera lo noté, en una parte el código estaba muy "ancho" :o
junio 03, 2007

soto said:

...
Muchas gracias por el aporte. Me ha echado un cable de la leche
septiembre 01, 2009

Escribir comentario
corto | largo

busy
Siguiente >