Listas Encadeadas

As listas encadeadas estão entra as mais simples e comuns enstruturas de dados, e são utilizadas com armazenamento de dados para diversos tipos abstratos de dados como pilhas, filas e arrays associativos. Uma lista encadeada é uma lista linear de dados, chamados de nós ou elos (em inglês, nodes), que contém além do valor do dado armazenado, um apontador para o próximo elemento da lista.

A principal vantagem das listas encadeadas em relacão aos vetores, é que os elementos podem ser inseridos ou removidos da lista sem realocação ou reorganização de toda a estrutura, pois os dados não são armazenados contiguamente, além disso, o número de operações para inserção e remoção, é constante, se realizada durante a iteração sobre os elemnetos da lista.

No entanto, a estrutura não permite o acesso randômico aos dados, sendo necessário uma busca linear, cujo número de operações é diretamente proporcional ao tamanho da lista, para encontrar um elemento, ou para inserir ou remover um elemento em uma posição específica.

Lista com encadeamento simples

Uma lista encadeada, é formada por elos compostos pelo dado que gardam, e por um porteiro, que informa se existe, e qual é o próximo elo da estrutura.

A estrutura para o elo pode ser declarada da seguinte forma:

class Node<T> {
  public final T data;
  private Node<T> next;
  /**
   * Since the data is public and final, a
   * constructor to initialize it is required.
   */
  public Node(T data) {
    this.data = data;
    this.next = null;
  }
}

Como cada elo desta lista possui apenas uma conexão como o próximo elo da lista, a lista formada por estes elos é chamada de lista encadeada simples, e apesar deste modelo permitir todas as operações de uma lista encadeada, alguns algoritmos podem ficar menos eficientes, ou mais complexos, quando implementados de forma iterativa.

Com a estrutura de elos apresentada, a lista pode ser definida como o armazenamento do primeiro elo da lista, pois uma vez que este elo é conhecido, todos os outros elos podem ser acessados a partir do apontamento do elo anterior. Este elo inicial é, normalmente, referenciado como head.

class LinkedList<T> {
  private Node<T> head;
}

Assim como em qualquer outra estrutura de dados, uma lista encadeada permite a inclusão e exclusão de elementos. Tanto a inserção, quanto a remoção de um elemento de uma lista encadeada possui um número de operações constantes e envolve apenas os elementos vizinhos ao elemento afetado.

Na inclusão de um elemento na lista, a ordem das operações que envolvem os apontamentos é importante para que não se perca a referência aos outros elementos da lista.

function inserir(elo, dado):
    novo = Elo(dado)
    novo.next = elo.next;
    elo.next = novo;

A operação de inserção ao final da lista (append) é uma operação bastante comum, e, no caso de uma lista que armazena apenas o primeiro elemento, é uma operação muito custosa, uma vez que é necessário iterar sobre todos os elementos da lista, até que se encontre o elemento final. Uma variação comum na implementação de listas encadeadas, é armazenar o final da lista, para facilitar, por exemplo, esse tipo de opecação.

class LinkedList<T> {
  private Node<T> head;
  private Node<T> tail;
}

Note que a inclusão de novos elementos pode afetar os apontadores da lista (inserção no início ou no final da lista), e esta situação deve ser tratada quando necessário. Considerando uma lista que mantém tanto um apontador para o primeiro elemento, como para o último, os casos de inserção de que devem ser tratados são:

Casos de inserção

Para a exclusão de um elemento da lista, é necessário conhecer o elemento anterior ao elemento que deve ser excluido. Com isso, é possível apontar para o elemento posterior ao excluído, fazendo com que este elemento não mais faça parte da lista.

function remover(anterior):
    elo = anterior.next
    anterior.next = elo.next;

Assim como na inclusão, existem situações onde os apontadores de início e fim da lista podem ser alterados e devem ser corretamente tratados.

Considerando as operações vistas até o momento, a exclusão de um elemento, ou a inserção de um elemento antes da posição atual da lista, são operações que trazem um complicador a mais, uma vez que é necessário conhecer o elemento anterior ao elemento que se deseja excluir, ou antes do qual se deseja realizar uma inserção. Para que seja possível a realização destas operações é necessário que, sempre que se avança em um elemento na lista, o elemento anterior seja armazenado para ser utilizado nestas operações.

public T next() {
    last = current;
    current = current.getNext();
}

Mesmo com essa modificação, outras operações, como obter a lista na ordem reversa, são mais custosas ou complexas de serem realizadas em uma lista simplesmente encadeada. Uma alternativa para estes casos é utilizar uma lista duplamente encadeada.

Listas Duplamente Encadeadas

Em uma lista duplamente encadeada, os elos que formam a lista possuem dois apontadores, ao invés de apenas um, e mantém um apontador para o próximo elemento (como na lista simples), e um apontador para o elemento anterior. Esta alteração, embora aumente o consumo de memória para cada elo, e aumente o número de operações na inclusão e exclusão dos elementos, facilita a implementação de alguns algoritmos, como acessar os elementos da lista de forma reversa (do último para o primeiro), ou excluir um elemento da lista.

Lista Duplamente Encadeada

O elo, agora, precisa armazenar mais uma informação a respeito da estrutura da lista.

class Node<T> {
  public final T data;
  private Node<T> next;
  private Node<T> previous;
  /**
   * Since the data is public and final, a
   * constructor to initialize it is required.
   */
  public Node(T data) {
    this.data = data;
    this.next = null;
    this.previous = null;
  }
}

Em uma lista duplamente encadeada, embora não seja estritamente necessário, o usual é armazenar tanto o head como o tail da lista. Desta forma, o algoritmo de obtenção da lista invertida é implementado apenas com a iteração entre os elementos da lista, começando a partir do último elemento (tail), indo em direção ao primeiro elemento, utilizando o previous.

O algoritmo de remoção, agora, pode ser implementado sem que seja necessário obter, antes, o elemento anterior ao que se deseja remover, uma vez que cada elo da lista já possui esta informação.

function remove(elo):
    prev = elo.previous
    next = elo.next
    prev.next = next
    next.previous = prev

Note que agora, os dois elos que estão ligados ao que será removido devem ter seus apontadores alterados.

Remoção na Lista Duplamente Encadeada

Alterações semelhantes devem ser realizadas no processo de inserção, que numa lista duplamente encadeada pode ser implementado de duas formas diferentes, como inserção antes do elo, e inserção após o elo.

function insert_before(elo, dado):
    novo = Elo(dada)
    prev = elo.previous
    novo.next = elo
    novo.previous = prev
    prev.next = novo
    elo.previous = novo    

Novamente, a ordem das operações é importante, e deve ser sempre no sentido de, primeiro, configurar o novo elo, para que este conheça a lista já existente, e somente depois, fazer com que o elo entre na lista.

Os mesmos casos de inserção e exclusão da lista com encadeamento simples devem ser tratados na lista duplamente encadeada.