Delete node in a list with passing by reference in C

Question

Given the following code for deletion of an element in a doubly linked list:

struct list
{
    int info;
    struct list *prev;
    struct list *next;
};

struct list *insert(struct list *top,int k)
{
    struct list *tmp=NULL;
    if(!top)
    {
        tmp=(struct list *)malloc(sizeof(struct list));
        if(tmp)
        {
            tmp->info=k;
            tmp->next=NULL;
            tmp->prev=NULL;
            top=tmp;
        }
        else
            printf("error\n");
    }
    else 
    {
        top->next=insert(top->next,k);
        if(top->next)
            top->next->prev=top;
    }
    return top;
}



void delete(struct list **top,int k)
{
    struct list *tmp=NULL;
    if(*top)
    {
        if((*top)->info==k)
        {
            tmp=*top;
            if((*top)->next)
            {
                (*top)->next->prev=(*top)->prev;
            }

            if((*top)->prev)
            {
                (*top)->prev->next=(*top)->next;
            }

            *top=(*top)->next;

            free(tmp);
        }
        else
            delete(&((*top)->next),k);
    }
}
/* correct function
void delete(struct list **top,int k)
{
    struct list *tmp=NULL;
    if(*top)
    {
        if((*top)->info==k)
        {
            tmp=*top;
            if((*top)->next)
            {
                (*top)->next->prev=(*top)->prev;
            }

            if((*top)->prev)
            {
                (*top)->prev->next=(*top)->next;
            }
            else
                *top=(*top)->next;

            free(tmp);
        }
        else
            delete(&((*top)->next),k);
    }
}*/

int main()
{
    int i,k;
    struct list *top=NULL;
    for(i=1;i<11;i++)
       top=insert(top,i);

    printf("insert a key\n");
    scanf("%d",&k);
    delete(&top,k);
    // ...
}

The problem is that when the node k is deleted, the field next of the previous node of k does not point to successor of k but to successor of the successor of k.

For example:

Given the following sequence : 1 2 3 4 5 6 7 8 9 10.

Delete node 5;

Result : 1 2 3 4 7 8 9 10.

Why is this happening?

EDIT: I added in the comment the function delete in which the pointer advance only when *top is the head, and it works now. But the question is always open, that it, why changing the value of *top is modified also the value of (*top)->prev->next=(*top)->next changed before.

C is strictly pass by value. It does not support references. Do you mean C++? — too honest for this site
– too honest for this site, Commented May 3, 2016 at 17:55
Your main function still doesn't tell us anything we didn't already know. Can you include a minimal, verifiable, complete example? — callyalater
– callyalater, Commented May 3, 2016 at 18:20
I am working on that. Omitting that line causes issues when deleting a node on the end (like 1). — callyalater
– callyalater, Commented May 3, 2016 at 19:24

Community · Accepted Answer · 2021-01-18 12:35:56Z

Working code

I've not checked the chat room, but here's my working solution with the test code I used. It uses an iterative rather than recursive approach. I didn't change the insert() code (though I moved it after the delete() function), though I would remove the recursion were it to become 'my' code.

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

struct list
{
    int info;
    struct list *prev;
    struct list *next;
};

static
void delete(struct list **top, int k)
{
    struct list *node = *top;
    while (node)
    {
        if (node->info == k)
        {
            if (node->next)
                node->next->prev = node->prev;
            if (node->prev)
                node->prev->next = node->next;
            if (node == *top)
                *top = node->next;
            free(node);
            return;
        }
        node = node->next;
    }
}

static
struct list *insert(struct list *top, int k)
{
    struct list *tmp = NULL;
    if (!top)
    {
        tmp = (struct list *)malloc(sizeof(struct list));
        if (tmp)
        {
            tmp->info = k;
            tmp->next = NULL;
            tmp->prev = NULL;
            top = tmp;
        }
        else
            printf("error\n");
    }
    else
    {
        top->next = insert(top->next, k);
        if (top->next)
            top->next->prev = top;
    }
    return top;
}

