Listas de encadeamento duplo

Uma lista de encadeamento duplo (doubly-linked list) implementa a ideia de uma lista bidirecional. Isto significa que cada elemento tem conhecimento sobre seu próximo e seu anterior na lista. Esta característica é ilustrada através de uma aresta bidirecionada ligando o elemento ao seu próximo.

a:(NULL, valor, b) <-> b:(a, valor, c) <-> c:(b, valor, NULL)

Assim como nas listas de encadeamento simples, o primeiro aspecto a ser notado é que um elemento de lista (um nó, node), não é um tipo de dado simples. Isto é necessário visto que cada elemento precisa, além de armazenar um valor, armazenar um ponteiro para o próximo e um ponteiro para o anterior.

Na linguagem C, este tipo de estrutura é implementada por uma struct. Utilizaremos a seguinte definição:

#define Type int
typedef struct _node {
    Type value;             // Valor armazenado
    struct _node* next;   // Endereço do próximo nó
    struct _node* prev;   // Endereço do próximo nó
} node;

Antes de implementarmos funções para a manipulação da list é importante compreendermos na prática o que os conceitos até então descritos realmente significam. Com esse fim, algums exemplos serão demonstrados a seguir.

Detalhes de implementação

Como tem sido convencionado até então, vamos definir uma função que implemente a alocação de memória para node que serão utilizados como elementos da nossa lista de encadeamento duplo list.

// Aloca memória para um 'node' e define o endereço do próximo como NULL
node* new_node(Type valor) {
    node* n = malloc(sizeof(node));
    n->value = valor;
    n->next  = NULL;
    n->prev  = NULL;
    return n;
}

Observe que a única diferença deste node para aquele utilizado em listas de encadeamento simples é o campo adicional prev, que também precisa ser inicializado.

Consideremos agora a criação de uma lista de encadeamento simples feita manualmente. Para isso a única coisa que precisamos é criar vários node e definir qual apontará para qual.

Encadeamento dos nós

O encadeamento no contexto de listas duplamente encadeadas implica em dizer para cada nó, qual será o seu próximo e qual será seu anterior. Para clarificar, vamos criar o encadeamento ilustrado a seguir.

a:(NULL, 0, b) <-> b:(a, 1, c) <-> c:(b, 2, NULL)

Observe, que tanto b quanto c são ponteiros, portanto representam o endereço de memória no Heap de uma estrutura node.

int main() {
    // Criação dos nós
    node* a = new_node(0); // (0, NULL)
    node* b = new_node(1); // (1, NULL)
    node* c = new_node(2); // (2, NULL)
    
    // Encadeamento
    a->prev = NULL;
    a->next = b; // (NULL, 0, b)
    
    b->prev = a; // b:(a, 1, NULL)
    b->next = c; // b:(a, 1, c)
    
    c->prev = b; // c:(b, 2, NULL)
    c->next = NULL;
}

Este exemplo criou manualmente uma lista encadeada simples de três elementos. Como o último elemento, o nó c, não possui referência a próximo (c->next == NULL) isso nos indica que ele está no final da lista (tail). Pela mesma ideia, o nó a está no início da lista (head) pois ele não possui antecessor (a->prev == NULL).

Todas as formas de inserção e remoção funcionam da mesma forma em uma lista duplamente encadeada, a única diferença é que neste caso ponteiros para o nó anterior também precisam ser atualizados.

Implementação de listas de encadeamento duplo

Nesta implementação de lista, armazenaremos informações adicionais na estrutura list. Esses campos adicionais tem como objetivo melhorar a eficiência das operações de inserção no final da lista. Para isso consideraremos as seguintes informações.

Considerando a estrutura list definida a seguir, implemente todas as funcionalidades que foram implementadas para vector.

// *** list.h *** 
#define Type int
typedef struct _node {
    Type value;             // Valor armazenado
    struct _node* next;   // Endereço do próximo nó
    struct _node* prev;   // Endereço do nó anterior
} node;

typedef struct {
    int size;   // Número de elementos na lista
    node* head; // Ponteiro para o primeiro elemento
    node* tail; // Ponteiro para o último elemento
} list;

// Aloca memória inicial para o vetor
list* new_list();
// Desaloca a memória de v->data e do próprio v.
void free_list(list* v);

// Funções de remoção de elementos
Type list_pop_back(list* v);
Type list_pop_front(list* v);
Type list_erase(list* v, int i);

// Funções de inserção de elementos
void list_insert(list* v, Type value, int i);
void list_push_back(list* v, Type value);
void list_push_front(list* v, Type value);

bool list_empty(list* v);
int list_size(list* v);
void list_print(list* v, const char* format);

Contato

Listas de encadeamento duplo

Detalhes de implementação

Encadeamento dos nós

Implementação de listas de encadeamento duplo

#

Referências