Implementation of a string singly linked list in C

Question

I want to make a singly linked list containing strings in each node, instead of integers.

However, I'm unable to implement it. Can someone please tell me what is wrong with the implementation?

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

struct node {
  char data;
  struct node* next;
};

struct node* create(struct node* head, const char* data) {
  struct node* newnode, * temp;
  newnode = (struct node*)malloc(sizeof(struct node));
  newnode->data = data;
  newnode->next = NULL;
  if (head == NULL) {
    head = newnode;
    temp = newnode;
  }
  else {
    temp->next = newnode;
    temp = temp->next;
  }
  temp->next = NULL;
  return head;
}

struct node* display(struct node* head) {
  struct node* temp;
  temp = head;
  while (temp != NULL) {
    printf("%d->", temp->data);
    temp = temp->next;
  }
  printf("NULL");
  return head;
}

int main() {
  struct node* head;
  head = NULL;
  int size, i;
  char str[5];
  printf("\nSize of linked list you want: ");
  scanf("%d", &size);
  for (i = 0; i < size; i++) {
    gets(str);
    head = create(head, str);
  }
  display(head);
  return 0;
}

Answer 1

char data holds a single character. That's not what you want, right? You want to hold a string, i.e. a pointer to the first character:

struct node {
  char *data;
  struct node* next;
};

This holds the string through a pointer - it's not clear whether you want this pointer to be an owning pointer (i.e. if node goes away then the string goes away too), or a reference (i.e. someone else owns the string and manages its lifetime).

There are other mistakes as well, but that'd be a good starting point. And enable all the warnings from the compiler, and understand them all because in case if your code, most of them are really bugs that the C language allows (since it can't be sure what you really wanted) - but that doesn't mean that the code is correct.

Another way of holding the string may be by value, i.e. instead of having just one character like you did in your answer, you may hold an array of those - see another answer to this question for how to do that. The choice between owning a string via a pointer vs. owning it as a value is of little importance in introductory teaching code where you don't measure the performance of the data structure in a real-life use case. So there's no "one true choice": each one has benefits in certain use cases.

Some vague recommendations (always subject to measurements!) may be:

• if the values are constant, then holding the string by value as either a fixed size or variable size usually wins in performance

• if the values have a small range of sizes (e.g. all strings are "short"), then having a fixed size node and allocating it in a contiguous memory pool may improve performance

• if the values change, then holding the string by value is not always feasible: the node may need to be reallocated to resize it, and then you need a doubly-linked list to adjust to pointers of neighboring nodes to reflect the new address of the node

• the most generic and potentially worst performing option is to hold the string via an owning pointer, so the node can stay at a fixed address, but the string can move; in that case a small string optimization may improve things further if there're lots of small strings: hold the string inside the node's fixed-size char array if it fits there, but otherwise allocate it in a separate memory block; that's what's typically done in implementations of std::string and it improves performance. The thinking is that since the string is "big", then the overhead to of having to reference some other address to get at its data will be minuscule compared to whatever work is then done with the actual value of that string.

Answer 2

There are several problems:

• you need an array of char in your struct instead of c char
• the create function is overly complicated and wrong

OTOH your display function is correct.

You want this:

For explanations, look at the comments.

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

#define MAXSTRINGSIZE 100                  // maximum allowed size of strings

struct node {
  char data[MAXSTRINGSIZE];                // we need an array of char her, not a char
  struct node* next;
};

struct node* create(struct node* head, const char* data) {
  struct node* newnode = malloc(sizeof(struct node));   // no cast is needed with malloc
  strcpy(newnode->data, data);             // copy the string

  newnode->next = head;  
  return newnode;
}

struct node* display(struct node* head) {
  struct node* temp;
  temp = head;
  while (temp != NULL) {
    printf("%s->", temp->data);
    temp = temp->next;
  }

  printf("NULL");
  return head;
}

int main() {
  struct node* head;
  head = NULL;
  int size;
  char str[MAXSTRINGSIZE];
  printf("\nSize of linked list you want: ");
  scanf("%d", &size);

  getchar();             // absorb \n, scanf and gets don't mix well

  for (int i = 0; i < size; i++) {
    gets(str);
    head = create(head, str);
  }

  display(head);
  return 0;
}

Notes

• Instead of having a fixed size data member in your struct, you could have a pointer and allocate just the amount of memory needed for the string to store. I let you figure this out yourself.
• instead of gets which is a deprecated function, you should rather use fgets. Read this for more information.