Listas Lineares

Uma lista linear permite representar um conjunto de dados do mesmo tipo onde a ordem linear entre eles é preservada.

Alguns exemplos de utilização são:

• Uma lista de supermercado
  • Neste tipo de lista a ordenação é casual.
• A lista telefônica
  • Contém registros com nome da pessoa, endereço e número de telefone.
  • A ordenação é alfabética pelo último nome da pessoa.
• A lista de alunos da Universidade
  • Cada registro contém a matrícula, o nome, a data de nascimento, etc.

As principais operações que podem ser executadas em Listas Lineares são:

• Inserir um componente na lista.
• Remover um componente da lista.
• Alterar um componente da lista.
• Procurar um componente da lista

Lista Seqüencial

Definição: Uma lista é dita seqüencial quando seus componentes são armazenados em posições contíguas na memória.

A implementação mais comum de uma lista seqüencial usa um vetor (array), mas pode ser também usado um arquivo ou conjunto.

Para ver uma implementação de uma lista Sequencial, abra a unit LstSeq e para um programa que demonstra como usá-la, veja DLstSeq.

Lista Encadeada

Definição: Uma lista encadeada é uma coleção de registros em que cada registro tem um campo que indica a localização do registro seguinte na lista.

Assim, a ordenação é fornecida explicitamente por esse campo. Esquematicamente podemos representar uma lista ligada da seguinte forma:

Onde o registro que representa cada componente da lista possui um campo que aponta para o próximo registro numa certa seqüência de ordenação.

Cabeça: Primeiro registro (elemento) da lista.

Cauda: Último elemento da lista. Para indicar que não ha elementos após a cauda, atribui-se nil ao apontador para o próximo, já que não existe um próximo.

A principal vantagem das listas encadeadas sobre as listas seqüenciais é que as primeiras podem aumentar e reduzir de tamanho dinamicamente, podendo assim ser usadas em diversas situações sem comprometer o uso de memória.

A principal desvantagem das listas encadeadas é a necessidade de armazenamento adicional para guardar os apontadores.

Para ver uma implementação de uma lista Encadeada, abra a unit LstEnc e para um programa que demonstra como usá-la, veja DLstEnc.

Inserção na lista encadeada

Inicialmente a cabeça da lista aponta para nil, indicando que a mesma está vazia (1). Após a inserção do um Item 1 na lista, a cabeça aponta para ele, e o apontador para o próximo Item contido no Item 1 aponta para nil, já que após ele não há outros itens (2). Caso um outro elemento (Item 2) seja inserido, ele passa a ser a cabeça da lista e seu apontador para o próximo elemento da lista aponta para a antiga cabeça da lista (Item 1), como pode ser verificado em (3).

Remoção na lista encadeada

Quando o item a ser removido encontra-se na cabeça da lista, executamos os seguintes passos:

1) Navegamos na lista até encontrar o item a ser removido e guardamos o apontador para o próximo item (segundo) da lista.

2) Fazemos com que o apontador para a cabeça passe a apontar para o item seguinte à cabeça da lista, através do apontador obtido no passo 1.

3) Já que a cabeça já foi ajustada, executamos o dispose no item que localizava-se na cabeça da lista, liberando a memória referente ao Item removido da lista.

4) A lista passa a ter um elemento a menos e a variável dinâmica que continha o elemento apontado pela cabeça da lista foi desalocado da memória.

Quando o item a ser removido não se encontra na cabeça da lista, é necessário atualizar o apontador do item anterior. Sendo assim, usamos um apontador (PAtual) para procurar o Item a ser removido e outro (PAnterior) para guardar o Item anterior na lista encadeada. Desta forma, ao encontrar o Item (1), temos um apontador para o item anterior a ele (PAnterior) e para o próprio item (PAtual), como mostra (2). De posse destes apontadores, podemos ajustar o apontador para o próximo do item apontador por PAnterior para o endereço apontado pelo campo próximo do item apontado por PAtual. Em seguida, usamos o dispose para desalocar a variável dinâmica que guarda o item removido (3). Ao final, temos uma lista encadeada com um item a menos e com todos os apontadores ajustados.

Lista Ordenada

Definição: É uma lista que mantém os seus elementos sempre ordenados por algum critério.

Deve ser usada quando é necessário acessar os elementos da lista de forma ordenada. Quando a ordem não for importante, deve-se considerar o uso de outro tipo de lista pois as operações de inserção e remoção são mais caras (exigem mais processamento)  nas listas ordenadas.