static void dump_list_fwd(const char *tag, struct list *top)
{
    printf("List %p: %s\n", (void *)top, tag);
    while (top != 0)
    {
        printf("  Item %p: %2d (next %p, prev %p)\n", (void *)top,
               top->info, (void *)top->next, (void *)top->prev);
        top = top->next;
    }
}

static void free_list(struct list *top)
{
    while (top != 0)
    {
        struct list *next = top->next;
        free(top);
        top = next;
    }
}

int main(void)
{
    struct list *top = NULL;

    for (int i = 1; i < 11; i++)
        top = insert(top, i);
    dump_list_fwd("After insert", top);

    for (int i = 1; i < 11; i++)
    {
        int k = (i * 3 + 5) % 10 + 1;
        printf("Delete %d\n", k);
        delete(&top, k);
        dump_list_fwd("After delete", top);
    }

    free_list(top);
    return 0;
}

This compiles cleanly using the command line:

gcc -O3 -g -std=c11 -Wall -Wextra -Wmissing-prototypes -Wstrict-prototypes \
    -Wold-style-definition -Werror dellink.c -o dellink

The functions apart from main() are static to satisfy the -Wmissing-prototypes option. If the functions were going to be used outside this source file, they'd be declared in a header — but there is no other source file and there is no header, so I made them static.

The delete() function is rewritten as an iterative function. The key observation (fix) is that address stored in the pointer passed to the function should only change when that is the node that is deleted. This is harder to handle when the code is recursive. I also avoided using (*top) everywhere by copying it into a local variable; that simplifies the code a little.

The print and free functions are straight-forward bits of code. I almost always pass a tag string to printing functions so that the different locations where it is called can be simply identified. Were I doing the job thoroughly, I'd use uintptr_t and the PRIXPTR macro from <inttypes.h> to avoid 0x0 being printed for null pointers (I'd use "0x%.12" PRIXPTR to print the addresses, perfectly aware that pointers could need 16 bytes but not often running into that as a problem).

The main() code serially adds entries 1..10. The deleting loop deals with the entries in a different sequence (9, 2, 5, 8, 1, 4, 7, 10, 3, 6) so that the 'remove from start' and 'remove from end' are both executed as well as 'remove from middle'.

Sample run

List 0x7f9460c03180: After insert
  Item 0x7f9460c03180:  1 (next 0x7f9460c031a0, prev 0x0)
  Item 0x7f9460c031a0:  2 (next 0x7f9460c031c0, prev 0x7f9460c03180)
  Item 0x7f9460c031c0:  3 (next 0x7f9460c031e0, prev 0x7f9460c031a0)
  Item 0x7f9460c031e0:  4 (next 0x7f9460c03200, prev 0x7f9460c031c0)
  Item 0x7f9460c03200:  5 (next 0x7f9460c03220, prev 0x7f9460c031e0)
  Item 0x7f9460c03220:  6 (next 0x7f9460c03240, prev 0x7f9460c03200)
  Item 0x7f9460c03240:  7 (next 0x7f9460c03260, prev 0x7f9460c03220)
  Item 0x7f9460c03260:  8 (next 0x7f9460c03280, prev 0x7f9460c03240)
  Item 0x7f9460c03280:  9 (next 0x7f9460c032a0, prev 0x7f9460c03260)
  Item 0x7f9460c032a0: 10 (next 0x0, prev 0x7f9460c03280)
Delete 9
List 0x7f9460c03180: After delete
  Item 0x7f9460c03180:  1 (next 0x7f9460c031a0, prev 0x0)
  Item 0x7f9460c031a0:  2 (next 0x7f9460c031c0, prev 0x7f9460c03180)
  Item 0x7f9460c031c0:  3 (next 0x7f9460c031e0, prev 0x7f9460c031a0)
  Item 0x7f9460c031e0:  4 (next 0x7f9460c03200, prev 0x7f9460c031c0)
  Item 0x7f9460c03200:  5 (next 0x7f9460c03220, prev 0x7f9460c031e0)
  Item 0x7f9460c03220:  6 (next 0x7f9460c03240, prev 0x7f9460c03200)
  Item 0x7f9460c03240:  7 (next 0x7f9460c03260, prev 0x7f9460c03220)
  Item 0x7f9460c03260:  8 (next 0x7f9460c032a0, prev 0x7f9460c03240)
  Item 0x7f9460c032a0: 10 (next 0x0, prev 0x7f9460c03260)
