how memory is assigned to the tail->next pointer while cloning the link list

Question

Below is the working function for copying the link list, by just passing the address of the original link list to this function it will create a copy and return the head.

I didn't understand how memory is assigned to tail->next pointer and how it is still pointing to the head_copy pointer. tail = tail->next; Now tail points to the new memory which is allocated to it using malloc, but still it points to the head_copy.

can anyone help me in understanding the flow of this code.

struct node
{
    int data;
    struct node* next; //Pointing back to the same structure.
};

struct node* copy_link_list(struct node** head)
{
    struct node* head_copy = NULL;
    struct node* tail = NULL;

    while (*head != NULL)
    {
        //printf("data in copy is %d and local_variable addr is %p\n",temp->data,&local);
        if (head_copy == NULL)
        {
            head_copy = malloc(sizeof(struct node));
            head_copy->data = (*head)->data;
            head_copy->next = NULL;
            tail = head_copy;
        }
        else
        {
            //printf("1. tail /// tail_of_data /// tail_of_next %p %d %p\n",&tail,tail->data,&(tail->next));
            printf("head_copy head_copy_of_data and head_copy_of_next %p %d %p\n",&head_copy,head_copy->data,(head_copy->next));
            tail->next = malloc(sizeof(struct node));
            printf("2. tail /// tail_of_data /// tail_of_next %p %d %p %p\n",&tail,tail->data,&(tail->next),tail->next);
            tail = tail->next;
            printf("3. tail /// tail_of_data /// tail_of_next %p %d %p %p\n",&tail,tail->data,&(tail->next),tail->next);
            tail->data = (*head)->data;
            tail->next = NULL;
        }
        *head = (*head)->next;
    }

    return head_copy; 
}

"Now tail points to the new memory which is allocated to it using malloc, but still it points to the head_copy." Why did you decide that tail points to head_copy?! Explain. — Vlad from Moscow
What are you doing? Copying a list! How are you doing it, you copy each element from the head until the end. The if (head_copy==NULL) sets tail to point to the a copy of the first node (assuming a non-empty list). After, at the beginning of the else block, tail always points to the last "node" which was copied, the a new node is assigned/created at tail->next, filled by copying the data. So now, tail->next is the last node which was copied, that is why tail = tail->next (because as stated above, tail should always point to the last node copied). — Emil Vatai
A (tail) recursive solution would only need 3 or 4 lines of code. — wildplasser

Vlad from Moscow Vlad from Moscow · Accepted Answer · 2019-12-29T14:30:57

In the first iteration of the while loop the pointer head_copy is equal to NULL. So this if statement is executed.

    if (head_copy == NULL)
    {
        head_copy = malloc(sizeof(struct node));
        head_copy->data = (*head)->data;
        head_copy->next = NULL;
        tail = head_copy;
    }

Now the memory for a node is allocated and its address is assigned to the pointer head_copy. Also the pointer tail points to the same node due to this assignment

tail = head_copy;

In the second iteration of the loop the pointer head_copy is already is not equal to NULL. So the else statement is executed.

    else
    {
        //printf("1. tail /// tail_of_data /// tail_of_next %p %d %p\n",&tail,tail->data,&(tail->next));
        printf("head_copy head_copy_of_data and head_copy_of_next %p %d %p\n",&head_copy,head_copy->data,(head_copy->next));
        tail->next = malloc(sizeof(struct node));
        printf("2. tail /// tail_of_data /// tail_of_next %p %d %p %p\n",&tail,tail->data,&(tail->next),tail->next);
        tail = tail->next;
        printf("3. tail /// tail_of_data /// tail_of_next %p %d %p %p\n",&tail,tail->data,&(tail->next),tail->next);
        tail->data = (*head)->data;
        tail->next = NULL;
    }

In the beginning of the else statement head_copy and tail are equal each other. Then tail is reassigned with the value of tail->next

tail = tail->next;

that is tail points now to the current last node of the created list. So starting from here the pointer tail is never equal to the value stored in the pointer head_copy. It points to currently created new node that is the last node of the created list.

Pay attention to that the function can look simpler. For example there is no need to pass the pointer head of the copied list by reference.

struct node* copy_link_list( const struct node *head )
{
    struct node *head_copy = NULL;
    struct node **tail = &head_copy;

    for ( ; head != NULL; head = head->next )
    {
        *tail = malloc( sizeof( struct node ) );

        ( *tail )->data = head->data;
        ( *tail )->next = NULL;

        tail = &( *tail )->next;
    }

    return head_copy;
}

how memory is assigned to the tail->next pointer while cloning the link list

1 Answers