Esta nota descreve uma implementação estilo Tipo Abstrato de Dado para listas encadeadas em C. As notas são baseadas nas aulas ministradas pelo Dr. Jarbas no semestre de 2017.2 na UFC - Sobral na disciplina de Estrutura de Dados.
Uma lista simplesmente encadeada só possuí um ponteiro para o próximo. Um nó só descreve quem é o próprio elemento e quem será o próximo. É a lista encadeada mais simples que tem. Outras versões de listas encadeadas podem ser implementadas como duplamente encadeada e circular. Em outro tópico será comentado sobre isso.
Definição formal de lista pode ser vista de uma maneira
recursiva. Existe um primeiro nó, que é a cabeça, então esse aponta
para o próximo: a cauda. O que consequentemente, o último elemento
apontará para o nil [fn:nil]
Head :: List
Tail :: List
Head -> data
prox -> Tail -> nil
Outra maneira de se ver uma lista é como uma árvore em que cada nó só possui um filho e um pai.
(1)
\
(2)
\
(3)
\
(4)
\
nil
=> [1,2,3,4]
Observe que nesse exemplo só existe o ponteiro de pai->filho. Quando
existir um ponteiro a mais que aponta filho->pai isto será uma lista
duplamente encadeada.
Em Lisp, por exemplo, listas são definidas através de pares chamado de cons.
CL-USER> (cons 1 (cons 2 (cons 3 (cons 4 nil)))) (1 2 3 4)
De uma maneira similar, embora não tão elegante como Lisp, seguindo
essas ideias podemos definir uma lista através de um struct na
linguagem C usando ponteiros.
[fn:nil] nil é uma keyword muito comum no mundo de Lisp pra
descrever uma lista vazia, em C poderíamos entender isso
grosseiramente como NULL.
Uma estrutura de lista simplesmente encadeada, armazenando um simples
int pode ser implementada da seguinte maneira:
struct node {
int data;
struct node *next;
};Ou seja, essa estrutura possuí apenas os campos data e o ponteiro
next para o próximo nó. O nó por si mesmo é uma lista (com apenas
um elemento).
Para definir nosso tipo abstrato de dados List, devemos implementar
um conjunto de operações definidos num cabeçalho. Essas operações
serão usadas pra manipular completamente a lista.
/* Tipo lista publico */
typedef struct node List;
/* Cria uma nova lista */
List* list_create(void);
/* Insere no começo da lista */
List* list_insert(List *l, int data);
/* Insere ordenadamente um elemento na lista */
List* list_insert_ord(List *l, int data);
/* Insere no fim da lista */
List* list_append(List *l, int data);
/* Busca na lista e retorna nó */
List* list_search(List *l, int data);
/* Imprime lista */
void list_print(List *l, int data);
/* Remove elemento específico da lista */
List* list_remove(List *l, int data);
/* Libera memória de toda lista */
void list_free(List *l);
/* Verifica se a lista está vazia */
int list_empty(List *l);Podemos implementar estes métodos acima de duas maneiras: iterative e
recursiva. A iterativa é geralmente a mais usada em C pois costumam
ser menos custosas em memória. Você precisa em geral de estruturas de
repetição como laços: while e for.
Implementações recursivas, definidas em termo de seus próprios métodos, geralmente são muito mais concisas e elegantes, mas C não garante Tail Call Optimization, então sua execução no geral pode ser mais custosa em memória por precisar de lembrar mais variáveis nas sucessivas criações de escopos nas chamadas recursivas.
É importante destacar que procedimentos iterativos podem ser definidos através de recursão por Tail Call (chamada por cauda) quando a linguagem ou compilador garante que no processo de compilação essa chamada de cauda irá descartar o escopo da pilha anterior (iterativo). Isto é conhecido como Tail Call Optimization ou Tail Call Eliminitation. Uma chamada de cauda é quando um função recursiva só chama a si mesmo quando não há mais nada pra lembrar do escopo atual.
Uma resposta que escrevi no StackOverflow descreve essa diferença no contexto de Scheme (LISP-1).
Observe que nem todas funções precisam ser definidas diferentemente,
apenas são necessárias aquelas que percorrem a lista de alguma
maneira. Por esse motivo, um arquivo separado chamado list-common.c
é definido os métodos comuns da lista. Isso evita reescrevê-los nos
arquivos individuais que contêm as implementações específicas dos
métodos recursivos e iterativos. O código fonte para esses métodos
você encontra em ./../src/list/single.
Os métodos em comum para essa TAD entre as implementações
recursiva e iterativa são as seguintes: list_create, list_empty e
list_insert.
List* list_create(void) {
return NULL;
}
int list_empty(List *l) {
return l == EMPTY_LIST;
}
List* list_insert(List *l, int data) {
List *head = (List *) malloc(sizeof(List));
check_alloc(head);
head->data = data;
head->next = list_create();
if (list_empty(l)) {
l = head;
} else {
head->next = l;
l = head;
}
return l;
}Como inserção na cabeça é \(Θ(1)\) então não é necessário percorrer a lista de nenhuma maneira.
As seguintes funções são criadas para auxiliar a definição dos métodos:
// util function
static inline List* new_node(int data) {
List* l = (List *) malloc(sizeof(List));
check_alloc(l);
l->data = data;
l->next = list_create();
return l;
}
// auxiliar print recursively list (without squared brackets)
void aux_list_print(List *l) {
if(!list_empty(l)) {
printf("%d", l->data);
if (!list_empty(l->next)) {
printf(", ");
}
aux_list_print(l->next);
}
}A função a seguir insere o elemento no fim.
List* list_append(List *l, int data) {
if (list_empty(l)) {
l = new_node(data);
} else {
l->next = list_append(l->next, data);
}
return l;
}Função definida recursivamente para inserir um elemento na lista de maneira ordenada.
List* list_insert_ord(List *l, int data) {
if(list_empty(l) || data <= l->data) {
l = list_insert(l, data);
} else {
l->next = list_insert_ord(l->next, data);
}
return l;
}Função de busca linear na lista.
List* list_search(List *l, int data) {
if(!list_empty(l)) {
if (l->data != data) {
l = list_search(l->next, data);
}
}
return l;
}Procedimento de impressão da lista, observe que está definida através
da função recursiva auxiliar aux_list_print.
void list_print(List *l) {
printf("[");
aux_list_print(l);
printf("]\n");
}Procedimento para remoção ordenada de um elemento específico da lista.
List* list_remove(List *l, int data) {
if (!list_empty(l)) {
if (l->data == data) {
List* next = l->next;
free(l);
l = next;
} else {
l->next = list_remove(l->next, data);
}
}
return l;
}Procedimento para liberar memória ocupada pelos nós da lista.
void list_free(List *l) {
if (!list_empty(l)) {
list_free(l->next);
free(l);
}
}A iterativa é a maneira mais verbosa de ser feita. Vou procastina um pouco até escrever. Mas enquanto isso olhe a recursiva.