Delete 2
List 0x7f9460c03180: After delete
  Item 0x7f9460c03180:  1 (next 0x7f9460c031c0, prev 0x0)
  Item 0x7f9460c031c0:  3 (next 0x7f9460c031e0, prev 0x7f9460c03180)
  Item 0x7f9460c031e0:  4 (next 0x7f9460c03200, prev 0x7f9460c031c0)
  Item 0x7f9460c03200:  5 (next 0x7f9460c03220, prev 0x7f9460c031e0)
  Item 0x7f9460c03220:  6 (next 0x7f9460c03240, prev 0x7f9460c03200)
  Item 0x7f9460c03240:  7 (next 0x7f9460c03260, prev 0x7f9460c03220)
  Item 0x7f9460c03260:  8 (next 0x7f9460c032a0, prev 0x7f9460c03240)
  Item 0x7f9460c032a0: 10 (next 0x0, prev 0x7f9460c03260)
Delete 5
List 0x7f9460c03180: After delete
  Item 0x7f9460c03180:  1 (next 0x7f9460c031c0, prev 0x0)
  Item 0x7f9460c031c0:  3 (next 0x7f9460c031e0, prev 0x7f9460c03180)
  Item 0x7f9460c031e0:  4 (next 0x7f9460c03220, prev 0x7f9460c031c0)
  Item 0x7f9460c03220:  6 (next 0x7f9460c03240, prev 0x7f9460c031e0)
  Item 0x7f9460c03240:  7 (next 0x7f9460c03260, prev 0x7f9460c03220)
  Item 0x7f9460c03260:  8 (next 0x7f9460c032a0, prev 0x7f9460c03240)
  Item 0x7f9460c032a0: 10 (next 0x0, prev 0x7f9460c03260)
Delete 8
List 0x7f9460c03180: After delete
  Item 0x7f9460c03180:  1 (next 0x7f9460c031c0, prev 0x0)
  Item 0x7f9460c031c0:  3 (next 0x7f9460c031e0, prev 0x7f9460c03180)
  Item 0x7f9460c031e0:  4 (next 0x7f9460c03220, prev 0x7f9460c031c0)
  Item 0x7f9460c03220:  6 (next 0x7f9460c03240, prev 0x7f9460c031e0)
  Item 0x7f9460c03240:  7 (next 0x7f9460c032a0, prev 0x7f9460c03220)
  Item 0x7f9460c032a0: 10 (next 0x0, prev 0x7f9460c03240)
Delete 1
List 0x7f9460c031c0: After delete
  Item 0x7f9460c031c0:  3 (next 0x7f9460c031e0, prev 0x0)
  Item 0x7f9460c031e0:  4 (next 0x7f9460c03220, prev 0x7f9460c031c0)
  Item 0x7f9460c03220:  6 (next 0x7f9460c03240, prev 0x7f9460c031e0)
  Item 0x7f9460c03240:  7 (next 0x7f9460c032a0, prev 0x7f9460c03220)
  Item 0x7f9460c032a0: 10 (next 0x0, prev 0x7f9460c03240)
Delete 4
List 0x7f9460c031c0: After delete
  Item 0x7f9460c031c0:  3 (next 0x7f9460c03220, prev 0x0)
  Item 0x7f9460c03220:  6 (next 0x7f9460c03240, prev 0x7f9460c031c0)
  Item 0x7f9460c03240:  7 (next 0x7f9460c032a0, prev 0x7f9460c03220)
  Item 0x7f9460c032a0: 10 (next 0x0, prev 0x7f9460c03240)
Delete 7
List 0x7f9460c031c0: After delete
  Item 0x7f9460c031c0:  3 (next 0x7f9460c03220, prev 0x0)
  Item 0x7f9460c03220:  6 (next 0x7f9460c032a0, prev 0x7f9460c031c0)
  Item 0x7f9460c032a0: 10 (next 0x0, prev 0x7f9460c03220)
