Este artigo demonstra como construir uma lista duplamente encadeada personalizada em Java, com funcionalidades essenciais como inserção, remoção e acesso por índice.

Classe No (Nó) A unidade fundamental da estrutura:

package com.cy.collection;

public class No {
    No anterior;     // Referência para o nó anterior
    Object valor;    // Dado armazenado
    No proximo;      // Referência para o próximo nó

    public No(Object valor) {
        this.valor = valor;
    }
}

Classe ListaEncadeada (Lista Duplamente Encadeada) Implementação principal com métodos de manipulação:

package com.cy.collection;

/**
 * Implementação personalizada de lista duplamente encadeada
 */
public class ListaEncadeada {
    private No primeiro;
    private No ultimo;
    private int contador;

    // Inserir no final
    public void inserir(Object valor) {
        No novoNo = new No(valor);
        if (primeiro == null) {
            primeiro = novoNo;
            ultimo = novoNo;
        } else {
            novoNo.anterior = ultimo;
            ultimo.proximo = novoNo;
            ultimo = novoNo;
        }
        contador++;
    }

    // Inserir em posição específica
    public void inserir(int posicao, Object valor) {
        verificarLimites(posicao);

        No noAtual = obterNo(posicao);
        No novoNo = new No(valor);

        if (noAtual != null) {
            No noAnterior = noAtual.anterior;
            if (noAnterior == null) {  // Inserção antes do primeiro
                novoNo.proximo = noAtual;
                noAtual.anterior = novoNo;
                primeiro = novoNo;
            } else {
                noAnterior.proximo = novoNo;
                novoNo.anterior = noAnterior;

                novoNo.proximo = noAtual;
                noAtual.anterior = novoNo;
            }
            contador++;
        }
    }

    // Obter valor por posição
    public Object obter(int posicao) {
        verificarLimites(posicao);

        No noAtual = obterNo(posicao);
        if (noAtual != null) {
            return noAtual.valor;
        }
        return null;
    }

    // Remover por posição
    public void remover(int posicao) {
        No noParaRemover = obterNo(posicao);

        if (noParaRemover != null) {
            No noAnterior = noParaRemover.anterior;
            No noProximo = noParaRemover.proximo;

            if (noAnterior == null) {  // Remoção do primeiro
                noProximo.anterior = null;
                primeiro = noProximo;
            } else if (noProximo == null) {  // Remoção do último
                noAnterior.proximo = null;
                ultimo = noAnterior;
            } else {  // Remoção do meio
                noAnterior.proximo = noProximo;
                noProximo.anterior = noAnterior;
            }
            contador--;
        }
    }

    // Localizar nó por posição
    private No obterNo(int posicao) {
        No noTemporario = null;
        if (primeiro != null) {
            if (posicao < (contador >> 1)) {  // Busca a partir do início
                noTemporario = primeiro;
                for (int i = 0; i < posicao; i++) {
                    noTemporario = noTemporario.proximo;
                }
            } else {  // Busca a partir do final
                noTemporario = ultimo;
                for (int i = contador - 1; i > posicao; i--) {
                    noTemporario = noTemporario.anterior;
                }
            }
        }
        return noTemporario;
    }

    // Tamanho atual
    public int tamanho() {
        return contador;
    }

    // Validação de limites
    private void verificarLimites(int posicao) {
        if (posicao < 0 || posicao >= contador) {
            throw new IndexOutOfBoundsException("Posição inválida");
        }
    }
}

Classe de Teste Exemplo de uso da implementação:

package com.cy.collection;

public class TesteLista {

    public static void main(String[] args) {
        ListaEncadeada lista = new ListaEncadeada();
        lista.inserir("Alpha");
        lista.inserir("Beta");
        lista.inserir("Gama");

        System.out.println("Tamanho: " + lista.tamanho()); // 3

        lista.inserir(2, "Delta");

        System.out.println("Elemento na posição 3: " + lista.obter(3)); // Gama
        System.out.println("Novo tamanho: " + lista.tamanho()); // 4
    }
}

Saída esperada:

Tamanho: 3
Elemento na posição 3: Gama
Novo tamanho: 4

A ipmlementação inclui otimização de desempenho no método obterNo, que escolhe a direção de percurso baseado na proximidade do índice em relação ao início ou ao final da lista.