Listas Duplamente Ligadas (genérica)

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

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);
 }