A forma mais comum de se implementar uma lista ordenada é usando uma lista encadeada, onde o primeiro nó é menor que o segundo e assim por diante. Graficamente teríamos:

Para

Para ver uma implementação de uma lista Ordenada, abra a unit LstOrd e para um programa que demonstra como usá-la, veja DLstOrd.

O procedimento inicializar faz com que a cabeça da lista aponte para nil, indicando que não há elementos na lista.

O procedimento apagar e as funções vazia e tamanho são iguais à da lista encadeada, recebendo apenas um parâmetro com tipo diferente.

A função inserir coloca o item passado na posição correta da lista, ou seja, mantendo a ordem da mesma. A lista não deve conter uma chave igual à do item passado. Se a chave do item passado for menor do que a do primeiro da lista, será inserido no início e tornar-se-á a cabeça da lista (situação 1). Caso contrário, será inserido no meio (situação 3) ou no final (situação 2) da lista, dependendo do valor de sua chave e dos elementos contidos na lista (situação 2).

Situação 1: Inserindo um valor no início da lista:

Situação 2: Inserindo um valor no final da lista:

Situação 3: Inserindo um valor no meio da lista:

A função remover encontra um item na lista com a chave passada, libera a memória alocada pelo item e ajusta apontadores. No caso da remoção, encontramos 2 situações: remoção do elemento da cabeça ou que não está na cabeça.

Situação 1: Removendo um item da cabeça da lista:

Situação 2: Removendo um item que não está na cabeça da lista:

Lista Circular

Definição: É uma lista encadeada na qual o último elemento aponta para a cabeça da lista.

Graficamente teríamos:

As listas vistas até agora não possuem nó cabeça (apesar de poderem). Um nó cabeça é um nó criado na inicialização da lista e que permanece sendo a cabeça mesmo após inserções e remoções. O nó cabeça não guarda informações, a não ser o apontador para o primeiro nó da lista.

Uma lista circular com nó cabeça vazia teria a seguinte estrutura:

Já uma lista circular com 2 itens teria a seguinte estrutura:

Observe que em ambas as situações o nó cabeça não é usado para armazenar valores.

Para ver uma implementação de uma lista Circular com no cabeça, abra a unit LstCirC e para um programa que demonstra como usá-la, veja DLstCirC.

O procedimento Inicializar faz com que o nó cabeça seja criado e ajusta o tamanho para zero. Também faz com que o apontador para o próximo contido no nó cabeça aponte para ele mesmo.

A função Inserir cria um novo nó e o coloca após o nó cabeça, fazendo com que o seu próximo seja igual ao anteriormente apontado pelo nó cabeça.

A função Remover retira o primeiro nó com a chave informada. Se encontrar, ajusta os apontadores e apaga o nó.

Observe que mesmo quando o último elemento é removido, o nó cabeça continua, conforme mostrado abaixo:

O procedimento para Apagar libera todos os nós da lista, incluindo o nó cabeça. Não é correto chamar nenhuma outra operação (a não ser Inicializar) após chamar Apagar.

Lista Duplamente Encadeada

Definição: Uma lista duplamente encadeada (ou duplamente ligada) é uma lista com ligações múltiplas em que cada nó tem um campo que aponta para o nó anterior na lista e outro campo que aponta para o nó seguinte.

Graficamente temos:

As listas duplamente encadeadas são bastante úteis quando desejamos percorrer os nós em qualquer sentido, como em um editor de textos (cada linha é um nó) ou uma agenda (cada pessoa é um nó).

Uma lista duplamente encadeada possui um apontador para o início da lista (cabeça) e outro para o final (cauda).

Para ver uma implementação de uma lista Circular com no cabeça, abra a unit LstDEnc e para um programa que demonstra como usá-la, veja DLstDEnc.

A função Inserir coloca o novo nó na cabeça da lista. Se a lista estiver vazia, o novo nó também será a cauda.

A função Remover apaga um nó da lista e ajusta os apontadores (cabeça, cauda, anterior e proximo) quando necessário

a) Removendo no meio

b) Removendo na cabeça

c) Removendo na cauda

d) Removendo o último

As funções Tamanho e Vazia são semelhantes às da lista circular, diferindo apenas nos tipos de parâmetros (passam de Lista_Circular para Lista_Duplamente_Enc).