Listas em C

Fazendo um percurso conforme o nível de entendimento:
 

LISTAS LINEARES

Lista Linear é a estrutura que permite representar um conjunto de dados afins de forma a preservar a relação de ordem linear de seus elementos. .

        Define-se lista linear como sendo o conjunto de  n ³ 0 nós  -  X1, X2, ....., Xn, organizados estruturalmente de forma a refletir as posições relativas dos mesmos:   SE n > 0,  então   X1   é o primeiro nó;  para  1 <  k  < n, o nó Xk é precedido pelo nó  Xk-1 e seguido do  Xk+1; E Xn é o último nó.  Quando  n = 0 diz-se que a lista é vazia.

     As operações mais frenquentes em uma lista linear são:

• A busca;
• Inserção e remoção de um determinado elemento;

Outras operações que costumam ocorrer são:

• Alteração de um elemento particular da lista;
• ordenação dos elementos da lista seguindo 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 sequencial. 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 - IMPLEMENTAÇÃO

ALOCAÇÃO SEQUENCIAL OU CONTÍGUA

A maneira mais simples de acomodar uma lista em um computador é através da utilização de um vetor. A representação por vetor explora a sequência da memória de tal forma que os nós de uma lista sejam armazenados em endereços contíguos, ou igualmente distanciados em do outro. 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 ordenada ou não de acordo com a chave.

                           X1  X2  X3   X4  X5  X6                          Xn-1  Xn