2 Listas encadeadas 0 1

Prévia do material em texto

2. Listas encadeadas 0.2 Lista encadeada
2.1 Introdução à listas
O objetivo deste capítulo é fazer voce entender a listas encadeadas. A implementação de acordo com as necessidades e o desempenho depende de você.
Listas encadeadas podem ser usadas quando várias operações para inserção,remonçao e busca do elementos são necessárias.
Definição :
 Uma lista encadeada é simplesmente uma lista de objetos do mesmo tipo em que
cada elemento contém:
· Informações relacionadas ao funcionamento do aplicativo, por exemplo
nomes completos de pessoas com endereços e números de telefone para
um livro de endereços.
· O endereço do próximo item ou uma marca final, se não houver outro.
É esse link através do endereço do próximo elemento contido no elemento
precedente que cria a "cadeia" e permite encontrar cada elemento da lista.
O endereço do seguinte objeto pode ser:
· um endereço de memória recuperado com um ponteiro (encadeamento dinâmico).
· um índice de matriz recuperado com um número inteiro
· uma posição em um arquivo. Este é o número de série do objeto no arquivo
multiplicado pelo tamanho do byte do tipo de objeto. É recuperado com um
inteiro.
Se a lista encadeada é construída com ponteiros ou números inteiros, é sempre o
termo ponteiro usado: cada elemento "aponta" para o próximo elemento,
ou seja, tem os meios para acessá-lo e uma lista encadeada pode ser representada
assim:
 
Cada quadrado corresponde a um elo da cadeia. O pequeno quadrado preto no topo
left corresponde ao endereço na memória do elemento. A pequena volta às
direita corresponde ao ponteiro que "aponta" no seguinte, ou seja, que contém
o endereço do próximo item. No início, há o ponteiro da cabeça que contém
o endereço do primeiro elemento, ou seja, o endereço da cadeia.
 2.2 Lista simplesmente encadeada
 As listas simplesmente encadeadas são estruturas de dados semelhantes às tabelas, 
exceto que o acesso a um elemento não é feito por índice mas através de um ponteiro. .
A alocação da memória é feita durante a execução. Em uma lista, os elementos são contíguos no que se refere ao encadeamento.
Lista simplesmente encadeada pode ser representada assim:
 No entanto, em comparação com as tabelas, onde os elementos ficam contíguos na memória, os elementos de uma lista ficam espalhados na memória. A conexão entre os elementos se realiza por um ponteiro. Na verdade, na memória é aleatória, dependendo do espaço alocado.O ponteiro "seguinte" ao último elemento deve dirigir para o NULL (o fim da lista), e ara acessar um elemento, a lista é varrida começando do topo, o ponteiro "seguinte" permite o deslocamento para o elemento seguinte. O deslocamento se faz em um único sentido, do primeiro para o último elemento. Se você quiser deslocar nos dois sentidos (para frente/para trás) use as listas duplamente encadeadas.
A construção de um elemento da lista simplesmente encadeada:
 
 Para definir um elemento da lista, o tipo de estrutura será usado.
O item da lista conterá um determinado campo e um ponteiro a seguir.
O próximo ponteiro deve ser do mesmo tipo que o elemento, caso contrário, não poderá apontar para o elemento.
O ponteiro "próximo" permitirá acesso ao próximo elemento.
typedef struct ElemetoLista { char *dado; struct ElementoLista *proximo; }Elemento;
 Para ter controle da lista, é preferível salvar certos elementos:
o primeiro elemento, o último elemento, o número de elementos. Para conseguir isso, outra estrutura será usada (isso não é obrigatório, variáveis podem ser usadas).
Aqui está sua composição:
typedef struct ListaReferência { Elemento *inicio; Elemento *fim; int tamanho; }Lista;
O ponteiro inicial conterá o endereço do primeiro item da lista.
O ponteiro final conterá o endereço do último item da lista.
A variável size contém o número de elementos.
Qualquer que seja a posição na lista, os ponteiros inicial e final sempre apontam respectivamente para o primeiro e o último elemento. O campo tamanho conterá o número de elementos na lista, independentemente da operação executada na lista.
2.3 Lista duplamente encadeada
Definição :
 Listas duplamente encadeada são estruturas de dados semelhantes a listas simplesmente encadeads.
A alocação de memória é feita em tempo de execução.
Por outro lado, em comparação com as listas encadeadas simplesmente, a conexão entre os elementos é feita graças a dois ponteiros (um que aponta para o elemento anterior e outro que aponta para o seguinte).
 Lista simplesmente encadeada pode ser representada assim:
O ponteiro anterior do primeiro elemento deve apontar para NULL (o início da lista).
O próximo ponteiro para o último elemento deve apontar para NULL (o final da lista).
Para acessar um elemento, a lista pode ser percorrida nas duas direções:
· começando com a cabeça, o próximo ponteiro permite o movimento para o próximo elemento.
· começando com a cauda, o ponteiro anterior permite o movimento para o elemento anterior.
Em resumo, o movimento é feito em duas direções, do primeiro ao último elemento e / ou do último ao primeiro elemento.
A construção de um elemento da lista duplamente encadeada:
Para definir um elemento da lista, o tipo de estrutura será usado.
O item da lista conterá um determinado campo, um ponteiro anterior e um próximo ponteiro.
 Os ponteiros anteriores e seguintes devem ser do mesmo tipo que o elemento, caso contrário, não poderão apontar para um elemento na lista.
O ponteiro "precedente" permitirá acesso ao elemento anterior, enquanto o ponteiro a seguir permitirá acesso ao próximo elemento.
typedef struct dl_ElementoLista { char *dado; struct dl_ElementoLista *Anterior; struct dl_ElementoLista *Proximo; }dl_Elemento;
Para ter controle da lista, é preferível salvar certos elementos:
o primeiro elemento, o último elemento, o número de elementos.
Para conseguir isso, outra estrutura será usada (isso não é obrigatório, variáveis podem ser usadas).qui está sua composição:
 
typedef struct dl_Lista {dl_Elemento *inicio;
 dl_Elemento *fim;
 int tamanho;
}dl_Lista;
 O ponteiro inicial conterá o endereço do primeiro item da lista. O ponteiro final conterá o endereço do último item da lista. A variável size contém o número de elementos.
 Qualquer que seja a posição na lista, os ponteiros inicial e final sempre apontam respectivamente para o primeiro e o último elemento.
O campo tamanho conterá o número de elementos na lista, independentemente da operação executada na lista.
2.4 Lista circular
Definição : A lista circular é um tipo de lista simples ou duplamente encadeada, que possui uma característica adicional para mover-se na lista: "ela não tem fim".
Para tornar a lista infinita, o próximo ponteiro para o último elemento apontará para o 1º elemento da lista em vez do valor NULL, que vimos no caso de listas simples e duplamente encadeada.
Nas listas circulares, nunca chegaremos a uma posição da qual não poderemos mais nos mover.
Ao chegar ao último elemento, o movimento começará novamente no primeiro elemento. Em brevemente, é uma rotação.
 Lista circular pode ser representada assim: