Pular para o conteúdo
Início » Domine as Listas Encadeadas em Java e Aprimore sua Lógica de Programação

Domine as Listas Encadeadas em Java e Aprimore sua Lógica de Programação

Introdução

Quando falamos sobre estruturas de dados, Listas Encadeadas (Linked List) é uma das primeiras que devemos aprender. Isso porque ela serve como base para várias outras estruturas, como pilhas (stacks), filas (queues) e árvores binárias. Além disso, dominar as Listas Encadeadas ajudará você a desenvolver um raciocínio lógico mais sólido e a resolver problemas de forma mais eficiente.

Diferente dos arrays, onde os elementos são armazenados em posições contínuas na memória, uma Lista Encadeada é composta por nós que se conectam entre si por referências. Por esse motivo, sua estrutura permite maior flexibilidade, facilitando a inserção e remoção de elementos sem a necessidade de deslocar outros itens.

Outro motivo importante para aprender Listas Encadeadas é que elas aparecem com frequência em entrevistas de emprego. Em muitos testes técnicos, candidatos são desafiados a resolver problemas clássicos, como reverter uma Lista Encadeada ou detectar ciclos.

  • Neste artigo, você aprenderá:
    O que é uma Lista Encadeada e como ela funciona.
  • Como implementá-la em Java, do zero.
  • As operações essenciais: inserção, busca e remoção.
  • A análise de complexidade de cada operação.

Ao final, você terá um conhecimento sólido sobre quando e por que usar Listas Encadeadas. Bora começar!

Estrutura da Lista Encadeada: Como os Nós se Conectam

Diferente de um array, onde os elementos ocupam posições contínuas na memória, uma Lista Encadeada é composta por nós (nodes) que se conectam entre si por meio de referências.

Como os nós estão organizados?

Cada nó de uma Lista Encadeada contém dois elementos principais:

  1. O valor armazenado: Representa a informação contida no nó.
  2. A referência para o próximo nó:  Um ponteiro indicando a posição do próximo elemento da lista.

Esses nós se conectam formando uma cadeia de referências. O primeiro nó da lista é chamado de cabeça (head cell), enquanto o último nó aponta para null, indicando o final da estrutura.

Para visualizar melhor, veja a seguinte sequência armazenada em uma Lista Encadeada:

Lista Encadeada com nós conectados e setas apontando para o próximo elemento. O primeiro nó é identificado como 'Primeiro', e o último como 'Último', finalizando em null.
Estrutura de uma Lista Encadeada: cada nó armazena um valor e aponta para o próximo, com o último nó referenciando null.

Criando um Nó para a Lista Encadeada em Java

Agora que entendemos a estrutura de uma Lista Encadeada, é hora de começar a implementação. O primeiro passo é criar a classe responsável por representar cada nó.

Implementação do nó em Java

A seguir, implementamos a classe No, onde cada instância terá um valor e uma referência para o próximo nó:

class No {
    int valor;
    No proximo;

    No(int valor) {
        this.valor = valor;
        this.proximo = null;
    }
}
Explicação do código
  • int data → Armazena o valor do nó.
  • Node next → Guarda a referência para o próximo nó da lista.
  • Construtor Node(int data) → Define o valor do nó e inicializa next como null, pois ao ser criado, ele ainda não aponta para outro elemento.
Complexidade da criação de um nó

Criar um nó é uma operação O(1), pois envolve apenas alocação de memória e atribuição de valores. No entanto, a forma como manipulamos esses nós ao longo da implementação da Lista Encadeada influenciará a eficiência de outras operações, como inserção e remoção.

Implementando uma Lista Encadeada em Java

Agora que criamos a classe No, podemos estruturar a Lista Encadeada e implementar suas operações básicas.

Criando a classe ListaEncadeada

Para representar uma Lista Encadeada, precisamos de uma classe que contenha um nó inicial (primeiro) e métodos para realizar operações como inserção, busca e remoção.

Aqui está a implementação básica da classe ListaEncadeada:

public class LinkedList {
    private No primeiro;
    private No ultimo;
    private int tamanho;

