Which data-structure is used widely in C? [closed]

Question

A couple of days ago I asked myself which data-structure I should in a function in C. I usually write in C++ and the choice would have fallen to std::vector.

There a some possible choices:

• a static (big enough) array
• a dynamic array which grows when needed(e.g. doubling its size)
• an own list implementation as struct with a pointer next

The last option seems to be unusual. Are there any bigger project where someone uses own structures like lists? Is there a general rule for the decision between array or own data-structures?

When I would need a tree structure I wouldn't think twice an just write a tree. Are there any widely used libs with such structures(like boost for C++)? Or is this considered as bad style because you would have to store a void* instead of the actual type?

Thank a lot for your experience!

Answer 1

Different data structures offer different computational complexity for insertions, lookups and other operations.

To take your specific example, there is a number of differences between an array and a linked list:

• lookup by index is O(1) in an array and O(n) in a list;
• insertions into a list are O(1) or O(n) (depending on whether they require traversal), and into an array are amortized O(1) if done well;
• deletions from an array are O(n) whereas certain types of list deletions can be done in O(1) time;
• arrays offer better locality of reference and consequently better cache performance.

You might find the following page useful: http://essays.hexapodia.net/datastructures/

As a general rule, when choosing a data structure I first consider whether I have strong reasons to believe that performance of the code in question is going to be important:

• if I don't, I choose the simplest data structure that would do the job, or the one that lends itself to the clearest code;
• if I do, I think carefully about what operations I am going to perform on the structure and choose accordingly, possibly followed by profiling.

As for recommendations for good C data structure libraries, take a look at Are there any open source C libraries with common data structures?

Answer 2

It completely depends on which operations you are going to perform on the data structure. If you will be retrieving data by index (eg, data[ 3 ]), then a list is a horrible idea since each read will require you to walk the list. If you will be inserting into the first position a lot (eg, data[ 0 ] = x), then an array will be terrible because you will be moving all the data for each insertion.

If you were going to use std::vector, then a dynamic array is probably the best replacement. But perhaps std::vector would not have been the correct choice.