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
}
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ção vector da APS1 é uma possível implementação do tipo abstrato LISTA que utiliza um vetor (array) para amazenamento dos elementos. No entando diversas outras implementações são possíveis. Para tornar explícito o fato de que todas essas possíveis implementações são versões de uma mesma ideia abstrata (o tipo abstrato de dados LISTA) definimos abaixo um arquivo de extensão .h, no qual todas as funcionalidades que devem estar disponíveis em uma estrutura de dados lista são indicadas.
// 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);
Implementação de listas de encadeamento simples
Dada interface definida acima, a implementação da estrutura de dados lista encadeada simples requer a implementação de todas as funcionalidades definidas em list.h. O primeiro passo é a criação de um arquivo .c para tal. Seguindo o padrão de nomenclatura utilizado pelas bibliotecas de C++ chamaremos as listas de encadeamento simples de forward_list e portanto criaremos um arquivo forward_list.c.
A partir de então, é preciso concretizar a implementação da estrutura list. Observe que em list.h essa estrutura é indicada de forma incompleta pela linha de código typedef struct TAD_LIST list;. Para que em nosso arquivo de implementação forward_list.c associemos uma estrutura útil ao nome list devemos então definir a struct TAD_LIST, o que é feito pelo trecho de código abaixo.
// *** forward_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ó
} node;
// Estrutura da lista, a qual nesta implementação armazena apenas
// um ponteiro para o primeiro elemento
struct TAD_LIST {
node* head;
};
// 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;
}
// 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) {
}
Utilização da estrutura list
Qual seria a principal motivação para essa separação entre interfaces (.h), implementação (.c) e utilização? Para tentar observarmos um dos benefícios da introdução da abstração definida pelo arquivo list.h, consideremos o arquivo main.c definido abaixo, o qual é o mesmo utilizado para implementação da APS1.
// **** main.c ****
#include "list.h"
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
int main() {
int capacidade, ncmds, indice, valor;
scanf("%d", &capacidade);
list* v = new_list();
scanf("%d", &ncmds);
char cmd[20];
while (ncmds-- > 0) {
scanf("%s", cmd);
if (strcmp(cmd, "push_back") == 0) {
scanf("%d", &valor);
list_push_back(v, valor);
} else if (strcmp(cmd, "push_front") == 0) {
scanf("%d", &valor);
list_push_front(v, valor);
} else if (strcmp(cmd, "insert") == 0) {
scanf("%d", &valor);
scanf("%d", &indice);
list_insert(v, valor, indice);
} else if (strcmp(cmd, "pop_back") == 0) {
list_pop_back(v);
} else if (strcmp(cmd, "pop_front") == 0) {
list_pop_front(v);
} else if (strcmp(cmd, "erase") == 0) {
scanf("%d", &indice);
list_erase(v, indice);
} else if (strcmp(cmd, "set") == 0) {
scanf("%d", &indice);
scanf("%d", &valor);
list_set(v, indice, valor);
}
list_print(v);
}
free_list(v);
}
Note que o código-fonte acima faz uso de várias funcionalidades definidas em list.h o qual é incluído neste arquivo main.c, porém não acessa nenhuma informação além da disponível em list.h. Como toda implementação do tipo abstrato lista deverá implementar todas as funcionalidade descritas em list.h este código (main.c) é independente da implementação da estrutura de dados lista a ser utilizada. Ou seja, ele poderá ser compilado tanto para utilização de vector.c quanto para utilização de forward_list.c sem que haja nenhuma necessidade de alteração no código-fonte main.c.
gcc main.c vector.c -o lista_com_vector
gcc main.c forward_list.c -o lista_encadeada_simples