    public void inserir(int valor) {
        No no = new No(valor);
        if (estaVazia()) {
            primeiro = no;
        } else {
            ultimo.proximo = no;
        }
        ultimo = no;
        tamanho++;
    }

    public boolean estaVazia() {
        return tamanho == 0;
    }

    public void imprimirLista() {
        No atual = primeiro;
        while (atual != null) {
            System.out.print(atual.valor + " -> ");
            atual = atual.proximo;
        }
    }
}
Explicação dos principais elementos
  • primeiro e ultimo → Referenciam, respectivamente, o primeiro e o último nó da lista. Isso permite inserções eficientes no final sem percorrer toda a estrutura.
  • tamanho → Mantém o número total de elementos na lista, tornando operações como estaVazia() mais rápidas.
  • inserir(int valor) → Adiciona um novo nó no final da lista:
    • Se a lista está vazia, o novo nó se torna o primeiro.
    • Caso contrário, ele é ligado ao último nó atual.
    • O ponteiro ultimo é atualizado, garantindo acesso rápido ao final da lista.

Adicionando e Removendo Elementos no Início e no Final da Lista Encadeada

Agora vamos expandir nossa Lista Encadeada para incluir operações de inserção e remoção no início e no final da lista.

Inserindo no Início da Lista

Inserir um nó no início da Lista Encadeada é uma operação rápida e eficiente, pois basta atualizar o ponteiro primeiro para apontar para o novo nó.

public void inserirNoInicio(int valor) {
    No no = new No(valor);
    if (estaVazia()) {
        primeiro = no;
        ultimo = no; 
    } else {
        no.proximo = primeiro;
        primeiro = no;
    }
    tamanho++;
}
Explicação do método:
  • Se a lista está vazia, o novo nó se torna tanto o primeiro quanto o último elemento.
  • Caso contrário, ele é ligado ao antigo primeiro nó, e primeiro é atualizado.
  • A complexidade é O(1), pois não há necessidade de percorrer a lista.

Removendo Elementos da Lista Encadeada

Agora que podemos inserir elementos, precisamos também de métodos para removê-los. Vamos implementar:

  1. removerPrimeiro() → Remove o primeiro elemento da lista.
  2. removerUltimo() → Remove o último elemento da lista.

A remoção no início é uma operação eficiente (O(1)), mas a remoção no final exige percorrer a lista para encontrar o penúltimo nó (O(n)).

Removendo o Primeiro Elemento

Para remover o primeiro elemento, basta atualizar primeiro para apontar para o segundo nó.

public void removerPrimeiro() {
    if (!estaVazia()) {
        primeiro = primeiro.proximo;
        size--;

        // Se a lista ficou vazia, resetamos o último nó também
        if (estaVazia()) {
            ultimo = null;
        }
    }
}
Explicação do método:
  • Se a lista não estiver vazia, movemos primeiro para primeiro.proximo.
  • Se a lista ficar vazia após a remoção, ultimo também precisa ser resetado para null.
Removendo o Último Elemento

Agora vamos implementar o método para remover o último elemento da Lista Encadeada. Como não temos um ponteiro direto para o penúltimo nó, precisamos percorrer a lista para encontrá-lo antes de atualizar ultimo.

public void removerNoFim() {
    if (!estaVazia()) {
        if (primeiro == ultimo) {
            removerPrimeiro(); // Reutiliza a lógica da remoção do primeiro nó
        } else {
            No atual = primeiro;
            while (atual.proximo != ultimo) {
                atual = atual.proximo;
            }

            ultimo = atual;
            ultimo.proximo = null;
            size--; 
        }
    }
}
Explicação do método
  • Apenas um elemento na lista
    • Se primeiro == ultimo, chamamos removerPrimeiro(), já que a lógica de remoção do primeiro nó cobre esse cenário.
  • Vários elementos na lista
    • Percorremos a lista até encontrar o penúltimo nó.
    • Atualizamos ultimo para que ele passe a ser atual.
    • Definimos ultimo.proximo = null para remover a referência ao último nó anterior.
    • Reduzimos size-- para manter a contagem correta de elementos.
Complexidade da Operação

O(n) → Pois precisamos percorrer a lista para encontrar o penúltimo nó.

Buscando um Elemento na Lista Encadeada

