Creating a linked list of strings

Question

Warning: I'm quite new to low-level programming and memory management so please don't mind it when I'm asking incredibly stupid things.

I'm working on a project where I need to read all the lines from a file and store them for further usage. I decided to use a linked list of untyped pointers for this which will contain pointers to characters.

The following code for testing actually does the job but I've got a feeling that the creation and extending of the list could be done in a "cleaner" way.

list-test.c

struct Node {
  void *value;
  struct Node *next;
};

long int count_to_next(char which, char *buffer, long int max);
void string_copy(char *from, char *to, long int chunk_size);

int main() {
  char *raw = "Line 1\nLine 2\nLine 3";
  int remaining = 20;
  int chunk_size;
  char *pointer = raw;
  char *buffer;
  struct Node *root = malloc(sizeof(struct Node));
  struct Node *last = root;
  struct Node *lines;

  while (remaining > 0) {
    chunk_size = count_to_next('\n', pointer, remaining);

    buffer = malloc(chunk_size * sizeof(char) + 1);

    string_copy(pointer, buffer, chunk_size);
    *(buffer + chunk_size) = '\0';

    last->next = malloc(sizeof(struct Node));
    last->next->value = (void *) buffer;
    last->next->next = NULL;
    last = last->next;

    /* + 1 bc the '\n' is ignored */
    remaining -= chunk_size + 1;
    pointer += chunk_size + 1;
  }

  lines = root->next;

  /* do something with lines */
}

Answer 1

While I agree with most of what's been said in the comments, I do think that writing your own linked list is a worthwhile exercise. (Though so is learning about reallocating arrays.) So I'll go with that premise - that it's worth your time to write a linked list. And I think you've done a pretty good job to start with! Here are some suggestions.

Don't Reinvent The Wheel

You've written your own functions for count_to_next() and string_copy(). There are functions in the standard C library that do these same things, so you don't need to write your own. Instead, you could use strpbrk() and strdup() or memcpy(). strdup() actually allocates the memory for you, if you want to go that route.

Edit: Also, instead of calling malloc() and then manually setting each field to 0, you can use calloc(sizeof(Node), 1); to both allocate and clear the memory.

Use Types

You should create type definitions for your structures to make it easier to read and save some typing. I'd do this:

typedef struct Node {
    void* value;
    struct Node* next;
} Node;

Then, whenever you declare one, you can simply write:

Node *root;

instead of:

struct Node *root;

Avoid Magic Numbers

Instead of just putting the number 20 into your code, you should either have a named constant telling you what the value 20 represents (something like const int TEST_STR_LENGTH = 20;, or get the value from the string so you can change the string without having to update the value in the code. Like this:

int remaining = strlen(raw);

Name Your Variables Appropriately

The variable names raw, pointer, and buffer aren't very informative. I recommend naming them something like input_string, next_line, and string_copy or something along those lines.

Bugs

I think the last line is incorrect. I think it should be:

lines = root;

Otherwise you're starting with the second line.

Also, you were starting with an empty node with an uninitialized string, and ending with an empty node with an uninitialized string. I fixed the first by setting the value field of last before allocating a new node. I fixed the second by only allocating the next node if we have some characters remaining in the string.

Edit: I also realized that both of our implementations have another bug in them. If the file (or input string) is empty, we end up with a list containing an empty node, whereas we probably should not have a list at all. You could fix that by not allocating a node until you know you have a string. So root would start out as NULL and could end up as NULL if there are no lines in the input. I'll leave that as an exercise for the reader. :-)

So putting it all together, your function might look something like this:

#include <stdlib.h>
#include <string.h>

typedef struct Node {
    void* value;
    struct Node* next;
} Node;

int main() {
    char *input_string = "Line 1\nLine 2\nLine 3";
    long remaining = (long)strlen(input_string);
    long chunk_size;
    char *next_line = input_string;
    char *string_copy;
    Node *root = calloc(sizeof(Node), 1);
    Node *last = root;
    Node *lines = NULL;

    while (remaining > 0) {
        char* next_new_line = strpbrk(next_line, "\n");
        /* If the string doesn't end with "\n", we need the rest of the string */
        if (next_new_line == NULL) {
            chunk_size = remaining;
        }
        else {
            chunk_size = next_new_line - next_line;
        }

        /* This allocates and copies the string */
        string_copy = strndup(next_line, chunk_size);

        last->value = (void *) string_copy;

        /* + 1 bc the '\n' is ignored */
        remaining -= chunk_size + 1;
        next_line += chunk_size + 1;

        /* If there's more, then allocate another node for the next go round */
        if (remaining > 0) {
            last->next = calloc(sizeof(Node), 1);
            last = last->next;
        }
    }

    lines = root;

    /* do something with lines */
}

Oh, and don't forget to free() all those strings and Nodes after you've used them!