Using a linked list as a char buffer for strings

Question

I've been getting into data structures in C lately, and I got the idea of making a char buffer which grows dinamically has you type by adding each character into a Linked List, and whose contents can be copied into a char array. Here is the code I ended up with:

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

//Here is the base structure of the LinkedList.
typedef struct linked_list_char {
    size_t size;                      //Number of characters (only known by the head)
    char item;                        //Character.
    struct linked_list_char* next;    //Next node.
} DavidLinkedListChar;

typedef DavidLinkedListChar* LinkedListChar; //This is how the head will be declared.

//Adds each node.
void addChar(LinkedListChar* head, char newItem) {
    LinkedListChar tracer = *head;    //This will go through the list.
    //If the head is NULL, the head will be accessed directly
    if(*head == NULL) {           
        *head = malloc(sizeof(DavidLinkedListChar));
        (*head)->item = newItem;
        (*head)->next = NULL;
        (*head)->size = 1;   //The size will be one.
    //If it isn't, the tracer will find the end of the list and insert a node.
    } else {
        while(tracer->next != NULL) tracer = tracer->next;
        tracer->next = malloc(sizeof(DavidLinkedListChar));
        tracer->next->item = newItem;
        tracer->next->next = NULL;
        (*head)->size++;    //The size will increase by one.
    }
    //I nullify all the pointers used, although I don't know if it is necessary.
    tracer = NULL;          
    head = NULL;
}

//Takes a char and allocates each character in the list, plus '\0'.
void convertIntoStaticString(char* destination, const LinkedListChar* source) {
    LinkedListChar tracer = *source;    //This will go through the list.
    int i = 0;                     //This will find the index in which '\0' needs to be.
    //This loop doesn't count the last member of the list, which is '\n'.
    while(tracer->next != NULL){
        destination[i] = tracer->item;
        tracer = tracer->next;
        i++;
    }
    destination[i] = '\0';     //Now the char array is null terminated.
    //Again: I don't know if this is necessary.
    tracer = NULL;
    destination = NULL;
}

//This function frees the entire list.
void deleteListChar(LinkedListChar* lChar) {
    LinkedListChar tracer = *lChar;     //This will go through the entire list
    LinkedListChar prev = NULL;         //This will contain the memory to be freed.
    //tracer will go down the list while every previous node pointed will be destroyed.
    while(tracer->next != NULL) {
        prev = tracer;
        tracer = tracer->next;
        free(prev);
        prev = NULL;
    }
    free(tracer);        //Frees the last node.
    free(*lChar);        //Frees the head (although it was probably freed already, but just in case it wasn't)
    //Nullifying everything.
    (*lChar) = NULL;
    lChar = NULL;
    tracer = NULL;
}

int main() {
   LinkedListChar cbuffer = NULL;
    char key = 'n';      
    //While the key isn't '\n', it will keep adding characters to the list.
    while(key != '\n') {
        key = fgetc(stdin);
        addChar(&cbuffer, key);
    }
    //Flexible char array of the same size as the buffer(counting the later ignored '\n' node).
    char name[cbuffer->size];
    //Copies the chars from the Linked List to the char array.
    convertIntoStaticString(name, &cbuffer);
    //Deletes the buffer.
    deleteListChar(&cbuffer);
    //Prints the char array.
    printf("%s", name);
    //Pauses until enter is pressed.
    getc(stdin);
    return 0;
}

This seems to work just fine; however I would like to know what more experienced programmers think of this. Plus, there's a considerable increase in memory for something like my fullname (which is 33 characters long, including blankspaces) of 20 KB, according to the Windows program manager. Do you guys think this was worth trying? Does my code contain any potential memory leak that might hinder performance? If one of you can try this code on the Linux Shell and tell me how well or badly it performed, it would be of great help!

Answer 1

I don't like typedef like this:

typedef DavidLinkedListChar* LinkedListChar;

For that makes the code harder to read, specially when reviewing code from other people. You overlook that line and the code does not make any sense.

//I nullify all the pointers used, although I don't know if it is necessary.
tracer = NULL;          
head = NULL;

