CODEWITHSUNDEEP
cpointerslinked-list
user16830968
user16830968

Reputation: 1

Recursive linked list garbles output in C

I'm writing a recursive linked list and all seems well until I try to output any information stored in the list to the screen. Here is the structure and enum definitions (ps. 'List' is used to refer to a node in the List):

typedef enum ListType ListType;
typedef struct List List;

enum ListType {
    STRING, 
    LIST
};

struct List { 
    union {
        char* STRING;
        List* LIST;
    };
    ListType type;
    List* next;
};

I wrote a function-to-rule-them-all to create and clone "lists" which follows this. Because variable argument lists aren't easily done in C (esp. with different variable types, etc.) new_list() accepts a string_source and a list_source. It is done on the assumption that one of them is set to NULL and the other is the actual value. The checking for this is done at the start of the function and the parameter that isn't NULL is used to infer the type. Then, if the type is a STRING, then the string can be copied to a newly allocated List. If it is a LIST, then it has to be determined whether the LIST to be copied contains a STRING or a LIST. new_list is recursively called. Then, if next_source is not NULL, then the list it points to is copied, otherwise the new list's "next" is set to NULL.

List* new_list(char* string_source, List* list_source, List* next_source) {
    ListType ctype;
    if(string_source == NULL && list_source == NULL) return NULL;
    if(string_source == NULL && list_source != NULL) ctype = LIST;
    if(string_source != NULL && list_source == NULL) ctype = STRING;

    List* temp = calloc(1, sizeof(List));
    if(ctype == STRING) {
        int n = strlen(string_source) + 1;
        temp->STRING = calloc(1, n);
        strcpy(temp->STRING, string_source);
    } else {
        if(list_source->type == STRING) {
            temp->LIST = new_list(list_source->STRING, NULL, list_source->next);
        } else {
            temp->LIST = new_list(NULL, list_source->LIST, list_source->next);
        }
    }
    temp->type = ctype;
    
    if(next_source != NULL) {
        temp->next = new_list(NULL, next_source, next_source->next);
    } else {
        temp->next = NULL;
    }
    return temp;
}

With the following test:

int main() {
    List* tail  = new_list("World", NULL, NULL);
    List* head = new_list("Hello ", NULL, tail);
    printf("%s\n", head->STRING);
    printf("%s\n", head->next->STRING);
}

Compiling with GCC gives me the output:

Hello 
`�E�lU

Obviously, the expected output should be:

Hello 
World

And when I try to print "tail->STRING" it outputs "World" correctly, so it is likely a problem with the copying code. What have I done wrong and what can I do to improve?

Upvotes: 0

Views: 53

Answers (1)

Robert Harvey
Robert Harvey

Reputation: 180787

You don't need the STRING/LIST bifurcation. Just use pointers for your list elements.

If you need the list to be polymorphic, use void*, keep track of the type you're storing, and cast it back to that type when you retrieve the element.

typedef struct {
    void* element;
    char type;
} ListItem;

Or something like that. A list built this way will work for any type, and the only time you ever have to think about the type is when you retrieve the element from the list.

Upvotes: 1

Related Questions