Remove item from simply chained list

Question

Remove item from simply chained list

Asked 9 years, 9 months ago

Viewed 4,464 times

3

I’m having trouble removing an item by the value of a simply chained list. I’m doing so:

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 on the function if it is entering at the beginning and at the end, I need to understand how I will remove 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;
    }
 }

Do you already have a method to go through the list? Can it find an item by its position? You need it first. Eliminating the last one is easy and I think you’re doing it, just undo it and obviously decrease the size. The problem is that you need to change the previous element of the list that it no longer has a next one. And since she’s not doubly chained you don’t have that information. Then you have to go through the entire list until you get to what was the penultimate element and undo the pointer from next.

– Maniero

2015/03/16 at 16:14
Do not comment code, edit the question and put all the information you can. To delete just make it null.

– Maniero

2015/03/16 at 16:39
@bigown in this last function removeItem(item) I need to locate the item and remove it, for this I did a while running and an if checking if the item matches a value, if yes I should remove it and make the previous point to the next in

– Gabriel Rodrigues

2015/03/16 at 17:57
You changed the question. You need to access two items to remove: you have to figure out the item to be removed; you will get the next contained in it; will undo the whole node; will throw the next obtained in it and will change the next of the previous node with this next, so the previous one will point to the next one. It’s pretty simple. I just don’t answer because I’m on a tight schedule right now and I can’t test. If you put a code that I can test I see if you can change what you need, if possible do in http://ideone.com/

– Maniero

2015/03/16 at 18:18
the code is made in two .h, here is the code: https://drive.google.com/open?id=0ByiDi-nlXfgVWHB3VzFPUE40Zk0&authuser=0

– Gabriel Rodrigues

2015/03/16 at 18:37

1 answer

Browser other questions tagged c++ chain-list

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

by Maniero • **444,682** points · Answer 1 · 2015-03-16T20:33:43+00:00

I made a basic code. I didn’t analyze all your code and I didn’t do extensive tests. There may be situations that don’t work. As I would have made several different decisions I preferred to try to keep the way you have been 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--;
        }
    }
}

Behold working in the ideone. And in the repl it.. Also put on the Github for future reference.

The removeFim now can be well simplified since the object knows which is the last one. So in it just call the removeItem above passing as argument the dado of last of the list.