Listas Duplamente Ligadas (genérica)

Note-se que esta lista não está implementada como um ADT de primeira ordem.

Apesar de não ser um ADT de 1ª ordem, esta lista implementa, no entanto, um tipo de dados de 1ª ordem e admite várias instâncias num mesmo programa.

Ficheiro lista.h

 #include <stdlib.h>

 struct _node {                 /* representação de um nó */
   void *data;
   struct _node *prev, *next;
 };
 typedef struct _node node;
 
 struct _dllist {               /* representação da uma lista */
   node *first, *last;
   size_t nelems;
 };
 typedef struct _dllist dllist;
 
 enum result { FAILURE = 0, SUCCESS };

Ficheiro lista.c

Nesta implementação faz-se uso da macro assert para garantir que as funções não recebem parâmetros inválidos.

 #include <assert.h>
 #include “lista.h”
 
 void init(dllist *l) {
   assert((l));
   l->first = l->last = NULL;
   l->nelems = 0;
 }

Predicados

Predicados sobre propriedades da lista.

 unsigned char vazia(dllist *l) {
   assert((l));
   return !l->nelems;
 }
 
 size_t comprimento(dllist *l) {
   assert((l));
   return l->nelems;
 }

Inserção e Remoção de Elementos

Inserção de elementos no início da lista.

 enum result push_front(dllist *l, void *data) {
   assert((l));
   node *elm = (node*)malloc(sizeof(node));
   if (elm == NULL) return FAILURE;
   if (vazia(l)) l->last = elm;
   if (l->first) l->first->prev = elm;
   elm->next = l->first;
   elm->prev = NULL;
   elm->data = data;
   l->first  = elm;
   l->nelems++;
   return SUCCESS;
 }

Remoção de elementos do início da lista.

 void *pop_front(dllist *l) {
   assert((l));
   if (vazia(l)) return NULL;
   l->nelems--;
   node *ptr  = l->first;
   void *data = ptr->data;
   l->first   = ptr->next;
   if (l->first) l->first->prev = NULL;
   else l->last = NULL;
   free(ptr);
   return data;
 }

Inserção de elementos no fim da lista.

 enum result push_back(dllist *l, void *data) {
   assert((l));
   node *elm = (node*)malloc(sizeof(node));
   if (elm == NULL) return FAILURE;
   if (vazia(l)) l->first = elm;
   if (l->last) l->last->next = elm;
   elm->next = NULL;
   elm->prev = l->last;
   elm->data = data;
   l->last   = elm;
   l->nelems++;
   return SUCCESS;
 }

Remoção de elementos do início da lista.

 void *pop_back(dllist *l) {
   assert((l));
   if (vazia(l)) return NULL;
   l->nelems--;
   node *ptr  = l->last;
   void *data = ptr->data;
   l->last    = ptr->prev;
   if (l->last) l->last->next = NULL;
   else l->first = NULL;
   free(ptr);
   return data;
 }

Iteração Sobre a Lista

Função que visita cada elemento da lista (do princípio para o fim).

 void visit_forward(dllist *l, void (*visit)(void*)) {
   assert((l && visit));
   node *cursor = l->first;
   for (; cursor != NULL; cursor = cursor->next)
     (*visit)(cursor->data);
 }

Função que visita cada elemento da lista (do fim para o princípio).

 void visit_backward(dllist *l, void (*visit)(void*)) {
   assert((l && visit));
   node *cursor = l->last;
   for (; cursor != NULL; cursor = cursor->prev)
     (*visit)(cursor->data);
 }