Listas Duplamente Ligadas (inteiros)
From 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;
}