Wiki**3

Estruturas de Suporte

Estruturas de suporte a uma lista duplamente ligada.

 struct iitem {
   int value;
   struct iitem *next;
   struct iitem *prev;
 };
 typedef struct iitem Item;
 typedef Item *ItemPtr;

Na implementação, consideram-se ainda os seguintes ponteiros: serão utilizados para referenciar as duas sentinelas utilizadas nos algoritmos que manipulam a lista.

 static ItemPtr first = NULL, last = NULL;

Reserva de Memória para Items

 static ItemPtr alloc_item() {
   return (ItemPtr)malloc(sizeof(IntItem));
 }

Inicialização e Destruição da Lista

A função init define duas sentinelas, apontadas por first e last.

   void init() {
     first = alloc_item();
     last  = alloc_item();
     first->next = last;
     last->prev  = next;
     first->prev = last->next = NULL;
   }
   

Note-se que a função que destrói a lista não afecta os items.

   void destroy() {
     while (px = first) {
       first = first->next;
       free(px);
     }
     first = last = NULL;
   }

Inserção de Items na Lista

   int insert(int value) {
     ItemPtr px, ni;

     for (px = first->next;
          px != last && px->value < value;
          px = px->next);

     if (px != last && px->value == value)
       return 0;  /* no dups */

     ni = alloc_item();
     ni->value = value;
     px->prev->next = ni;
     ni->prev = px->prev;
     ni->next = px;
     px->prev = ni;

     return 1;
   }

Remoção de Items da Lista

   int delete(int value) {
     ItemPtr px;

     for (px = first->next;
          px != last && px->value < value;
          px = px->next);

     if (px && px->value == value) {
       px->prev->next = px->next;
       px->next->prev = px->prev;
       free(px);
       return 1;
     }

     return 0;
   }

Ver Também

• Lista duplamente ligada para dados genéricos