Listas

Listas

1. Introdução 2. Definições Básicas 3. Listas com Alocação Seqüencial 4. Pilhas com Alocação Seqüencial 5. Listas com Alocação Encadeada 6. Listas Simplesmente Encadeadas 7. Listas Circulares 8. Exercícios

Introdução Neste capítulo iremos discutir alguns aspectos de listas e como podemos implementar esta estrutura de dados em C. Não iremos abordar extensivamente este assunto, mas apenas discutir os algoritmos mais importantes e mostrar como eles podem ser implementados em C.

Listas

Listas - Definições Básicas
Uma lista linear de informações é uma estrutura de dados simples que armazena informações sobre dados que apresentam uma relação entre seus elementos.
As operações mais frequentes em listas são a busca, inserção e remoção de um determinado elemento. Outras operações que costumam ocorrer são a alteração de um elemento particular da lista, ordenação dos elementos da lista segundo uma determinada chave, procura do último ou do primeiro elemento da lista, etc.
Os elementos da lista podem ser armazenados em posições contíguas da memória e neste caso temos uma lista seqüencial. Podemos também armazenar os elementos em posições quaisquer da memória e neste caso temos de armazenar em cada elemento um indicador de onde está o próximo elemento da lista. Este último método é conhecido como alocação encadeada.

Listas com Alocação Seqüencial
A maneira mais simples de se manter uma lista na memória do computador é colocar seus nós em posições contíguas. Neste caso o elemento j+c estará c bytes (ou palavras, depende do sistema) à frente do elemento j da lista. A constante c corresponde ao número de bytes (ou palavras) necessário para armazenar cada elemento da lista. Cada elemento da lista é comumente chamado de nó. Um nó da lista pode conter vários tipos de informações que são armazenados em campos. Cada nó contém um (ou mais) elemento(s) que identificam unicamente o nó, a chave. Uma lista pode estar