remove kth last element from singly-linked list - Follow up

Question

This code is a revised version of implementation which asked for an improvement. Original question is asked here: remove kth last element from singly-linked list

credits to: Toby, Andreas, Arkadiusz

What has changed:

1. remove length from xllist struct
2. check if k is bigger than list length on the fly

Code:

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

typedef struct llnode
{
    int value;
    struct llnode *next;
} llnode;

typedef struct xllist
{
    llnode * head;
    llnode * tail;
} xllist;

bool create_node(xllist *list, int value)
{
    llnode *node = malloc(sizeof *node);
    if(!node)
    {
        return false;
    }

    node->value = value;
    node->next = NULL;
    if(!list->head)
    {
        list->head = node;
        list->tail = node;
    }
    list->tail->next = node;
    list->tail = node;
    return true;
}

bool del_element_from_last(xllist *llist, int k)
{
    //window with 2 pointers, length of k
    //prev is the prev node to the window
    llnode *prev;
    llnode *last;
    int len;  //list length

    if(llist->head)
    {
        last = llist->head;
        prev = llist->head;
        len = 1;
    }

    for(; last; last=last->next)
    {
        len++;
        if(len > k+1)
            prev = prev->next;
    }

    if(len < k) //len is smaller than k
    {
        return false;
    }

    if(len == k)  //means del 1st element from the list
    {
        llist->head = llist->head->next;
    }

    //remove first node of the window
    printf("deleted element:%d \n", prev->next->value);
    prev->next = prev->next->next;
    return true;
}

int main(void)
{
    xllist llist = {NULL, NULL};

    for(int i=0; i<100; i++)
    {
        if(!create_node(&llist, 100+i))
            printf("create fail\n");
    }

    del_element_from_last(&llist, 15);
}

Answer 1

• You are relying on the compiler zeroing local variables. For portability initialize them as needed.
• Use the address of either head or next fields (llnode**). Then deletion will become trivial.
• Free the deleted node.
• head node deletion does not printf. As printf was probably just test code, not so important.
• Two loops (instead of ifs) are more readable; first one to establish the back lag, and then following with a distance of k. Doing one thing at the time.
• Variable names could be more accurate. (I did not do that much better.)

So:

bool del_element_from_last(xllist *llist, int k)
{
    llnode *cur;
    int back = 0;
    for (cur = llist->head; cur && back < k; cur = cur->next)
    {
        ++back;
    }
    if (back < k) // List too short.
    {
        return false;
    }

    llnode **follow = &(llist->head);
    for (; cur; cur = cur->next)
    {
        follow = &(*follow)->next;
    }


    if (!*follow) // k <= 0.
    {
        return false;
    }
    printf("deleted element:%d \n", (*follow)->value);
    llnode *old = *follow;
    *follow = (*follow)->next;
    free(old);
    return true;
}

The second if guards the deletion naturally - no null pointer. The second if returning false could happen when k is 0. A fallacy is to combine conditions to make the code shorter. The code above is better traceable:

1. [At the second if] Why that null check? At the end of the list?
2. Aha, then k must be 0 (or less).

Answer 2

In the function del_element_from_last, when removing the first element of the list, you update llist->head. However, when removing the last element of the list, you do not update llist->tail.

If keeping track of the tail of the list is only intended for building the list, and is not intended to be updated by the function del_element_from_last, then you should not pass the entire struct xllist to the function del_element_from_last. Rather, you should change the function signature to the following, so that the function only has access to the head:

bool del_element_from_last( xlnode **pp_head, int k )

---

According to the task description, k is guaranteed to be smaller than the list. This means that the list is guaranteed to be not empty. In that case, the line

if(llist->head)

in the function del_element_from_last is redundant, because the condition will always be true.

On the other hand, defensive programming is good programming style. Therefore, it may still be appropriate to keep it.

However, if you decide to keep it, your program should handle both cases properly. If the condition is false, your program will cause undefined behavior, because you read the uninitialized value of last. Therefore, you should probably instead immediately return false when the condition is false.

An alternative to the if statement would be to use the assert macro, like this:

assert( llist->head );

That way, you don't have to provide code to handle both cases. Instead, a diagnostic error message will appear if the variable does not have the expected value (only on debug builds though, not on release builds).