linked list or array to store strings in C

Question

In C, I need to store a list of short strings (char*) that can be relatively large (thousands of items).
Strings can be removed or inserted but not modified, and the order is not important.
I don't know what is the more efficient data structure to do this.
I could use a struct :

struct node_s {
  char *str;
  node_s *next;
}

or an array of char * :

char **strings;

I don't need to access directly the strings, I just need them to exist because another data structure (a radix trie) beside maintains pointers on some parts of the strings.

Are you supposed to support frequent lookup? Because if you do, you may want to consider using some sort of dictionary (balanced tree or hash map), rather than a linear data structure. — StoryTeller - Unslander Monica, Dec 11 '12 at 14:47
What do you mean by `more efficient`? Efficient in terms of insertion, deletion, shifting, searching? — Mike, Dec 11 '12 at 14:48
In fact, I don't need to access directly the strings, I just need them to exist because another structure (a radix trie) has pointers on some parts of the strings. I just modified my post to precise it. — Guid, Dec 11 '12 at 14:59
If the string is supposed to be immutable, you might want to declare *str a const within your struct. — munk, Dec 11 '12 at 15:00
@usmcs: yes, but I need to be able to free the string eventually — Guid, Dec 11 '12 at 15:01
@Guid You can free by casting it to a non const string [like this](http://stackoverflow.com/questions/2819535/unable-to-free-const-pointers-in-c) — munk, Dec 11 '12 at 15:04
Ok, I see elsewhere that casting a const char * into a char * to free an immutable string seems to be a standard. Ugly but it's fine. Thanks. — Guid, Dec 11 '12 at 15:08

Philipp · Accepted Answer · 2012-12-11T16:40:04.003

When you don't know the exact number of entries at initialization, using a linked list is usually a better decision than using an array.

An array has a fixed size. When you don't know how many entries you will have and you want to use an array, you have two options. Either you allocate an array which is vastly larger than anything you will ever need, which is a huge waste of memory (also, it's often hard to know in advance what a reasonable upper limit should be). Or you start with a small array and wait until it is full. Then you allocate a new, larger array, copy all entries to the new array and deallocate the old, which is a huge waste of CPU cycles.

But with a linked list, you don't have that issue as they can grow and shrink dynamically.

But be aware of the differences in runtime of various operations.

In an array, getting an element by its index is very fast. But removing an element with a specific index without leaving an empty entry is very expensive, because every single element which follows must be moved back by one index. Inserting an entry in the middle without overwriting a existing one is equally expensive, because you have to move everything which follows forward by one.

With a linked list, removing or inserting a node in the middle is fast (when you already have its precedessor node), because no nodes except for the inserted node and its precedessor need to be touched. But finding the node after which this operation has to take place can be expensive, because you have to follow the links through all nodes which come before.

When you need both fast lookup and fast insertion/removal, then using a binary tree is a good compromise.

Neither an array nor a linked list sound particularly suitable for this case. A binary tree with thousands of strings, sorted by alphabetic order, will also become quite slow. — Lundin, Dec 11 '12 at 15:42
I actually already suggested just that, before making that comment :) — Lundin, Dec 11 '12 at 19:16

score 1 · Answer 2 · answered Dec 11 '12 at 14:47

It depends of your program.

If you know the number of string. I advice you to use the array

If you do not know the number of string I advice you to use linked list

If the string will be define in C as constant. You can use this way:

char *strings[1000] = {
  "string 0",
  "string 1",
  "string 2",
  "string 3",
   .
   .
   .
  "string 999"
}

score 1 · Answer 3 · answered Dec 11 '12 at 14:47

1

Actually, char **strings is just an array of string. array ≠ linked list. Then the node_s is definitely the solution.

answered Dec 11 '12 at 14:47

phaazon

1,972
15
21

score 1 · Answer 4 · answered Dec 11 '12 at 14:50

It depends of what you want to do with them.

If order not important, I think most operations will be add\remove.. If it's true you need to select list data structure(first variant).

Array is good if you need constant-time access to element, but in unordered array this wouldn't work.. Searching for some string will take O(n) time, like in list.

ams · Answer 5 · 2017-07-09T20:04:31.077

So, if I understand correctly, the list of strings is not the primary way that the data will be accessed, it just a "cleanup list" of pointers that must be freed without having to grub through all the other, now obsolete data.

In that case, I would use a linked list, but not in the normal way. Your node_s above requires that, for each string, you do one malloc for the struct, and one for the string itself.

Instead, I would define a struct like this:

struct string_list {
  struct string_list *next;
  char data[0];
};

The zero-length array takes up no space in the struct, but gives you a typed address you can take. You can then malloc memory for the struct and the real string:

struct string_list *newstr = malloc (sizeof(struct string_list) + my_desired_size);

You then place your data at newstr->data, and link up the next pointer:

newstr->next = list_head;
strcpy (newstr->data, my_data, my_desired_size);
list_head = newstr;

When it's time to release the string, one free is all that's needed. Oh, and fixing up the links, of course.

@ams: you defined a `char string[0]` in the struct, shouldn't it be `char data[0]` because you strcpy to a `newstr->data` which isn't defined yet? Nonetheless a good idea to add data to the head. — Tom Kuschel, Jul 09 '17 at 19:27

score 0 · Answer 6 · answered Dec 11 '12 at 15:41

When you have a large number of items and you want to add/remove items frequently, while having an access time close to random access O(log n), you should consider a hash table.

A linked list will get dreadfully slow access times if you add thousands on nodes, and an array is not suitable for frequent add/removal.

linked list or array to store strings in C

6 Answers6