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
– StoryTeller - Unslander Monica, Commented Dec 11, 2012 at 14:47
What do you mean by more efficient? Efficient in terms of insertion, deletion, shifting, searching? — Mike
– Mike, Commented Dec 11, 2012 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
– Guid, Commented Dec 11, 2012 at 14:59
If the string is supposed to be immutable, you might want to declare *str a const within your struct. — munk
– munk, Commented Dec 11, 2012 at 15:00

Philipp · Accepted Answer · 2012-12-11 16:40:04Z

2

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.

edited Dec 11, 2012 at 16:40

answered Dec 11, 2012 at 14:52

Philipp

70.1k10 gold badges121 silver badges159 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Lundin Over a year ago

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 Over a year ago

I actually already suggested just that, before making that comment :)

MOHAMED · Accepted Answer · 2012-12-11 14:47:15Z

1

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"
}

answered Dec 11, 2012 at 14:47

MOHAMED

44k62 gold badges178 silver badges293 bronze badges

Comments

phaazon · Accepted Answer · 2012-12-11 14:47:17Z

1

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

answered Dec 11, 2012 at 14:47

phaazon

2,01216 silver badges21 bronze badges

Comments

Olympian · Accepted Answer · 2012-12-11 14:50:40Z

1

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.

answered Dec 11, 2012 at 14:50

Olympian

7781 gold badge6 silver badges13 bronze badges

Comments

ams · Accepted Answer · 2017-07-09 20:04:31Z

1

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.

edited Jul 9, 2017 at 20:04

answered Dec 11, 2012 at 15:59

ams

25.7k4 gold badges62 silver badges79 bronze badges

2 Comments

Tom Kuschel Over a year ago

@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.

ams Over a year ago

Fixed now. Well spotted.

Lundin · Accepted Answer · 2012-12-11 15:41:08Z

0

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.

answered Dec 11, 2012 at 15:41

Lundin

220k47 gold badges282 silver badges447 bronze badges

Collectives™ on Stack Overflow

linked list or array to store strings in C

6 Answers 6

2 Comments

Comments

Comments

Comments

2 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

6 Answers 6

2 Comments

Comments

Comments

Comments

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related