Delete 10
List 0x7f9460c031c0: After delete
  Item 0x7f9460c031c0:  3 (next 0x7f9460c03220, prev 0x0)
  Item 0x7f9460c03220:  6 (next 0x0, prev 0x7f9460c031c0)
Delete 3
List 0x7f9460c03220: After delete
  Item 0x7f9460c03220:  6 (next 0x0, prev 0x0)
Delete 6
List 0x0: After delete

The code is given a clean bill of health by valgrind — no access errors and no unfreed memory.

Why does the original code skip a node?

Let's draw a picture — ASCII art to the fore!

Before deleting Node 2:

  +-----+
  | top |
  +-----+
     |
     v
+--------+     +--------+     +--------+     +--------+
|        |---->|        |---->|        |---->|        |
| Node 1 |     | Node 2 |     | Node 3 |     | Node 4 |
|        |<----|        |<----|        |<----|        |
+--------+     +--------+     +--------+     +--------+

Recursive call:

The top in the recursive call is actually stored in 'Node 1'->next!

                 +-----+
                 | top |
                 +-----+
                    |
                    v
+--------+     +--------+     +--------+     +--------+
|        |---->|        |---->|        |---->|        |
| Node 1 |     | Node 2 |     | Node 3 |     | Node 4 |
|        |<----|        |<----|        |<----|        |
+--------+     +--------+     +--------+     +--------+

Non-null `(*top)->next`:

Assigning: (*top)->next->prev=(*top)->prev;

                 +-----+
                 | top |
                 +-----+
                    |
                    v
+--------+     +--------+     +--------+     +--------+
|        |---->|        |---->|        |---->|        |
| Node 1 |     | Node 2 |     | Node 3 |     | Node 4 |
|        |<-------------------|        |<----|        |
+--------+     +--------+     +--------+     +--------+

Non-null `(*top)->prev`:

Assigning: (*top)->prev->next=(*top)->next;

Note that because top is actually a pointer to 'Node 1'->next, the assignment (*top)->prev->next = (*top)->next also changes (*top).

                                +-----+
                                | top |
                                +-----+
                                   |
                                   v
+--------+     +--------+     +--------+     +--------+
|        |------------------->|        |---->|        |
| Node 1 |     | Node 2 |     | Node 3 |     | Node 4 |
|        |<-------------------|        |<----|        |
+--------+     +--------+     +--------+     +--------+

Assign `*top` and free

Assigning (*top) = (*top)->next;

Because *top is also 'Node 1'->next, the assignment to *top also changes where 'Node 1'->next points to, skipping 'Node 3'. Note that a backwards traverse would still go through 'Node 3'.

                                               +-----+
                                               | top |
                                               +-----+
                                                  |
                                                  v
+--------+                    +--------+     +--------+
|        |---------------------------------->|        |
| Node 1 |                    | Node 3 |     | Node 4 |
|        |<-------------------|        |<----|        |
+--------+                    +--------+     +--------+

The reason for the damage is now explained.

Thanks @Jonathan Leffler. Do you have some link which explains in details the question of the pointer in the recursive call that you quote? Why when the code i recursive this situation is harder to handle?
I've added my explanation of what went wrong. The fix you show (adding a judiciously placed else in the delete() function) seems to work, and is remarkably neat and tidy. I've not done enough testing to be more sure than 'seems to work'; I've only run my test program on it, without varying the sequence of deletions.
@JonathanLeffler: thanks a lot for the detailed reply. The motivation of the wrong is subtle.

Collectives™ on Stack Overflow

Delete node in a list with passing by reference in C

1 Answer 1

Working code

Sample run

Why does the original code skip a node?

Before deleting Node 2:

Recursive call:

Non-null `(*top)->next`:

Non-null `(*top)->prev`:

Assign `*top` and free

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Working code

Sample run

Why does the original code skip a node?

Before deleting Node 2:

Recursive call:

Non-null (*top)->next:

Non-null (*top)->prev:

Assign *top and free

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related

Non-null `(*top)->next`:

Non-null `(*top)->prev`:

Assign `*top` and free