Diferente de um array, onde podemos acessar um elemento diretamente pelo índice, a Lista Encadeada não possui índices. Isso significa que, para encontrar um elemento, precisamos percorrer a lista nó a nó, verificando se algum deles contém o valor desejado.

A busca tem complexidade O(n), pois no pior caso precisamos percorrer toda a lista.

Implementação do método buscar
public No buscar(int valor) {
    No atual = primeiro;
    while (atual != null) {
        if (atual.valor == valor) {
            return atual; // Retorna o nó encontrado
        }
        atual = atual.proximo; // Atualiza o ponteiro para o próximo nó
    }
    return null; // Retorna null se o valor não for encontrado
}
Explicação do Código:
  • Inicia a busca a partir do primeiro nó (primeiro).
  • Percorre a lista nó a nó, comparando atual.valor com o valor buscado.
  • Se o valor for encontrado, retornamos a referência do nó correspondente.
  • Se o loop termina sem encontrar o valor, retornamos null.

Conforme mencionado, diferente de um array, onde podemos acessar array[i] em O(1), aqui precisamos percorrer toda a lista, o que pode levar O(n) no pior caso.

Removendo um Elemento Específico da Lista Encadeada

Agora que conseguimos buscar elementos, vamos implementar a remoção de um nó com um valor específico. Diferente da remoção do primeiro ou do último elemento, aqui precisamos:

  1. Percorrer a lista até encontrar o nó que contém o valor desejado.
  2. Atualizar a referência do nó anterior para ignorar o nó a ser removido.
  3. Tratar os casos especiais, como remover o primeiro ou o último nó.
Implementação do método remover
public void remover(int valor) {
    if (estaVazia()) {
        return; // Lista vazia, nada a remover
    }

    // remover o primeiro nó
    if (primeiro.valor == valor) {
        removerPrimeiro();
        return;
    }

    No atual = primeiro;
    No anterior = null;

    // Percorre a lista para encontrar o nó a ser removido
    while (atual != null && atual.valor != valor) {
        anterior = atual;
        atual = atual.proximo;
    }

    // Se o valor não foi encontrado, encerra
    if (atual == null) {
        return;
    }

    // Caso especial: remover o último nó
    if (atual == ultimo) {
        removerUltimo();
    } else {
        // Nó encontrado no meio da lista, ajustamos as referências
        anterior.proximo = atual.proximo;
        size--;
    }
}
Explicação do Método
  • Caso especial: Se a lista estiver vazia, não há nada para remover.
  • Se o valor estiver no primeiro nó, chamamos removerPrimeiro() e encerramos.
  • Percorremos a lista até encontrar o nó com o valor desejado.
  • Se o nó a ser removido for o último, chamamos removerUltimo().
  • Caso contrário, ajustamos a referência do nó anterior para ignorar o nó removido.
Complexidade da Operação

O(n) → No pior caso, precisamos percorrer toda a lista para encontrar o nó a ser removido.

Conclusão

Neste artigo, exploramos Listas Encadeadas em Java, cobrindo desde a estrutura básica até a implementação de operações essenciais, como inserção, remoção, busca e verificação de posição.

Aprendemos que, diferente dos arrays, uma Lista Encadeada não possui índices diretos, exigindo um percurso nó a nó para acessar os elementos. Embora essa estrutura tenha vantagens, como inserções eficientes no início e no fim, operações como busca e remoção podem ter complexidade O(n) no pior caso.

Agora que você domina o básico, chegou o momento de avançar para um desafio real!?

📌 Em detecção de ciclos, precisamos verificar se há um loop na lista. Esse é um problema clássico em algoritmos e aparece com frequência em entrevistas de emprego. Já escrevi um artigo explicando isso passo a passo.

👉 Clique aqui para conferir: Detecção de Ciclos em Listas Encadeadas

Se gostou do artigo ou tem dúvidas, deixe um comentário! 🚀

Quer praticar esse tipo de problema do jeito que cai em entrevistas?
Estou construindo o DevPrep, uma plataforma em português focada em raciocínio e padrões de algoritmos.

👉 Acesso por beta fechado: https://devprep.dev/

Referências

Marcações: