1

Debo eliminar cualquier nodo de una lista doblemente enlazada, recibiendo la posición. Realicé la función y elimina cualquier nodo, a excepción del primer nodo, no veo el error, si alguien puede explicarme el porqué no funciona y cual sería una posible solución, le agradezco mucho, adjunto el código.

void eliminarDato(Lista *lista,int posicion)
{
    Nodo *p, *anterior;
    int i;

    p = lista->inicio;
    anterior = NULL;

    for(i=1; i != posicion; i++)
    {
        anterior = p;
        p = p->siguiente; 
    }

    if( anterior == NULL)
    {

        lista->inicio = p->siguiente; 
        p->siguiente->anterior = NULL;       

        free(p);
    }

    anterior->siguiente = p->siguiente;
    p->anterior = anterior->anterior;
    free(p);


}
4
  • ¿Usas un puntero para guardar la referencia del último nodo? Para eliminar un nodo se requiere de 3 casos. Es decir, se necesita de varias condicionales para eliminar X nodo. Por ejemplo, una restricción cuando toque remover el primer y último nodo y un nodo intermedio. También noté que esté código no tiene sentido: p->anterior = anterior->anterior;, es decir, modificas el campo anterior del búfer al que apunte p pero luego lo liberas con free(p);, es decir, se pierde lo que asignaste.
    – MrDave1999
    Commented el 24 mar. 2020 a las 2:19
  • p->anterior = anterior->anterior si tiene sentido, anterior es un puntero de tipo Nodo, Nodo que tiene dos campos que *siguiente y *anterior, entonces hace que anterior->siguiente apunte al p->siguiente que es el siguiente dato del nodo a eliminar, y el anterior del nodo a eliminar va apuntar al anterior de ese mismo nodo. De hecho esa parte del código me funciona perfectamente, el error que hay es al eliminar el primer elemento de la lista.
    – Jhojan
    Commented el 24 mar. 2020 a las 3:13
  • Con respecto al error del primer elemento, solo agregale un else (caso contrario) a la condición anterior == NULL. De lo contrario estarías desreferenciando un puntero nulo y por esa razón ocurre un segment fault.
    – MrDave1999
    Commented el 24 mar. 2020 a las 15:24
  • No tiene sentido asignar algo a p->anterior, porque posteriormente liberas el nodo que apunta p con free(p). La forma correcta sería: p->sig->anterior = anterior;. Con esto modificamos el campo anterior del nodo siguiente para que apunte al nodo anterior del nodo que queramos eliminar.
    – MrDave1999
    Commented el 24 mar. 2020 a las 15:27

2 respuestas 2

4

Realicé la función y elimina cualquier nodo, a excepción del primer nodo, no veo el error

Cualquiera pensaría que el problema radica aquí:

if( anterior == NULL)
{

   lista->inicio = p->siguiente; 
   p->siguiente->anterior = NULL;       

   free(p);
}

Pero en realidad no, debido a que, el puntero inicio estaría apuntando al siguiente nodo (nodo B), en la cual, sería el primero y posteriormente, se modificaría el contenido del puntero anterior del siguiente nodo (nodo B), por lo tanto, apuntaría a NULL.

Este proceso lo podemos visualizar mejor con el siguiente diagrama: img1 En la imagen se puede ver que el nodo B sería el primer nodo y su enlace anterior apuntaría NULL.

Nota: En la imagen escribí p->inicio, en realidad es: lista->inicio.

El problema radica cuando esta instrucción se ejecute:

anterior->siguiente = p->siguiente;

Como estamos eliminando el primer nodo, el puntero anterior apuntaría a NULL, por lo tanto, es ilegal usar el contenido de dicho puntero, debido a que, estaríamos escribiendo en una dirección de memoria que no le pertenece al programa (ver segmentation fault). Si este error le llegara a suceder al programa, dejaría de funcionar al instante y de paso también estaríamos usando el contenido del puntero p cuando en realidad ya lo habíamos liberado anteriormente con free(p).

Para lograr evitar una falla de segmentación en este caso, podríamos agregar este bloque de código:

anterior->siguiente = p->siguiente;
p->anterior = anterior->anterior;
free(p);

En un else:

if( anterior == NULL)
{
    lista->inicio = p->siguiente; 
    p->siguiente->anterior = NULL;       
    free(p);
}
else
{
    anterior->siguiente = p->siguiente;
    p->anterior = anterior->anterior;
    free(p);
}

De este modo no ocurrirá una falla de segmentación y podremos eliminar el primer nodo sin ningún problema.

¿Qué pasaría si solo hubiera un único nodo? ¿Seguiría funcionando el código de arriba?

Pues lamentablemente no y esto se debe porque ocurriría una falla de segmentación en esta línea de código:

p->siguiente->anterior = NULL; 

¿Por qué? Como solo tenemos un nodo en la lista, ambos enlaces (anterior y siguiente) apuntarían a NULL, por lo tanto, el programa estaría escribiendo en una dirección que no tiene acceso y esto hará que el programa deje de funcionar.

En esta imagen se puede visualizar mejor: img2

Una solución es verificar cuando el puntero inicio contenga un NULL.

if( anterior == NULL)
{
    lista->inicio = p->siguiente; 
    if(lista->inicio != NULL)
      p->siguiente->anterior = NULL;       
    free(p);
}

Otro problema que vi en tu código fue esta línea de código:

p->anterior = anterior->anterior;
free(p);

Pensemos... Si queremos eliminar el nodo B, entonces el puntero p estaría apuntando hacia el nodo B y el puntero anterior apuntaría al nodo A (porque es el anterior), sin embargo, estarías asignando el contenido del campo anterior (del nodo que apunta anterior) en el campo anterior del nodo al que apunta p, pero ese contenido sería un NULL, por lo tanto, el campo anterior del nodo B (al que apunta p) apuntaría a NULL.

En esta imagen se visualizar mejor: img4

Ahora, la pregunta del millón: ¿Cual es propósito de modificar el campo anterior del nodo al que apunte p?

Pues ninguno. Porque no nos interesa modificar el contenido de ese nodo, ya que posteriormente lo liberamos con free(p) (esto libera el nodo al que apunte p).

En realidad lo que deberíamos modificar es el campo anterior del nodo C (al que apunte p->siguiente), porque si no lo llegaras hacer, el puntero anterior (del nodo C) seguiría apuntando a un nodo (el nodo B) que ya fue liberado y esto ocasionará una falla de segmentación (en nuestro ejemplo si) porque estamos accediendo a un registro de memoria que NO LE PERTENECE AL PROGRAMA.

Entonces la forma correcta de modificar dicho contenido es:

p->sig->anterior = anterior;

Como el puntero anterior apunta al nodo A, le debemos asignar esa dirección en el campo anterior del nodo C, para que de este modo el nodo C quede enlazado con el nodo A.

Entonces, el código quedaría así hasta mientras:

if( anterior == NULL)
{
    lista->inicio = p->siguiente; 
    if(lista->inicio != NULL)
      p->siguiente->anterior = NULL;       
    free(p);
}
else
{
    anterior->siguiente = p->siguiente;
    p->sig->anterior = anterior;
    free(p);
}

¿El código seguiría funcionando si quisiéramos eliminar el último nodo?

No. Esto se debe porque el puntero p quedaría apuntando al último nodo (nodo C) y al momento de ejecutarse esta instrucción:

p->sig->anterior = anterior;

Ocurriría una falla de segmentación, debido a que, el campo siguiente del último nodo apunta a NULL, por ende, es ilegal acceder a dicho contenido.

Una manera de solucionar este problema, es lograr que ese código solo se ejecute cuando no queramos eliminar el último nodo.

Por ejemplo:

if( anterior == NULL)
{
    lista->inicio = p->siguiente; 
    if(lista->inicio != NULL)
      p->siguiente->anterior = NULL;       
    free(p);
}
else
{
    anterior->siguiente = p->siguiente;
    if(p->sig != NULL)
      p->sig->anterior = anterior;
    else
      lista->ultimo = anterior;
    free(p);
}