Some people consider this good practice setting the freed pointers to NULL, but in this case I personally don't see the point in NULLing these two pointers, you are not using them after these two instructions anyway, in fact the function ends at that point. Setting these pointers can have some benefits if later you want to check if they are still valid or not, but in this case I don't see any benefit to that.

---

void convertIntoStaticString(char* destination, const LinkedListChar* source);

I don't see why you pass a pointer to LinkedListChar here, you are not manipulating the contents of the list in any way. I'd declare this function as

void convertIntoStaticString(char* destination, const LinkedListChar source);

---

Your deleteListChar is almost correct:

//Frees the head (although it was probably freed already, but just in case it wasn't)
free(*lChar);

*lChar was indeed freed in the first iteration and because since then you haven't change where *lChar is pointing to, you are doing a double free with the same address, this is undefined behaviour. So remove that line. The (*lChar) = NULL; line is OK, here I see a benefit of setting it to NULL.

---

One problem with your implementation is that you don't check the return values of malloc, if it returns NULL, you cannot dereference the pointers. You should alway check the return values of malloc, calloc and realloc.

And it's better practice to do the malloc like this:

int *arr = malloc(size * sizeof *arr);

I try to avoid sizeof(<type>) whenever possible, it's easy to make mistakes (add a * too much for example) and it's easy to overlook when reviewing code. On the other hand, using sizeof *arr will give you always the correct size regardless of the type of arr, if you later change the type, then you don't have to worry about the sizeof inside of functions that take the size of objects as argument. So in this case I'd do:

*head = malloc(sizeof **head);

---

void convertIntoStaticString(char* destination, const LinkedListChar* source);

Here I also don't see why you pass a LinkedListChar *source instead of a LinkedListChar source.

One bigger problem is that you don't take the size of the destination in consideration, if the buffer is not large enough, you will overflow it.

Functions that take a pointer to a buffer should always take the length of the buffer as argument as well, unless the end of the buffer is somehow encoded in the values (like the '\0'-terminating byte for strings), but in this case this function simple cannot know when to stop. So I'd rewrite this functions as:

int convertIntoStaticString(char *destination, size_t len, const LinkedListChar *source)
{
    if(destination == NULL || source == NULL || *source == NULL)
        return 0;

    LinkedListChar tracer = *source;    //This will go through the list.
    int i = 0;                     //This will find the index in which '\0' needs to be.

    // making sure not to overflow destination
    while(tracer->next != NULL && i < len - 1){
        destination[i] = tracer->item;
        tracer = tracer->next;
        i++;
    }

    destination[i] = '\0';     //Now the char array is null terminated.

    return 1;
}

and you would call it:

char name[1024];
convertIntoStaticString(name, sizeof name, &cbuffer);

or

char name[cbuffer->size+1];
convertIntoStaticString(name, sizeof name, &cbuffer);

This way your code is simply more robust.

---

What do I think about this implementation? As an exercise of linked lists, it's OK, but I would not use that in production code, it has way to much overhead for my taste when you can implement the same with a simple loop and one realloc call:

#define BLOCKSIZE 64

char *get_line(FILE *fp)
{
    if(fp == NULL)
        return NULL;

    char *buffer = NULL, *tmp;
    size_t size = 0;
    size_t i = 0;
    int c;

    while((c = fgetc(fp)) != '\n' && c != EOF)
    {
        if(i == size)
        {
            tmp = realloc(buffer, size + BLOCKSIZE + 1);

            if(tmp == NULL)
            {
                // return all we've got so far
                if(buffer)
                    buffer[i] = 0;
                return buffer;
            }

            buffer = tmp;
            size += BLOCKSIZE; // do not count the + 1 for the
                               // 0-terminating byte, size should
                               // remain a multiple of BLOCKSIZE
        }

        buffer[i++] = c;
    }

    if(buffer == NULL)
    {
        if(c != EOF)
        {
            return strdup(""); // user just pressed ENTER
        } else
            return NULL; // fp has no characters to be read
    }

    buffer[i] = 0;
    return buffer;
}

And if strdup is not available on your system

char *strdup(const char *txt)
{
    if(txt == NULL)
        return NULL;

    char *tmp = calloc(strlen(txt), 1);

    if(tmp == NULL)
        return NULL;

    return strcpy(tmp, txt);
}