Transform a simply chained list code into a dual chained java list

Question

I would like you to help me because I am not yet very familiar with double-chained lists.

Answer 1

You will need to add a new field to the class Celula: anterior:

public class Celula {
    int valor;
    Celula proximo;
    
    // Adicione um campo que apontará para a célula anterior
    // Esse campo faz com que a célula seja duplamente encadeada
    Celula anterior;

    public Celula (int valor) {
        this.valor = valor;
    }
}

Next, you will need to change your code every time you create or modify a cell:

• in the method inserir:

public void inserir (int pos, int valor) {
    Celula nova = new Celula(valor);

    if (pos == 0) {
        // Como esse é o primeiro elemento dessa lista, essa célula não
        // possui nenhuma célula anterior, portanto o inicialize em `null`
        // Esse passo é opcional, visto que o campo `anterior` da classe
        // `Celula` já é inicializado em `null` por padrão
        nova.anterior = null;
        nova.proximo = primeiro;
        primeiro = nova;
    
    } else {
        Celula acessado = primeiro;
        for (int i = 0; i < pos - 1; i++) {
            acessado = acessado.proximo;
        }
 
        // Atual:
        // [acessado.anterior] <-> [acessado] <-> [acessado.proximo]
        // Objetivo:
        // [acessado.anterior] <-> [acessado] <-> [nova] <-> [acessado.proximo]

        nova.anterior = acessado;
        nova.proximo = acessado.proximo;
        if (acessado.proximo != null)
            acessado.proximo.anterior = nova;
 
        acessado.proximo = nova;
    }

    tamanho++;
}

• in the method remover:

public void remover (int pos) {
    if (pos == 0) {
        // Atual:
        // [primeiro] <-> [primeiro.proximo]
        // Objetivo:
        // [primeiro.proximo]

        primeiro = primeiro.proximo;
        if (primeiro.proximo != null)
            primeiro.proximo.anterior = null;
    }
    else {
        Celula acessado = primeiro;
        for (int i = 0; i < pos - 1; i++) {
            acessado = acessado.proximo;
        }

        // Atual:
        // [acessado] <-> [acessado.proximo] <-> [acessado.proximo.proximo]
        // Objetivo:
        // [acessado] <-> [acessado.proximo.proximo]

        if (acessado.proximo != null && acessado.proximo.proximo != null)
            acessado.proximo.proximo.anterior = acessado;
        acessado.proximo = acessado.proximo.proximo;
    }
    tamanho--;
}

---

Your main can be used as follows:

public static void main(String[] args) {
    ListaEncadeada lista = new ListaEncadeada();
    lista.inserir(0, 1);
    lista.inserir(1, 2);
    lista.inserir(2, 3);
    lista.inserir(3, 0);

    System.out.println("Populando lista:");
    for (int i = 0; i < lista.tamanhoList(); i++) {
        System.out.print(lista.acessar(i));
        System.out.print(", ");
    }
    System.out.println();

    lista.remover(0);
    System.out.println("Removendo elemento da posição 0:");
    for (int i = 0; i < lista.tamanhoList(); i++) {
        System.out.print(lista.acessar(i));
        System.out.print(", ");
    }
    System.out.println();

    lista.remover(2);
    System.out.println("Removendo elemento da posição 2:");
    for (int i = 0; i < lista.tamanhoList(); i++) {
        System.out.print(lista.acessar(i));
        System.out.print(", ");
    }
    System.out.println();
}