How do I pass a string to a linked list instead of an array of characters in C?

Question

I understand that there's no String data type in C. What I want to do is get an input string from the user and store it to a variable without having to define how many characters it needs to have. Can I do that using linked lists? I want to avoid putting it to a character array as much as possible so linked lists are the only thing I can think of but I don't know how to.

Answer 1

You could do it in a linked list, but a linked list of char will generally be an extremely inefficient data structure -- each node will have one char and (at least) one pointer. In a typical case, you're looking at 4 or 8 bytes for the pointer and one for the char, so you're imposing a lot of overhead.

My immediate recommendation would be to put at least 16 characters in each node in your linked list to keep the overhead at least sort of reasonable. Of course, a dynamic array will usually be better still, but at least that will keep a linked list from being totally unreasonable.

Answer 2

You could use a linked list, but the more usual approach is to allocate a block of memory with malloc() and dynamically resize that block with realloc() if the user input exceeds the bounds of the array.

void *malloc(size_t size);

The malloc() function allocates size bytes of memory and returns a pointer to the allocated memory.

void *realloc(void *ptr, size_t size);

The realloc() function tries to change the size of the allocation pointed to by ptr to size, and returns ptr. If there is not enough room to enlarge the memory allocation pointed to by ptr, realloc() creates a new allocation, copies as much of the old data pointed to by ptr as will fit to the new allocation, frees the old allocation, and returns a pointer to the allocated memory. If ptr is NULL, realloc() is identical to a call to malloc() for size bytes. If size is zero and ptr is not NULL, a new, minimum sized object is allocated and the original object is freed.

Answer 3

I'm pretty sure you do this with a char pointer.

char* storedString;

void storeString(char* inputString)
{
  char* s = storedString; // temporary handler
  while(++s = ++inputString); // copy string
}

int main(int argc, char** argv)
{
  storeString("hello");
  // you can now treat storedString as if it was an array of chars
  // containing: 'h'+'e'+'l'+'l'+'o'+'\0'
}

Answer 4

You could either:

1. calculate the length of string that will be needed (e.g. counting the number of chars until a newline is seen) then allocate a dynamic array using malloc(), this requires two-pass over the input string, OR
2. if it is impossible to precalculate how long an array should be, then you can malloc() a fixed amount of array, read from the user, then realloc() if the allocated size isn't big enough. This requires an n-pass, where n is the number of realloc() made.