====== Listas encadeadas ====== Em C, uma [[https://en.wikipedia.org/wiki/Linked_list|lista encadeada]] (lista ligada ou //linked list//) é composta por um conjunto de estruturas (''struct'') ligadas por ponteiros, de forma a construir uma sequência de valores de tamanho variável e que pode ser facilmente alterada. Listas encadeadas são estruturas dinâmicas muito utilizadas em programação, por sua flexibilidade e escalabilidade. Elas são frequentemente usadas na construção de TADs como pilhas, filas e listas, por exemplo. Algumas das principais operações efetuadas sobre uma lista encadeada são: * criar/destruir uma lista * inserir nodo * no início * no fim * no meio * remover nodo * do início * do fim * do meio * percorrer a lista (para imprimir, contar, procurar, etc) * do início ao fim * do fim ao início Esta página apresenta algumas das listas encadeadas mais usadas. Cada uma delas tem características próprias e formas distintas de implementar as operações acima definidas. ===== Lista simples ===== \\ {{ :prog1:lista-simples.png |}} \\ struct nodo_t { int valor ; // valor armazenado struct nodo_t *prox ; // próximo nodo } ; struct fila_t { struct nodo_t *primeiro ; // primeiro nodo struct nodo_t *ultimo ; // último nodo int num ; // numero de elementos } ; ===== Lista simples reversa ===== \\ {{ :prog1:lista-simples-reversa.png |}} \\ struct nodo_t { int valor ; // valor armazenado struct nodo_t *ant ; // nodo anterior } ; struct pilha_t { struct nodo_t *base ; // primeiro nodo struct nodo_t *topo ; // último nodo int num ; // numero de elementos } ; ===== Lista dupla ===== \\ {{ :prog1:lista-dupla.png |}} \\ struct nodo_t { int valor ; // valor armazenado struct nodo_t *ant ; // nodo anterior struct nodo_t *prox ; // próximo nodo } ; struct fila_t { struct nodo_t *primeiro ; // primeiro nodo struct nodo_t *ultimo ; // último nodo int num ; // numero de elementos } ; ===== Lista simples circular ===== \\ {{ :prog1:lista-simples-circular.png |}} \\ struct nodo_t { int valor ; // valor armazenado struct nodo_t *prox ; // próximo nodo } ; struct fila_t { struct nodo_t *primeiro ; // primeiro nodo struct nodo_t *ultimo ; // último nodo int num ; // numero de elementos } ; ===== Lista dupla circular ===== \\ {{ :prog1:lista-dupla-circular.png |}} \\ struct nodo_t { int valor ; // valor armazenado struct nodo_t *ant ; // nodo anterior struct nodo_t *prox ; // próximo nodo } ; struct fila_t { struct nodo_t *primeiro ; // primeiro nodo int num ; // numero de elementos } ; ===== Listas "sem cabeça" ===== A implementação de listas também pode ser feita usando somente estruturas do tipo ''nodo_t'', sem uma estrutura para a cabeça da lista. É uma implementação mais simples, porém menos flexível. \\ {{ :prog1:lista-simples-circular-headless.png |}} \\ struct nodo_t { int valor ; // valor armazenado struct nodo_t *ant ; // nodo anterior struct nodo_t *prox ; // próximo nodo } ; struct nodo_t *primeiro ; // início da lista ===== Exercícios ===== * [[https://www.ime.usp.br/~pf/algoritmos/aulas/lista.html|Esta página]] do prof. Paulo Feofiloff (IME/USP) tem uma ótima apresentação de listas encadeadas, com muitos exercícios.