Walking through doubly linked list runs forever (despite apparent NULL terminator)

Question

My implementation of a C doubly linked list doesn't seem to work correctly. I fear it may be due to my cursory knowledge of pointers in C (coming from the blissful ignorance of interpreted languages). When I run this code, it seems print_list() runs forever, even though it should be terminated by the next field being NULL.

#include<stdio.h>

typedef struct Node {
    int data;
    struct Node* prev;
    struct Node* next;
} Node;

void print_list(Node* head) {
    Node* cursor = head;
    while(cursor != NULL) {
        printf("data: %d\n", cursor->data);
        cursor = cursor->next;
    }
}

void push_node(Node* head, int data) {  
    Node node = {data, NULL, NULL};
    Node* cursor = head;
    while(cursor->next != NULL) {       
        cursor = cursor->next;
    }
    cursor->next = &node;
    node.prev = cursor;
}

int main() {
    Node root = {0, NULL, NULL};
    push_node(&root, 1);
    push_node(&root, 2);
    print_list(&root);
    return 0;
}

What am I doing wrong?? Any help would be much appreciated.

`Node node = {data, NULL, NULL};` is in automatic storage. ("the stack") it goes out of scope once the function returns. — wildplasser, Apr 25 '18 at 22:32
In `push_node` you are creating the new Node on the stack, after `push_node` returns that memory is no longer readable without invoking undefined behaviour. — Paul, Apr 25 '18 at 22:33
read the other 100 questions about how to make a linked list in C. — Stargateur, Apr 25 '18 at 22:37
@Stargateur none of the questions I read on doubly linked lists explicitly mentioned that `malloc` or `calloc` were necessary for an implementation of a linked list - there's no need to be actively disencouraging. I wrote this code, it didn't work, I asked for help, I'm sorry for the inconvenience(!) — jonny, Apr 25 '18 at 22:49
@jonny well, to be fair, how many of those other questions did not malloc the new nodes? — Martin James, Apr 25 '18 at 23:29
`malloc` and `calloc` are not necessary. You can create the nodes the way you are doing it, you just have to do it higher up in the stack. EG. in `main`. — Paul, Apr 25 '18 at 23:30
@Paulpro true enough, though I would imagine it's difficult to think up an application scenario where that would be useful. Maybe to add sentinel nodes. — Martin James, Apr 25 '18 at 23:40
https://stackoverflow.com/a/39618642/905902 It is possible to use linked lists without malloc/free. It is even possible without pointers inside the nodes. — wildplasser, Apr 26 '18 at 00:13
@wildplasser the 'backing array' indices are base pointers and offsets. Still pointers:) — Martin James, Apr 26 '18 at 00:17
I cannot find the pointerless version now, maybe I'll add a link tomorrow. (comes in handy when the table is in shared memory or memmapped, or even on disk) There you go: http://stackoverflow.com/questions/8059591/lookups-on-known-set-of-integer-keys — wildplasser, Apr 26 '18 at 00:21

MFisherKDX · Accepted Answer · 2018-04-25T22:58:31.970

Your code does not work because Node node = { data, NULL, NULL }; creates a local variable node scoped to the function push_node. Once that function returns, you are using the address of a local out of scope which is undefined behavior. Instead, use malloc or calloc to allocate space for the Node.

Additionally, your push_node function does not correctly handle the case when the head pointer is NULL. There are several fixes for this. One way is to check for NULL, and if so, return the new pointer as the new head.

Also, you should write a function to delete your list when done.

Node *push_node(Node* head, int data) 
{  
    Node *node = malloc(sizeof(*node));
    node->data = data;
    node->prev = node->next = NULL;
    Node* cursor = head;
    if (cursor == NULL)
    {
        head = node;
    }
    else
    {
        while(cursor->next != NULL) {       
            cursor = cursor->next;
        }
        cursor->next = node;
        node->prev = cursor;
    }
    return head; 
}   

void free_list(Node *head) {
    if(head != NULL)
    {
        Node *next = head->next;
        free(head);
        head = next;
    }
}

int main()  {
    Node *root = NULL;
    root = push_node(root, 1);
    root = push_node(root, 2);
    print_list(root);
    free_list(root);
    return 0; 
}

score 1 · Answer 2 · answered Apr 25 '18 at 22:36

1

You cannot create the node in this fashion

Node node = { data, NULL, NULL };

