Remove elements from the end of a list in C

Question

I’m having a problem where my list is removing all the elements and leaving only the last and last.

#include <stdio.h>
#include <stdlib.h>

typedef struct LISTA{

    int dado;
    struct LISTA *prox; 




}lista;


lista *insere(lista *p, int valor){

    lista *novo;
    novo=(lista*)malloc(sizeof(lista));
    novo->dado = valor;
    novo->prox = p;
    return novo;

}


void imprime(lista *p){
    lista *novo;
    for(p = novo; p!= NULL; p=p->prox){
        printf("%d",p->dado);

    }


}

/*lista *retira(lista *p, int valor){


    lista *aux = NULL;
    lista *novo = p;

    while(novo != NULL && novo->dado != valor){
    aux = novo;
    novo = novo->prox;  
    }
    if(novo == NULL){
        return p;
    }
    if(aux == NULL){
        novo = novo->prox;
    }else{
        aux->prox = novo->prox;
    }
    free(novo);
    return p;

}*/


lista *retiraFirst(lista *l){
    lista *tmp = l;
    tmp = l->prox;
    l->prox = tmp->prox;
    l->prox--;
    return tmp;


}


lista *retiraLast(lista *l){

    lista *ultimo = l,
    *penultimo = l;

    while(ultimo->prox != NULL){
        penultimo = ultimo;
        ultimo = ultimo->prox;

    }
    penultimo->prox = NULL;
    ultimo->prox= penultimo;
    return ultimo;



}






main(){

lista *l;
lista *primeiro, *ultimo;
    l = NULL;
    l = insere(l, 20);
    l = insere(l, 30);
    l = insere(l, 40);
    l = insere(l, 50);
    l = insere(l, 60);

    imprime(l);
    printf("----");
    //l =retira(l, 40);
    //l = retiraFirst(l);
    //imprime(l);
    printf("----");
    l = retiraLast(l);
    imprime(l);

}

Answer 1

First the printing function is wrong, the way it is doing is messing with the original list, ie while doing p=p->proximo you move up the list, then you miss the beginning of the list.

You must do it like this:

void imprime(lista *p){
    lista *novo=p;
    for(; novo!= NULL; novo=novo->prox){
        printf("%d  ",novo->dado);

    }
}

---

In function retiraLast the mistake is in l=retiraLast(l) should be ultimo = retiraLast(l); in main, because the function is well implemented (bearing in mind that not remove even in the list this element, giving free).

The problem with this implementation is that it will not be able to deliver free to the last element, because if you want to go through the list and give free to the last element will not be able to go back to the beginning and so should create in the struct a pointer to the beginning of the list.

As for example like this:

typedef struct _l_elemento
{
    /* string armazenada */
    char* str;
    /* apontadores para elementos vizinhos */
    struct _l_elemento *proximo;
    struct _l_elemento *anterior;
} l_elemento;

typedef struct
{
    l_elemento *inicio;
    l_elemento *fim;
    int tamanho;
} lista;

I suggest seeing some of my implementation of the Github

Answer 2

I suggest creating a struct to type "node", where you will store your data, and control the first and last within the list struct. And you should create only a list and pass it as a reference (via &) to your functions to ensure that you are editing the same list. See in the code below:

#include <stdio.h>
#include <stdlib.h>

typedef struct LISTA{
        struct no *pri;
        struct no *ult;
}lista;

struct no {
        int dado;
        struct no *prox;
};

void insere(lista *l, int valor);
void retira(lista *l, int valor);
void imprime(lista *l);

void imprime(lista *l){
        struct no *atual;
        atual = l->pri;
        while(atual != NULL){
                printf("%d\n", atual->dado);
                atual = atual->prox;
        }
}


void insere(lista *l, int valor){

        struct no *novo = malloc(sizeof(struct no));
        novo->dado = valor;
        novo->prox = NULL;

        /* primeiro item da lista
           pri == ult */
        if(l->pri == NULL) {
                l->pri = novo;
                l->ult = novo;
        }
        l->ult->prox = novo;
        l->ult = novo;
}

void retira(lista *l, int valor){
        struct no *atual, *achou = NULL;
        atual = l->pri;
        while(atual != NULL){
        /* se estiver no primeiro elemento */
                if(l->pri == atual &&
                        atual->prox->dado == valor){
                        achou = atual;
                        l->pri = achou->prox;
                        free(achou);
                        break;
                }else{                                                                                                                                                
                //olha uma posição na frente para não precisar voltar na lista                                                                                         
                   if(atual->prox != NULL && atual->prox->dado == valor){                                                                                                                  
                   // salva o proximo elemento                                                                                                                                         
                      achou = atual->prox;                                                                                                                                             
                   // atualiza o ponteiro do atual
                      atual->prox = achou->prox;
                    /* libera o elemento */                                                                                                                        
                      free(achou);                                                                                                                                                            
                      break;                                                                                                                                                           
                }

            }
                // avança o ponteiro
                atual = atual->prox;
        }

}


int main(){
        lista l;
        l.pri = NULL;
        l.ult = NULL;

        insere(&l, 10);
        insere(&l, 20);
        insere(&l, 30);
        insere(&l, 40);
        insere(&l, 50);
        insere(&l, 60);

        imprime(&l);
        printf("\n");

        retira(&l, 40);
        retira(&l, 50);
        imprime(&l);
}