Deleting a linked list element causes an infinite loop

Question

I am writing a program that takes a list of integers in input, and based on the integer it performs the following operations:

1. remove the absolute value if the value in input is negative

2. If the number is positive and even, then add in on the top of the list

3. If the number is positive and odd, add it on the tail of the list

4. If the number is equal to zero, end the program and print the list.

My problem is with the pop_el function, which causes an infinite loop on the list, so when i print the list the program goes into an infinite loop. This is my code:

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

typedef struct ll_node_S * ll_node_ptr;
struct ll_node_S
{
    int v;
    ll_node_ptr next;
};
typedef struct ll_node_S ll_node;

ll_node_ptr push_tail(ll_node_ptr head, int v)
{
    ll_node_ptr backup = head;
    ll_node_ptr current = head;

    while(current->next != NULL)
    {
        current = current->next;
    }
    current->next = (ll_node_ptr) malloc(sizeof(ll_node));
    current->v = v;
    return backup;
}

ll_node_ptr push_head(ll_node_ptr head, int v)
{
    ll_node_ptr new_head = (ll_node_ptr)malloc(sizeof(ll_node));
    new_head->v = v;
    new_head->next = head;
    return new_head;
}

ll_node_ptr pop_el(ll_node_ptr head, int el)
{
    ll_node_ptr backup = head;
    ll_node_ptr current = head;
    ll_node_ptr previous = NULL;
    int found = 0;

    while(current != NULL && !found)
    {
        if(current->v == el)
        {
            if(previous == NULL)
            {
                backup = current->next;
                free(current);
                current = backup;
                previous = current;
            }
            else
            {
                previous->next = current ->next;
                free(current);
                current = current->next;
            }

            found = 1;
        }
        else
        {
            previous = current;
            current = current->next;
        }
    }
    return backup;
}

void print(ll_node_ptr head)
{
    ll_node_ptr current = head;
    printf("%d\n", head->v);
    while(current->next != NULL)
    {
        current = current->next;
        printf("%d\n", current->v);
    }   
}

int isPair(int n)
{
    return ((n % 2) == 0);
}

int main(int argc, char** argv)
{
    int n = 1;
    ll_node_ptr list = NULL;
    while(n != 0)
    {
        scanf("%d", &n);

        if(n < 0)
        {
            list = pop_el(list, -n);
        }
        else
        {
            if(isPair(n))
            {
                list = push_head(list, n);
            }
            else
            {
                list = push_tail(list, n);
            }

        }


    }

    print(list);
    //should free the list
    return 0;
}

and this is the test case (passed in input) i am testing the code against:

4
5
2
-4
-5
-3
9
2
0

which should produce the following output:

2
2
9

any clues?

Answer 1

Several things,

In pop_el,

1.If previous is NULL then you just need to move your head ptr to the next node. So that it will become new head.

if(previous == NULL)
{
    backup = current->next;
    free(current);      
    //current = backup;   ---> Not needed.
    //previous = current; ---> Not needed.
    break;  //            ---> No need of setting found flag. You can remove it
}

2.If previous is not NULL then you need to just point the previous node next ptr to the current node's next node.

else
{
    previous->next = current ->next;
    free(current);          
    //current = current->next; ---> Not needed.
    break;  //            ---> No need of setting found flag. You can remove it
}

3.In push_tail you are allocating memory for current->next node and in the next line you are adding v to current node's v. That's wrong. Check following,

ll_node_ptr push_tail(ll_node_ptr head, int v)
{
    ll_node_ptr backup = head;
    ll_node_ptr current = head;
    ll_node_ptr new = NULL; // Created new pointer
    while(current->next != NULL)
    {
        current = current->next;
    }
    //current->next = (ll_node_ptr) malloc(sizeof(ll_node));
    new = (ll_node_ptr) malloc(sizeof(ll_node));
    //current->v = v;   ----> incorrect. new Value is actually replacing the old value.
    new->v = v;       // New value is added in the newly created node.
    new->next = NULL;
    current->next = new;
    return backup;
}