Otra posible solución vendría ser:

void eliminarDato(Lista* lista, int posicion)
{
    Nodo *aux = lista->inicio;
    int i = 0;
    while(aux != NULL)
    {
        i++;
        if(i == posicion)
        {
            //Cuando aux apunte al primer nodo, la condición se cumple.
            if(lista->inicio == aux)
            {
                //Actualizamos el puntero inicio para que apunte al siguiente nodo.
                lista->inicio = aux->siguiente; 
                if(lista->inicio != NULL)
                    //Si la lista tiene más de un nodo, actualizamos el campo anterior del siguiente nodo (que vendría ser el primer nodo)
                    aux->siguiente->anterior = NULL;
            }
            else //De lo contrario, queremos eliminar un nodo intermedio o el último nodo
            {
                //Actualizamos el campo siguiente del anterior nodo para que apunte al nodo que le sigue al nodo que apunte aux
                aux->anterior->siguiente = aux->siguiente;
                if(aux->sig != NULL)
                    aux->sig->anterior = aux->anterior;
                else
                    //Actualizamos el puntero ultimo.
                    lista->ultimo = aux->anterior;
            }
            free(aux);
            break;
        }
        aux = aux->sig;
    }
    if(aux == NULL)
        printf("Error: La posicion que ingresaste es invalida!");
}

Conclusión:

El código de arriba sirve para:

  • Eliminar el primer nodo cuando solo haya un único nodo en la lista.

  • Eliminar el primer nodo cuando haya más de un nodo creado en la lista.

  • Eliminar un nodo intermedio.

  • Eliminar el último nodo (se debe actualizar el puntero que haga referencia al último nodo (lista->ultimo)).

2
  • Ahora tengo muchos conceptos más claros y aprendí otros conceptos nuevos, muchas gracias por tu explicación y por ayudarme con este código.
    – Jhojan
    Commented el 24 mar. 2020 a las 22:18
  • @Jhojan De nada amigo! No olvides de aceptar la respuesta que te sirvió.
    – MrDave1999
    Commented el 24 mar. 2020 a las 22:19
3

En una lista doblemente enlazada, al eliminar un nodo arbitrario debes enlazar el siguiente del anterior con el siguiente del eliminado y el anterior del siguiente con el anterior del eliminado. Esto funciona para cualquier nodo esté en el centro1:

Al inicio:

O al final:

no veo el error

El error es que avanzas hasta el nodo que quieres eliminar (p) pero en lugar de reenlazar los nodos siguientes y anterior a p, lo haces con el inicio de la lista:

lista->inicio = p->siguiente; // Mal.
p->siguiente->anterior = NULL;

Mi consejo es que modularices tu código creando funciones de búsqueda de nodo por posición y reenlazado:

Nodo *ir_a(Lista *lista,int posicion)
{
    Nodo *resultado = lista->inicio;

    for (int indice = 0; resultado && (indice != posicion); ++indice)
        resultado = resultado->siguiente;

    return resultado;
}

La función anterior devuelve el n-ésimo nodo desde el inicio de la lista o NULL si la posición facilitada está más allá de la cantidad de nodos disponibles.

void enlaza(Nodo *anterior, Nodo *siguiente)
{
    if (anterior)
        anterior->siguiente = siguiente;
    if (siguiente)
        siguiente->anterior = anterior;
}

La función anterior se explica sola.

Con estas funciones, tu función eliminarDato podría quedar así:

void eliminarDato(Lista *lista, int posicion)
{
    Nodo *p = ir_a(lista, posicion);

    if (p)
    {
        enlaza(p->anterior, p->siguiente);
        free(p);
    }
}

1nullptr es el literal de puntero nulo de , en se usa la macro NULL, debí poner NULL en el ejemplo pero me di cuenta tarde cuando ya tenía las imágenes creadas.

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.