Initializing doubly linked list in for-loop results in crash

Question

I am programming the classic Snake game in C using doubly linked lists and have written a function that creates a pointer, allocates the required space for the structure, then allocates memory for the next pointer in the list and so on. In the end the pointer to the first element is returned by the function and can be assigned to the head pointer in the main function.

When starting the game I want the snake to have a length of three so I had three malloc's in the function and used pointer, pointer->next, pointer->next->next and so forth and everything was working.

Since a lot of steps have to be repeated in this process I thought of putting all of this into a for-loop like this:

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

typedef struct snake snake;
struct snake {
    int x; /* x coordinate */
    int y; /* y coordinate */
    snake *previous;
    snake *next;
};

snake *initSnake(void) {
    snake *pointer, *tmp1, *tmp2 = NULL;
    /* three iterations, so the snake will have a length of three */
    for( int i = 0; i<3; i++, tmp1 = tmp1->next) {
        if(NULL == (tmp1 = (snake*)malloc(sizeof(snake)))) {
            return NULL;
        }
        /* coordinates */
        tmp1->x = 20;
        tmp1->y = 10 + i;
        /* first previous points to NULL */
        tmp1->previous = tmp2;
        /* temporarily store last pointer to be used for next previous pointer */
        tmp2 = tmp1;
        if(0 == i) {
            /* store first pointer so it can be returned */
            pointer = tmp1;
        }

    }
    /* the last next pointer has to point to NULL */
    tmp1 = NULL;
    /* now return the pointer to the first element in list */
    return pointer;
}


int main() {
    /* pointer to first element in list */
    snake *head = NULL;

    if(NULL == (head = initSnake() ) ) {
        fprintf(stderr, "Not enough memory!\n");
        return EXIT_FAILURE;
    }
    /* here everything works fine */
    printf("%d\n", head->y);
    printf("%d\n", head->previous);
    /* when trying to acces the content of the next element, the program crashes... */
    printf("%d\n", head->next->x);
    /* pause */
    getchar();
}

The problem is that when I try to access the second element of the list inside the main function, the game crashes. I suspect that something is wrong with tmp1 = tmp1->next in the for-loop and I don't really access the next pointers but I am not completely sure.

Can you help me out?

probably setting tmp1->next = NULL would help, or call calloc instead of malloc. And don't cast the return value of malloc. — bruceg, Jan 21 '16 at 22:50
@bruceg Why not cast the return of malloc? I rarely see it but my professor who is giving the C lecture insists in doing it. — user1662035, Jan 21 '16 at 23:04
http://stackoverflow.com/questions/605845/do-i-cast-the-result-of-malloc — bruceg, Jan 21 '16 at 23:06

Amit · Answer 1 · 2016-01-21T23:16:11.763

You have a lot of mistakes that suggest you don't really understand how memory, variables & pointers work. For example doing tmp1 = tmp1->next in the end of the for loop, immediately followed by tmp1 = (snake*)malloc(sizeof(snake)) overwrites tmp1 and makes the previous operation pointless. Similar operations exist in other places in your code.

To clean that up, try this:

snake *initSnake(void) {
    snake *head, **current, *prev;

    /* three iterations, so the snake will have a length of three */
    for(int i = 0, prev = NULL, current = &head; i<3; i++) {
        if(NULL == (*current = malloc(sizeof(snake)))) {
            return NULL; /* note that if this happens midway
                  through allocation, nothing gets freed */
        }
        /* coordinates */
        (*current)->x = 20;
        (*current)->y = 10 + i;
        /* next, previous pointers */
        (*current)->next = NULL;
        (*current)->previous = prev;
        prev = *current;
        current = &current->next;
    }

    /* now return the pointer to the first element in list */
    return head;
}

Christophe · Answer 2 · 2016-01-21T23:07:49.053

0

You have to set the last next pointer to NULL:

/* the last next pointer has to point to NULL */
tmp1->next = NULL;   // -> next !

because tmp1 is a local variable and setting it to NULL just before returning will have no effect.

Edit:

Ooops, also don't do tmp1 = tmp1->next in the for loop: as it is not set at the moment you attempt to perform this operation. You need to set next together with previous:

   /* first previous points to NULL */
    tmp1->previous = tmp2;
    if (tmp2) 
        tmp2->next = tmp1;

Online demo

edited Jan 21 '16 at 23:07

answered Jan 21 '16 at 22:54

Christophe

68,716
7
72
138

But tmp1 already is the last `->next pointer` in the list because I set `tmp1` to `tmp1->next` before leaving the loop. – user1662035 Jan 21 '16 at 22:58
At the moment you do the tmp1 = tmp1->next, you never did set the value of next. See my edit – Christophe Jan 21 '16 at 23:01

Initializing doubly linked list in for-loop results in crash

2 Answers2