It will create the node using stack memory, which will be deallocated once the function returns. You need to use malloc() to allocate heap memory.

void push_node(Node* head, int data) {
    Node *node = malloc(sizeof(*node));
    if (node == NULL) {
        printf("memory error\n");
        return;
    }
    node->data = data;
    node->next = node->prev = NULL;

    Node* cursor = head;
    while (cursor->next != NULL) {
        cursor = cursor->next;
    }
    cursor->next = node;     // note the changes here
    node->prev = cursor;     //
}

answered Apr 25 '18 at 22:36

Stephen Docy

4,738
7
18
31

1

what if `head` is NULL ? – Stargateur Apr 25 '18 at 22:55
A good point, but that is a second issue, unrelated to the question asked here, and not possible to hit given the OP's current code (he initializes the list in main with a single node). While I agree it is not good code, again, it is not related to the question he asked. So feel free to add your own answer if you wish to expand on what his code should ultimately be doing. – Stephen Docy Apr 25 '18 at 22:59

score 1 · Answer 3 · answered Apr 25 '18 at 22:48

In push_node you are creating the new Node on the stack, after push_node returns that memory is no longer readable without invoking undefined behaviour (infinite loops included). You could use malloc inside push_node but you probably shouldn't unless you're create a huge list. You would also need to keep track of the memory and free it properly later. If you're not making a massive list you can just create your nodes in main instead, with minimal changes to your code:

#include<stdio.h>

typedef struct Node {
    int data;
    struct Node* prev;
    struct Node* next;
} Node;

void print_list(Node* head) {
    Node* cursor = head;
    while(cursor != NULL) {
        printf("data: %d\n", cursor->data);
        cursor = cursor->next;
    }   
}

void push_node(Node* head, Node* new) {
    Node* cursor = head;
    while(cursor->next != NULL) {    
        cursor = cursor->next;
    }   
    cursor->next = new;                                                                                                                               
    new->prev = cursor;
}

int main() {
    Node root = {0,NULL,NULL};
    push_node(&root, &(Node){ 1, NULL, NULL }); 
    push_node(&root, &(Node){ 2, NULL, NULL }); 
    print_list(&root);
    return 0;
}

If your list is massive then you should use malloc anyway, but you wouldn't want to call it every time you create a new node, instead you might allocate a large enough amount of memory to hold a large list in one call to malloc, and then realloc it to be twice as large if your list grows to the point where you need more memory for it.

@MFisherKDX I think, it's the user stefoc, who downvote everything. This answer is the only one funny ;) but you should use for loop it's more idiomatic to iterate. — Stargateur, Apr 25 '18 at 22:51

bestestefan · Answer 4 · 2018-04-26T14:08:32.253

instead of creating local variables in push function you should use dynamically allocated memory, use malloc to allocate & free to free it before exiting from main, or even better you could use calloc, works same as malloc but fills allocated memory with zeros so you dont have to care about filling nulls, proof of concept:

void push_node(Node* head, int data){
    Node* node = calloc(sizeof(Node), 1);
    node->data = data;
    Node* cursor = head;
    while(cursor->next != NULL) {       
        cursor = cursor->next;
    }
    cursor->next = node;
    node->prev = cursor;
}

and in your main before return you should free allocated memory, function should be similar to your print function but instead of printing data you need to free given element until you get to end, proof of concept:

void free_list(Node* head){
   if(head){
       free_list(head->next);
       free(head);
   }
}

call free_list on your list before exiting

@joop yeah, my bad, haven't programmed in C for a while, it doesn't take overall buffer size but size of single elem and count of elems — bestestefan, Apr 26 '18 at 14:08

score 0 · Answer 5 · answered Apr 25 '18 at 23:52

The program runs forever because your call to push node places the Node declared on the stack onto the list twice. You are using two names for the same thing,

cursor->next = &node;

points to the stack node, and creates the conditions for the infinite loop. Which happens after the second call to this loop (in push_node).

while(cursor->next != NULL) {
    printf("ptr: %p -> %p\n",cursor,cursor->next); //add this
    cursor = cursor->next;
}

Add to your debug print the pointer value and you will see what is happening,

while(cursor != NULL) {
    printf("ptr: %p, data: %d\n",cursor,cursor->data); //change this
    cursor = cursor->next;
}

.

Walking through doubly linked list runs forever (despite apparent NULL terminator)

5 Answers5