How to implement simply chained circular list based on a simply chained linear list?

Asked

Viewed 435 times

1

Hello folks how to implement simply chained circular list based on a simply chained linear list?

Method of inserting element in a given position:

@Override
public void adiciona(E elemento, int posicao) throws Exception {
    this.validarPosicao(posicao);
    this.verificarPosicaoOcupada(posicao);
    if (posicao == 0) {
        this.adicionaInicio(elemento);
    } else {
        if (posicao == this.tamanho) {
            this.adicionaFim(elemento);
        } else {
            Celula<E> anterior = this.recuperaCelulaRecursivo(this.primeira, posicao - 1, 0);
            Celula<E> nova = new Celula<>(elemento, anterior.getProxima());
            anterior.setProxima(nova);
            this.tamanho += 1;
        }
    }
}

Element insertion method at the end of the list:

@Override
public void adicionaFim(E elemento) {
    if (this.vazio()) {
        this.adicionaInicio(elemento);
    } else {
        Celula<E> nova = new Celula<>(elemento);
        this.ultima.setProxima(nova);
        this.ultima = nova;
        this.tamanho += 1;
    }
}

Element insertion method at the beginning of the list:

@Override
public void adicionaInicio(E elemento) {
    Celula<E> nova = new Celula<>(elemento, this.primeira);
    this.primeira = nova;
    if (this.vazio()) {
        this.ultima = this.primeira;
    }
    this.tamanho += 1;
}

Method of removing element at a given position:

@Override
public void remove(int posicao) throws Exception {
    this.validarPosicao(posicao);
    this.verificarSeEstaVazio();
    this.verificarPosicaoLivre(posicao);
    if (this.vazio()) {
        this.removeInicio();
    } else {
        if (posicao == this.tamanho - 1) {
            this.removeFim();
        } else {
            Celula<E> anterior = this.recuperaCelulaRecursivo(this.primeira, posicao - 1, 0);
            Celula<E> atual = anterior.getProxima();
            Celula<E> proxima = atual.getProxima();
            anterior.setProxima(proxima);
            proxima.setElemento(anterior.getProxima().getElemento());
            this.tamanho -= 1;
        }
    }
}

Item removal method at the end of the list:

@Override
public void removeFim() throws Exception {
    this.verificarSeEstaVazio();
    Celula<E> celulaAuxiliar = this.primeira;
    Celula<E> celulaAnterior = null;
    while (celulaAuxiliar.getProxima() != null) {
        celulaAnterior = celulaAuxiliar;
        celulaAuxiliar = celulaAuxiliar.getProxima();
    }
    Celula<E> celulaVazia = null;
    celulaAnterior.setProxima(celulaVazia);
    this.ultima = celulaAnterior;
    this.tamanho -= 1;
}

Item removal method at the beginning of the list:

@Override
public void removeInicio() throws Exception {
    this.verificarSeEstaVazio();
    this.primeira = this.primeira.getProxima();
    this.tamanho -= 1;
    if (this.vazio()) {
        this.ultima = null;
    }
}
  • Next to last is first.

  • Then @Gabriel in this case I would have to implement in the add methods Im(E element) and removeFim() the command this.ultima.setProxima(this.primeira)?

  • Yes, and when adding or removing the first one you need to update the next one. In short, whenever you touch the ends of the list you need to update the next one. It is also necessary to take care when iterating through the elements, not to enter in infinite loop.

No answers

Browser other questions tagged

You are not signed in. Login or sign up in order to post.