cstructuredoubly-linked-liststack-corruption

Doubly Linked List C - stack around variable 'list' was corrupted


I'm writing a code that splits a doubly linked list list into two lists listA and listB and prints them out. Code seems to get job done but in the end program crashes. Debugger throws Run-Time Check Failure #2 - Stack around the variable 'listA' was corrupted. and Run-Time Check Failure #2 - Stack around the variable 'list' was corrupted. I've read this might be caused by not enough memory allocated for my structure, but how much should I allocate?

Whole code:

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

typedef struct node {
    int val;
    struct node* prev;
    struct node* next;
}Node;
typedef struct list {
    Node* head;
    Node* tail;
}List;

void init(List* l) {
    l->head = NULL;
    l->tail = NULL;
}
Node* create(int val) {
    Node* ptr = (Node*)malloc(sizeof(Node));
    ptr->val = val;
    ptr->next = NULL;
    ptr->prev = NULL;

    return ptr;
}
void printList(const List* list) {

    Node *ptr = list->head;
    while (ptr != NULL) {
        printf("%i ", ptr->val);
        ptr = ptr->next;
    }
    puts("");
    free(ptr);
}
void pushLast(List* l, Node* node) {

    if (l->head == NULL) {
        l->head = node;
        l->tail = node;
    }
    else {
        node->prev = l->tail;
        l->tail->next = node;
        l->tail = node;
    }
}
void splitList(const List* list) {

    List* listA;
    List* listB;
    init(&listA);
    init(&listB);

    Node* ptr = list->head;
    int i = 0;
    while (ptr != NULL) {

        Node* node = create(ptr->val);
        if (i % 2 == 0)
            pushLast(&listA, node);
        else
            pushLast(&listB, node);
        i++;
        ptr = ptr->next;
    }

    puts("Input list");
    printList(list);
    puts("Odd nodes list:");
    printList(&listA);
    puts("Even nodes list:");
    printList(&listB);
}

int main(void) {

    List* list;
    init(&list);

    int i;
    for (i = 1; i <= 10; i++) {
        Node* node = create(i);
        pushLast(&list, node);
    }
    splitList(&list);
    return 0;
}

Output received:

Input list:
1 2 3 4 5 6 7 8 9 10
Odd nodes list:
1 3 5 7 9
Even nodes list:
2 4 6 8 10

Any help will be welcomed.


Solution

  • First, you are not allocating memory for pointers list, listA, and listB to point to.

    Second, you are defining list, listA, and listB as List *. Then passing &list, &listA, &listB - which are of type List ** - to your functions, whereas your functions are expecting List *.

    You need to make below changes in splitList(). (Shown only relevant part of code which has errors - or need addition of malloc):

    void splitList(const List* list) 
    {
        List *listA;
        List *listB;
    
        /* Allocate memory to which these pointers will point */
        if ((listA = malloc(sizeof(List))) == NULL) {
             /* Error handling code */
             exit(1);
        }
        if ((listB = malloc(sizeof(List))) == NULL) {
             /* Error handling code */
             exit(1);
        }
    
        /* ... */
        while (ptr != NULL)
        {
                Node* node = create(ptr->val);
                if (i % 2  ==  0)  
                        /* pushLast(&listA, node); */  /* ISSUE here */
                        pushLast(listA, node);
                else
                        /* pushLast(&listB, node); */  /* ISSUE here */
                        pushLast(listB, node);
                i++;
                ptr = ptr->next;
        }
    
        /* ... */
    
        puts("Odd nodes list:");
        /* printList(&listA); */  /* ISSUE here */
        printList(listA);
        free(ListA);  /* Free 1 */
        puts("Even nodes list:");
        /* printList(&listB); */  /* ISSUE here */
        printList(listB);
        free(ListB);  /* Free 2 */
    }
    

    Also, you need to make similar changes in main:

    int main(void)
    {
        List* list;
    
        /* Allocate memory */
        if((list = malloc(sizeof(List))) == NULL) {
            /* Error handling code */
            exit(1);
        }
    
        /* init(&list); */  /* ISSUE here */
        init(list);
    
        int i;
        for (i = 1; i <= 10; i++)
        {
                Node* node = create(i);
                /* pushLast(&list, node); */  /* ISSUE here */
                pushLast(list, node);
        }
        /* splitList(&list); */   /* ISSUE here*/
        splitList(list);
        free(list); /* free 3 */
    
        return 0;
    }
    

    Also note that you need to properly free all the memory allocated using malloc to avoid memory leak. It can be seen that you are NOT freeing all the nodes in. All the you have freed is just one node in printList() function.