Vejamos como implementar listas simplesmente ligadas e duplamente ligadas em que a cabeça da lista é passada como parâmetro das funções de inserção e remoção, que também terão de retornar a cabeça da lista para o caso de esta ter mudado.
Lista simplesmente ligada
struct node { int value; struct node *next; }; typedef struct node *link; /* Insercao ordenada numa lista simplesmente ligada de inteiros */ link list_insert(link head, int value) { link node, prev, curr; prev = NULL; curr = head; while(curr != NULL && curr->value < value) { prev = curr; curr = curr->next; } node = (link) malloc(sizeof(struct node)); node->value = value; node->next = curr; if (prev != NULL) prev->next = node; else head = node; return head; } /* Remocao de um elemento da lista */ link list_delete(link head, int value) { link prev, curr; prev = NULL; curr = head; while (curr != NULL && curr->value < value) { prev = curr; curr = curr->next; } /* Encontramos o elemento? */ if (curr !=NULL && curr->value == value) { if (prev != NULL) prev->next = curr->next; else head = curr->next; free(curr); } return head; }
Lista duplamente ligada
struct node { int value; struct node *next, *prev; }; typedef struct node *link; /* Insercao ordenada numa lista simplesmente ligada de inteiros */ link list_insert(link head, int value) { link node, prev, curr; prev = NULL; curr = head; while(curr != NULL && curr->value < value) { prev = curr; curr = curr->next; } node = (link) malloc(sizeof(struct node)); node->value = value; node->next = curr; node->prev = prev; if (prev != NULL) prev->next = node; else head = node; if (curr != NULL) curr->prev = node; return head; } /* Remocao de um elemento da lista */ link list_delete(link head, int value) { link curr = head; while (curr != NULL && curr->value < value) curr = curr->next; /* Encontramos o elemento? */ if (curr !=NULL && curr->value == value) { if (curr->prev != NULL) curr->prev->next = curr->next; else head = curr->next; if (curr->next != NULL) curr->next->prev = curr->prev; free(curr); } return head; }
Exemplo: pilha dinâmica de inteiros
Neste exemplo não podemos perder a referência para o topo da pilha, ou seja, o ponteiro top
.
#include <stdio.h> #include <stdlib.h> /* * +----+ +----+ +----+ * top -->| 10 | | 8 | | 15 | * +----+ +----+ +----+ * | -+-->| -+-->| -+--> NULL * +--+-+ +----+ +----+ */ struct node{ int value; struct node*next; }; static struct node *top; void init() /* inicializa a pilha */ { top = NULL; } void push(int value) /* introduz novo elemento no topo */ { struct node *new; new = (struct node *) malloc(sizeof(struct item)); new->value = value; new->next = top; top = new; } int is_empty() /* pergunta se está vazia */ { return top == NULL; } int pop() /* apaga o topo */ { int value; struct node *old; if (!is_empty()) { value = top->value; old = top; top = top->next; free(old); return value; } else return -1; }
Problema: Como obter o número de elementos da Pilha?
Solução: É necessário percorrer toda a Pilha! Alternativa?
Exemplos lista de strings
Vamos utilizar uma lista simplesmente ligada mas em que Item
é char *
. Notar que neste exemplo não podemos perder a referência para o início da lista.
#include <stdio.h> #include <stdlib.h> #include <string.h> typedef struct node { char *text; struct node *next; }Node; typedef Node *link; link NEW(char* text) { link x = (link) malloc(sizeof(struct node)); x->text = (char*) malloc(sizeof(char)*(strlen(text)+1)); strcpy(x->text, text); x->next = NULL; return x; } link insertBegin(link head, char* text) { link x = NEW(text); x->next = head; return x; } link insertEnd(link head, char* text) { link x; if(head == NULL) return NEW(text); for(x = head; x->next != NULL; x = x->next) ; x->next = NEW(text); return head; } link lookup(link head, char* text) { link t; for(t = head; t != NULL; t = t->next) if(strcmp(t->text, text) == 0) return t; return NULL; } link delete(link head, char* text) { link t, prev; for(t = head, prev = NULL; t != NULL; prev = t, t = t->next) { if(strcmp(t->text, text) == 0) { if(t == head) head = t->next; else prev->next = t->next; free(t); } } return head; } /* Criar lista com argumentos da linha de comandos */ int main(int argc, char* argv[]) { int i; link head = NULL; /* inserir todos os elementos na lista*/ for(i = 1; i < argc; i++) head = insertEnd(head, argv[i]); print(head); /* imprime toda a lista*/ /* remover o um elemento (lido do stdin) */ scanf("%d", &i); head = delete(head, argv[i]); print(head); /* voltamos a imprimir toda a lista */ return 0; }
Em alternativa, podemos também implementar a inserção no início sem retornar:
void insertBegin(link *headptr, char *text) { link x = NEW(text); x->next = *headptr; *headptr = x; }