4.You can improve your print logic

void print(ll_node_ptr head)
{
    ll_node_ptr current = head;
    //printf("%d\n", head->v);
    while(current != NULL)
    {
        printf("%d\n", current->v);
        current = current->next;
    }   
}

Answer 2

Your immediate problem can be solved by fixing the push_tail() function, as pointed out by @Vitek. The original code not only stored the value in the wrong node, but also failed to set the next field of the newly allocated tail node to NULL. There is a further problem in this function: both the push_head() and the push_tail() functions need to create and return a node pointer when called with a NULL head pointer. The original push_head() function does this, but the push_tail() function does not. If the first number entered by the user is odd, the first node is added to the list via the push_tail() function, leading to undefined behavior (most likely a segmentation fault).

More importantly, you should work on simplifying your code. This will make it easier to write, and easier to debug. For example, your print() function can be reduced to three lines:

void print(ll_node_ptr current)
{
    while(current) {
        printf("%d\n", current->v);
        current = current->next;
    }
}

There are several things that can be done to improve the push_tail() function. Here is a new version:

ll_node_ptr push_tail(ll_node_ptr head, int v)
{
    ll_node_ptr current = head;
    ll_node_ptr prev = NULL;
    ll_node_ptr tail = malloc(sizeof(ll_node));

    if (tail == NULL) {
        fprintf(stderr, "Tail node allocation error\n");
        exit(EXIT_FAILURE);
    }

    tail->v = v;
    tail->next = NULL;

    while (current) {
        prev = current;
        current = current->next;
    }

    if (head) {
        prev->next = tail;
    } else {
        head = tail;
    }

    return head;
}

You do not need to cast the result of malloc(). Opinions differ on whether or not you should do so, but writing without the cast simplifies the code. Also, you should check to make sure that malloc() has successfully allocated the requested memory. This is especially important if you are instead using realloc(), because failing to do so can lead to memory leaks. After the new tail node is created here, the v and next fields are immediately set.

It usually seems simpler to iterate over a linked list by looking at the current node, rather than by looking at the current->next node. Use of the prev node pointer facilitates this. The new function iterates over the list until current == NULL, at which point prev points to the last node of the list. In the event that head was passed in as a NULL pointer (i.e., the list was empty, which can happen if the first number entered by the user is odd) the iteration loop is skipped, since current is initialized to head. The code after the loop sets the next field of the last node to point to the newly created tail node if a nonempty list was given to the function, otherwise head becomes the new tail node. Finally, head is returned to the calling function.

There is much simplification that could be applied to the pop_el() function, and a lot of superfluous code. This function should really be completely redesigned. Where you have:

previous->next = current ->next;
free(current);
current = current->next;

You have freed the memory referenced by current, then you try to dereference the pointer to this memory. After the call to free(), you no longer own this memory, and this is undefined behavior. Instead you want:

current = previous->next;

But this does not really matter, because found is next set to 1, the loop terminates, and the function returns backup, with no more uses of current. You should just remove the above assignment to current since it is not needed.

You should be able to use this information to improve the rest of the code in your program. There are other issues that you may want to look at. It is generally a bad practice to typedef pointers-- this only serves to obfuscate the code and increases the likelihood of programming errors. The specification that you provided does not make it clear what should happen if there are multiple nodes containing the same value, i.e., should one or all be removed? And, what if the first number entered by the user is 0?

Answer 3

First of all i would suggest using recursive functions when working with lists. Its much easier to debug and understand.

I think i found an issue with your push_tail function:

current->next = (ll_node_ptr) malloc(sizeof(ll_node));
current->v = v;

You allocate memory for current->next but assign the value to the current node. This should be

current->next = (ll_node_ptr) malloc(sizeof(ll_node));
current->next->v = v;
current->next->next = NULL;

Maybe this has something to do with your problem.