C++ pointer arithmetic for linked lists

Question

I am just starting out self-learning C++, and as a toy problem, I am trying to do the following - given a linked list, I want to store all nodes that are even into a new list, and return this new list. For context, I come from a Python background.

I have the following program -


#include <iostream>
using namespace std;

struct node
{
    unsigned val;
    struct node *next;
};

node *even_nodes(node **root)
{
    node *new_list_head = NULL;
    node *new_list_runner = NULL;
    node *runner = *root;
    while (runner != NULL)
    {
        if (new_list_head != NULL){
            printf("OUTSIDE LOOP new_list_head.val = %d\n", new_list_head->val);
        }
        if (runner->val % 2 == 0)
        {
            cout << runner->val << endl;
            node new_node = {.val = runner->val, .next = NULL};
            if (new_list_head == NULL)
            {
                printf("new_list_head is NULL!\n");
                new_list_head = &new_node;
                new_list_runner = &new_node;
                printf("after allocation. new_list_head.val = %d\n", new_list_head->val);
            }
            else
            {
                printf("new_list_head is NOT NULL! new_list_head.val = %d\n", new_list_head->val);
                new_list_runner->next = &new_node;
                new_list_runner = new_list_runner->next;
                printf("after allocation. new_list_head.val = %d\n", new_list_head->val);
            }
        }
        runner = runner->next;
    }
    printf("new_list_head val = %d\n", new_list_head->val);
    return new_list_head;
};

void add_data(node **root, int new_data)
{
    node *new_node = (node *)malloc(sizeof(node *));
    new_node->val = new_data;
    new_node->next = (*root);
    (*root) = new_node;
}

void print_list(node *root)
{
    node *head = root;
    while (head != NULL)
    {
        printf("%d -> ", head->val);
        head = head->next;
    }
    printf("END\n");
};

int main()
{
    node *head = NULL;
    add_data(&head, 19);
    add_data(&head, 18);
    add_data(&head, 3);
    add_data(&head, 4);
    add_data(&head, 1);
    printf("Initial list:\n");
    print_list(head);
    node *new_list = even_nodes(&head);
    printf("New list of even numbers: \n");
    print_list(new_list);

    return 0;
}

The output is the following -

Initial list:
1 -> 4 -> 3 -> 18 -> 19 -> END
4
new_list_head is NULL!
after allocation. new_list_head.val = 4
OUTSIDE LOOP new_list_head.val = 4
OUTSIDE LOOP new_list_head.val = 4
18
new_list_head is NOT NULL! new_list_head.val = 18
after allocation. new_list_head.val = 18
OUTSIDE LOOP new_list_head.val = 18
new_list_head val = 18
New list of even numbers: 
[1]     segmentation fault

I do not understand why the new_list_head also changes with the new_list_runner? Why is my new_list_head pointing to the last element of the new list, and not the first?

Also, why is there a seg fault error? In the print_list method, why is the guard

while (head != NULL)

not working?

Any help will be appreciated!

With `node new_node = ...;` you define a *local* variable. A variable whose life-time will end when the current block ends, meaning the variable will cease to exist. The pointer you get with `&new_node` will become useless, and any attempt to dereference that pointer will lead to *undefined behavior*. Please refresh your text-books or tutorials about *scope* and *life-time*. — Some programmer dude, Nov 21 '22 at 11:39
Thanks for your reply! This helped me a lot. It seems moment I changed the following line - ```cpp node new_node = {.val = runner->val, .next = NULL}; ``` to ```cpp node *new_node = (node *)malloc(sizeof(node *)); new_node->val = runner->val; new_node->next = NULL; ``` it seems to work. However, I cannot find an explanation to why this works - is it because by doing `malloc`, we ensure the value the pointer is pointing towards is always valid? — mndl, Nov 21 '22 at 11:47
@AvishekMondal Do not use `malloc` in a C++ program, use `new` instead — john, Nov 21 '22 at 11:50
@AvishekMondal C++ is a difficult language with many traps for the unwary. It's clear that you are learning without proper reference material. I suggest you buy a [good book](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list/388282) — john, Nov 21 '22 at 11:51
Also your malloc is incorrect, it should be `sizeof(node)` not `sizeof(node*)`. As I say, you really need some proper learning material. — john, Nov 21 '22 at 11:53

john · Accepted Answer · 2022-11-21T11:45:38.510

You cannot do dynamic allocation by taking addresses of local variables. When the scope exits the local variable is destroyed and you are left with a pointer to an object which does not exist (known as a dangling pointer).

Your code has this problem here

node new_node = {.val = runner->val, .next = NULL}; // local variable
if (new_list_head == NULL)
{
    new_list_head = &new_node; // BAD
    new_list_runner = &new_node; // BAD
}
else
{
    new_list_runner->next = &new_node; // BAD
    new_list_runner = new_list_runner->next;
}

instead you should use new to allocate new nodes, Objects created with new do not get destroyed until you delete them.

node* new_node = new node{runner->val, NULL};
if (new_list_head == NULL)
{
    new_list_head = new_node;
    new_list_runner = new_node;
}
else
{
    new_list_runner->next = new_node;
    new_list_runner = new_list_runner->next;
}

C++ pointer arithmetic for linked lists

1 Answers1