Listas de encadeamento duplo
Contato
- Jean Paulo Martins (jeanmartins utfpr edu br)
- Sala 105, Bloco S (UTFPR - Campus Pato Branco)
Conteúdo
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.
Alocação de nós de lista
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.
Encadeamento dos nós
O encadeamento no contexto de listas duplamente encadeadas implica em definir 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)
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. Esses campos adicionais tem como objetivo melhorar a eficiência das operações de inserção no final da lista.
Considerando os componentes head e tail descritos anteriormente, uma estrutura list para listas de encadeamento duplo pode definida como.
struct TAD_LIST {
int size; // Número de elementos na lista
node* head; // Ponteiro para o primeiro elemento
node* tail; // Ponteiro para o último elemento
} list;
Adicionalmente, inserimos o campo size o qual deverá armazenar a quantidade elementos presente na lista. Isso permitirá que a operação list_size() seja muito mais eficiente, pois não será mais necessário percorrer toda a lista para determinarmos o seu tamanho.
Interface para o tipo abstrato LISTA
O tipo de dados abstrato LISTA define-se por suas funcionalidades, as quais nos permitem manipular os dados armazenados por meio de inserções e remoções que podem ser efetuadas em qualquer posição da lista.
A implementações vector.c e forward_list.c vistas anteriormente, provêm todas as funcionalidades de lista definidas no arquivo list.h representado abaixo.
// Arquivo list.h
#include <stdbool.h>
#define Type int
// Uma definição abstrata da struct que representará a lista
typedef struct TAD_LIST 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);
// Funções de acesso aos dados
Type* list_at(list* v, int pos);
void list_set(list* v, int pos, Type value);
void list_print(list* v);
// Retorna a quantidade de elementos na lista
int list_size(list* v);
// Retorna true se a lista está vazia, false caso contrário.
bool list_empty(list* v);
A implementação de listas duplamente encadeadas oferece outra possibilidade de implementação do tipo abstrato LISTA e, portanto, também deverá implementar as funcionalidades descritas em list.h.
Implementação de list.c
Seguindo o mesmo padrão de desenvolvimento proposto até então, a implementação da lista duplamente encadeada deverá ser feita em um arquivo list.c, o qual está, em parte, definido abaixo.
// *** list.c ***
#include "list.h"
#include <stdlib.h>
// Nó de lista
typedef struct _node {
Type value; // Valor armazenado. 'Type' está definido em list.h
struct _node* next; // Endereço do próximo nó
struct _node* prev;
} node;
// Estrutura da lista
struct TAD_LIST {
int size;
node* head;
node* tail;
};
// 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;
}
// 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) {
}
// Funções de acesso aos dados
Type* list_at(list* v, int pos) {
}
void list_set(list* v, int pos, Type value) {
}
void list_print(list* v) {
}
// Retorna a quantidade de elementos na lista
int list_size(list* v) {
}
// Retorna true se a lista está vazia, false caso contrário.
bool list_empty(list* v) {
}