Listas Encadeadas Simples

Afluentes: Estrutura de Dados

Vídeoaulas

• Análise visual de Lista Encadeada Simples
• Lista Encadeada Simples - Implementação em java: Só assista esse vídeo depois de tentar implementar por si.

Lista Encadeada

As listas ou listas encadeadas são a estrutura de dados mais simples concebível, excetuando-se naturalmente os arrays. Listas encadeadas nada mais são que uma sequência de células ligadas ou encadeadas umas as outras. As células de uma lista encadeada são compostas de dois elementos cada. O primeiro elemento é o dado efetivo a ser armazenado e o segundo é uma referência para o próximo elemento da lista. O código abaixo apresenta uma estrutura de dados referente à uma lista encadeada simples.

1public class No {       // Estrutura de dados da célula ou nó
2    String info;        // Conteúdo da célula
3    No proximo;         // Ponteiro para a próxima célula
4}

Quando lidamos com arrays, devemos saber de antemão ou em tempo de compilação qual o tamanho ou quantidade de bytes a ser alocados para o array. Existem muitas situações em programação onde a quantidade exata de memória a ser alocada não é conhecida na criação do programa devendo ser definida durante sua execução. Para estes casos pode-se alocar a memória necessária via alocação dinâmica de memória. No entanto ainda existem outros casos em que mais memória deve ser alocada para armazenar os dados do programa a medida que o programa vai sendo utilizado.

Este é um dos casos em que a utilização de listas ligadas é mais indicada do que a utilização de arrays estáticos ou dinâmicos. Outra vantagem das listas ligadas é que não existe nenhuma restrição indicando que as células que as compõem devem estar alocadas sequencialmente na memória, tal como ocorre com arrays ou memória alocada dinamicamente. Em verdade, cada célula pode existir em diferentes regiões a memória.

A lista ligada é composta, como visto, por nós (ou células) de informação. Cada nó contém um item de dado e um ponteiro para o próximo nó da lista. O final da lista é marcado pelo último nó da lista, apontando para o ponteiro nulo (NULL). Uma lista ligada vazia nada mais é que um ponteiro apontando para NULL.

Por fim, pode-se imaginar que o requisito imposto de um ponteiro apontando para o próximo elemento de cada elemento da lista seja um uso desnecessário de memória. No entanto vale lembrar que em geral as itens armazenados em uma lista encadeada são muito maiores que os tipos atômicos de dados, tornando assim a proporção entre memória de dados e ponteiros relativamente negligenciável.

Lista com e sem Cabeçalho

Listas ligadas podem ser organizadas de duas maneiras distintas.

Lista com cabeçalho: O conteúdo da primeira célula não importa, marca apenas o início da lista. A primeira célula está sempre no mesmo lugar na memória, mesmo que a lista fique vazia. Digamos que o cabeçalho aponta para o endereço da primeira célula. Então cabecalho.proximo == null se e somente se a lista está vazia. Para criar uma lista vazia, basta dizer:

No lista = new No();     
lista.proximo = null;

A estrutura da lista com cabeçalho ficaria da seguinte forma:

class Lista {
    No cabecalho = new No(); // Precisa ser inicializado
}

List sem cabeçalho: O conteúdo da primeira célula é tão relevante quanto o das demais. Nesse caso, a lista está vazia se o endereço de sua primeira célula é NULL. Para criar uma lista vazia basta fazer:

No lista = null;

A estrutura da lista sem cabeçalho ficaria da seguinte forma:

class Lista {
    No inicio;
}

Operações

Operações básicas de inserção, retirada e busca de informações em listas podem ser efetuadas no início da lista, no meio ou no fim.

Inserção no Início da Lista

Na inserção de elementos no início da lista deve-se observar se a mesma possui ou não um cabeçalho. Para o caso em que a lista sem cabeçalho, deve-se proceder da seguinte forma:

1. Criar a nova célula a ser inserida;
2. Apontar o ponteiro proximo do no a ser inserido para o primeiro nó da lista original (novo_no.proximo = inicio);
3. Apontar o inicio para o novo nó inserido (inicio = novo_no);

void inserirInicio (No no) {
    no.proximo = inicio;
    inicio = no;
}

Inserção no Meio da Lista

A inserção de um elemento no meio da lista ou em uma posição arbitrária independe do fato da lista possuir ou não cabeçalho. A idéia geral é encontrar a posição na qual a célula corrente deve ser inserida e então identificar as células anterior e posterior. Uma vez identificadas tais células basta que os ponteiros sejam ajustados.

Inserção no Fim da Lista

Tal inserção ocorre de maneira muito similar ao caso anterior. A única diferença é que no.proximo deve apontar para NULL.

Remoção de Elementos de uma Lista

Os elementos de uma lista podem ser removidos, a semelhança das regras de inserção, de três maneiras distintas:

• Remoção do primeiro elemento da lista;
• Remoção do último elemento da lista;
• Remoção de um elemento em uma posição arbitrária.

As funções de remoção são muito similares as de inserção e, portanto ficam como exercício.

Compare a remoção de um item de uma lista encadeada com a remoção de um item de um array!

Busca em Listas Encadeadas

Embora existam vantagens obvias relativas à utilização de listas encadeadas para gerência de memória alocada e inserção e remoção de itens, listas encadeadas não podem ser indexadas tal como um array. Existem todavia diversas formas de acessar os elementos de uma lista encadeada. As duas mais relevantes são:

• Busca por um elemento específico. Nesse caso, é informado o dado ou, no caso de um objeto, um atributo do objeto, e a lista é percorrida iterativavmente até que o dado seja encontrado;
• Recuperação do elemento na posição N a partir do início da lista. Nesse caso, a lista é percorrida a partir do início até que o elemento na posição N é encontrado.

No buscaElemento (int info) {               // Consideramos aqui que a informação é um inteiro
    No no = primeiro;                       // Aponta para o primeiro nó
    while (no != null && no.info != info) { // Enquanto no != nulo e a informação não encontrada
        no = no.proximo;                    // Vai para o próximo nó
    }
    return no;                              // Retorna o nó
}

A partir da ideia geral de listas encadeadas, estruturas de dados variantes podem ser concebidas. Em especial duas estruturas são de especial interesse. As listas duplamente encadeadas e as listas circulares.

Exercício

Implemente as seguintes operações de uma Lista Encadeada Simples em Java:

• Inserir elemento no início
• Inserir elemento no fim
• Inserir elemento no meio
• Retirar elemento do início
• Retirar elemento do fim
• Retirar elemento do meio

Implemente uma variante da operação de retirar elemento da lista, tanto no fim, como do meio, como do início, com base na informação que está alocada.

Por exemplo, imagine que você tenha uma lista de strings com nomes. Se você quiser tirar uma string que contenha o nome "saulo", você vai precisar varrer a lista até achar um nó com esse elemento e então o retira da lista e retorna como verdadeiro. Se não conseguiu encontrar um elemento que contenha a informação "saulo", não retira nada e retorna falso.