Remove item from a simply linked list

Question

Remove item from a simply linked list

Navigation

#1 by (3 votes)

3

I'm having trouble removing an item by the value of a simply linked list. I'm doing this:

class No{
    public:
    int dado;
    No *next;
    No(int item, No *ptr= NULL){
        dado=item;
        next=ptr;
    }
};

class Lista{
    public:
        Lista(){
        first = last = NULL;
    };
    bool listaVazia();
    void inserirInicio(int item);
    void inserirFim(int item);
    void inserirPosicao(int item, int posicao);
    void buscaItem(int item);
    void removeInicio();
    void removeFim();
    void removeItem(int item);
    void imprimirLista();
    int tamanhoLista = 0;
    private:
    No *first, *last;
};

I can already check the function if it is inserting at the beginning and at the end, I need to understand how I'm going to remove it from a position in the middle so it does not get lost:

void Lista::inserirPosicao(int item,int posicao){
    if(posicaoValida(posicao)){
        if(posicao == 1){ // INSERI NA PRIMEIRA POSICAO
        inserirInicio(item);
    }else{
        if(last->next == NULL){ // INSERI NA ULTIMA POSICAO
            inserirFim(item);
            return;
        }else{ //   INSERIR NO MEIO


        }

    }
    }else{
       cout << endl << "       POSICAO INVALIDA" << endl;
    }
 }

c++ lista-encadeada

asked by anonymous 16.03.2015 / 16:57

1 answer

Git does not send commits to server. Error: Everything up-to-date What is a javascript Override?

score 3 · Accepted Answer

I made a basic code. I did not analyze all your code and did not do extensive testing. There may be situations that do not work. As I would have made several different decisions I preferred to try to keep the way you were doing and I did not even analyze if some things are not ideal, because it seems to me that you are learning and this is secondary.

void Lista::removeItem(int item){
    if(listaVazia()){
       cout << endl << "       LISTA VAZIA" << endl;
    //se tem um item ou já é o primeiro, desvie o quanto antes para removeInicio
    } else if(tamanhoLista == 1 || first->dado == item) {
        removeInicio();
        return;
    } else {
        No *ant = first; //já inicializei o nó anterior com o primeiro item
        No *atu = ant->next; //o nó atual com o próximo nó
        while(atu != NULL){
            if(atu->dado == item) {
                break; //se achou não precisa continuar procurando
            } else { //já que vai analisar outro item, então atualiza os nós
                ant = atu; //agora o anterior é o item atual
                atu = atu->next; //o atual passa ser o próximo item da lista
            }
        }
        if(atu != NULL) { //se chegou no fim sem achar nada, nada deve ser feito
            if (last == atu) { //se é o último que está removendo
                last = ant;
            }
           ant->next = atu->next; //atualiza a lista pegando o próximo do atual
           delete atu; //mata o atual
           tamanhoLista--;
        }
    }
}

See working on ideone .

removeFim can now be simplified since the object knows the last one. Then it is enough to call removeItem up by passing as an argument the dado of the last of the list.