Listas de encadeamento simples
Contato
- Jean Paulo Martins (jeanmartins utfpr edu br)
- Sala 105, Bloco S (UTFPR - Campus Pato Branco)
Conteúdo
Listas encadeadas
Da mesma forma que vetores (arrays), listas encadeadas também são estruturas sequenciais. Ou seja, os elementos armazenados em tais estruturas de dados obedecem uma certa ordem linear, em que um sucede (ou precede) outro elemento. Nos vetores, essa ordem é implementada diretamente em memória, ou seja, dado um elemento $v[i]$ em um vetor, o elemento $v[i+1]$ está na posição de memória subsequente.
valor := v[0] v[1] v[2] ... v[n-1]
endereço := x x+1 x+2 ... x+n-1
Já listas encadeadas, a situação é um pouco diferente. Apesar dos elementos ainda sim manterem uma ordem sequencial, essa ordem não precisa ser refletida nas posições de memória que eles ocupam. Deste modo, estruturas adicionais são necessárias para indicar qual elemento sucede ou precede outro. Nesta seção iremos tratar de uma implementação bem restrita de listas encadeadas, as listas de encadeamento simples forward_list.
Listas de encadeamento simples
Uma lista de encadeamento simples (singly-linked list) implementa a ideia de uma lista unidirecional. Isto significa que cada elemento somente tem conhecimento sobre o próximo elemento da lista, e não do anterior. Esta característica é ilustrada através de uma aresta direcionada (seta) ligando o elemento ao seu próximo.
a:(valor, b) -> b:(valor, c) -> c:(valor, prox) -> ...
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.
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ó
} node;
Antes de implementarmos funções para a manipulação da forward_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 simples forward_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;
return n;
}
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.
Criação dos nós
Dada a função new_node, a etapa de criação (alocação de memória no Heap) dos nós é trivial. Neste exemplo criamos três nós, $a$, $b$ e $c$; contendo, respectivamente, os valores inteiros $0, 1, 2$.
// Etapa de criação dos nós de lista
int main() {
node* a = new_node(0); // (0, NULL)
node* b = new_node(1); // (1, NULL)
node* c = new_node(2); // (2, NULL)
}
Encadeamento dos nós
Como cada nó foi alocado por uma chamada independente à malloc, fica evidente que não temos controle sobre suas posições de memória. Isso implica que o nó b, por exemplo, pode não estar em uma posição de memória subsequente à posição de a.
valor := (b, NULL) ... (c, NULL) ... (a, NULL)
endereço := x ... y ... z
Nessas condições, o que definirá a ordem desses nós será o encadeamento entre eles. O termo encadear, neste contexto, significa apenas dizer qual dos nós será o próximo de qual outro nó. Para clarificar, vamos estender o exemplo acima de modo a criar o encadeamento ilustrado a seguir.
a:(0, b) -> b:(1, c) -> c:(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->next = b; // (0, b)
b->next = c; // (1, c), (2, 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).
Inserção de um novo nó
Inserção no início
De acordo com a posição de inserção, existem três formas de se inserir um novo nó em uma lista já existente. A primeira, e mais simples neste caso, é a inserção no início da lista. Esse tipo de inserção exige apenas que um novo nó aponte para o atual início. Considerando o exemplo anterior, vamos inserir node* d no início da lista atual, criando a lista ilustrada abaixo.
d:(3, a) -> a:(0, b) -> b:(1, c) -> c:(2, NULL)
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->next = b; // (0, b)
b->next = c; // (1, c), (2, NULL)
// Inserção no início
node* d = new_node(3); // Criação do nó (3, NULL)
d->next = a; // (3, a)
}
Observemos então, que para a inserção no início precisamos apenas de referências ao nó que atualmente está no início (node* a) e ao novo nó (node* d).
Inserção no final
O segundo tipo mais simples de inserção é aquela que introduz um novo elemento no final da lista encadeada. Para isso, precisaremos apenas de referências ao nó que atualmente é o último da lista (node* c), e o novo nó (node* e).Considerando o exemplo anterior, vamos inserir node* e ao fim da lista atual, criando a lista ilustrada abaixo.
d:(3, a) -> a:(0, b) -> b:(1, c) -> c:(2, e) -> e:(4, NULL)
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->next = b; // (0, b)
b->next = c; // (1, c), (2, NULL)
// Inserção no início
node* d = new_node(3); // Criação do nó c:(3, NULL)
d->next = a; // (3, a)
// Inserção no final
node* e = new_node(4); // Criação do nó e:(4, NULL)
c->next = e;
}
Inserção no meio
Por fim, trataremos do tipo de inserção mais genérico, o que nos permite inserir um novo nó em qualquer posição da lista encadeada. Como forma de exemplo, suponhamos que queremos inserir um novo nó (node* f) na posição $2$ da lista, ou seja, entre os nós a e b. Após essa inserção a lista teria a seguinte ordem.
d:(3, a) -> a:(0, f) -> f:(5, b) -> b:(1, c) -> c:(2, e) -> e:(4, NULL)
Para melhor compreendermos os passos necessários para implementar essa inserção, vamos focar na parte de interesse da lista, comparando o antes e o depois.
a:(0, b) -> b:(1, c)
a:(0, f) -> f:(5, b) -> b:(1, c)
Talvez o fato mais evidente seja que nada foi alterado em b. De fato, para inserirmos um novo nó numa posição $i$ qualquer, basta que tenhamos a referência ao nó na posição $i-1$ (a, neste caso). Vejamos como isso é feito em código:
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->next = b; // (0, b)
b->next = c; // (1, c), (2, NULL)
// Inserção no início
node* d = new_node(3); // Criação do nó c:(3, NULL)
d->next = a; // (3, a)
// Inserção no final
node* e = new_node(4); // Criação do nó e:(4, NULL)
c->next = e;
// Inserção no meio: entre a e b
node* f = new_node(5); // Criação do nó f:(5, NULL)
f->next = a->next; // Aqui ambos apontam para b
a->next = f; // Aqui a aponta para f
}
Implementação de listas de encadeamento simples
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ó
} node;
typedef struct {
node* head;
} 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);