So I am trying to create a duplicate of a linked list containing a void pointer to data The definitions are:

typedef struct SinglyLinkedListNode {
    void *data;
    struct SinglyLinkedListNode *next;
}SinglyLinkedListNode;

typedef struct SinglyLinkedList {
    int size;
    struct SinglyLinkedListNode *front;
}SinglyLinkedList;

My function to clone the linked list has been inspired from How to clone a linked list with a head/tail implementation? The only difference being, my list doesn't have a tail implementation.

Here is my implementation

SinglyLinkedListNode *cloneList(SinglyLinkedList *list, SinglyLinkedListNode *head) {
    if(head == NULL)
        return NULL;
    SinglyLinkedListNode *result = (SinglyLinkedListNode *)malloc(sizeof(SinglyLinkedListNode));
    result->data = head->data;
    if(head->next)
        result->next = cloneList(list, head->next);
    return result;
}

SinglyLinkedList *cloneFullList(SinglyLinkedList *list) {
    if(list == NULL)
        return NULL;
    SinglyLinkedList *result = (SinglyLinkedList *)malloc(sizeof(SinglyLinkedList));
    result->size = list->size;
    if(list->front != NULL)
        list->front = cloneList(result, list->front);
    return result;
}

But when trying to access the data like this

SinglyLinkedList *list1 =  (SinglyLinkedList *)malloc(sizeof(SinglyLinkedList));
list1 = cloneFullList(list); //where list is an already existing list which works correctly
SinglyLinkedListNode *curr1 = (SinglyLinkedListNode *)malloc(sizeof(SinglyLinkedListNode));
curr1 = list1->front;

Trying to access curr1->data returns a SEGMENTATION FAULT. But when I try to access the data by making curr1 = list->front the data is accessed correctly. Where is the fault in my function to clone the Linked List?

CodePudding user response：

I don’t think you understand correctly how things work… malloc allocates memory for your object, but does not initializes it. list1 = cloneFullList(list); this assigns the pointer to a new destination, but looses track of allocated space, without initializing it.

Also, your cloneList does not set next pointer on last element (when next is null), so it remains uninitialized. And same for cloneFullList (you should just remove if(list->front != NULL), since cloneList already takes care of the NULL case).

CodePudding user response：

In this part there is an error in variable name :

if(list->front != NULL)
    list->front = cloneList(result, list->front);
    // in previous line you modify list not result.
    // so result->front contents is undefined
    // you also missed the else when list->front is null
return result;

In both function you could use calloc to have NULL pointers or 0 integer as initial values

CodePudding user response：

A few issues:

• In your main code you allocate memory for *list1, but then immediately assign a different value to list1, leaking the allocated memory.

• Your code makes a similar mistake with curr1

• The functions make an assignment to next (or front respectively) only when a condition is true, but these properties should always get a value.

• There is an assignment to list->front which should be to result->front.

Not a problem, but the first version of cloneList really doesn't need the first parameter (the list). You can just do it with the node parameter only.

So here is the code updated:

// No need for the list as first argument:
SinglyLinkedListNode *cloneList(SinglyLinkedListNode *head) {
    if(head == NULL)
        return NULL;
    SinglyLinkedListNode *result = (SinglyLinkedListNode *)malloc(sizeof(SinglyLinkedListNode));
    result->data = head->data;
    result->next = cloneList(head->next); // No condition here
    return result;
}

SinglyLinkedList *cloneFullList(SinglyLinkedList *list) {
    if(list == NULL)
        return NULL;
    SinglyLinkedList *result = (SinglyLinkedList *)malloc(sizeof(SinglyLinkedList));
    result->size = list->size;
    result->front = cloneList(list->front); // No condition here
    return result;
}

int main(void) {
    // ... code that creates `list` comes here ...
    // 
    // No calls to malloc here...
    SinglyLinkedList *list1 = cloneFullList(list);
    SinglyLinkedListNode *curr1 = list1->front;
    // ...
    return 0;
}