I've been reading through Introduction To Algorithms 3rd Ed, and am really enjoying the material; however, I am having difficulty in implementing some practical situations. It's not the theory, or implementing the internals of the data structures themselves, but rather how to design a good interface that makes the data structures useful for storing real data (as opposed to just the keys).

Specifically, I'm told that C has a very "trust the programmer" type philosophy. I just don't know how much trust is too much trust ..

Q1. To what extent should I be encapsulating my implementations? For most structures, you have both: (a) a data structure type, and (b) a type that can be inserted/deleted from the data structure. Should they both be hidden? Clearly if I expose a some node_t with the intention someone only alters key and *data.. theres the possibility prev or next is altered, thus destroying the data structure. A similar risk exists if I expose the data structure type and someone messes around with the root..

Q2. How should the keys be stored/accessed/compared? Presumably, the keys depend on the satellite data, but if you go the approach as above, you've decoupled the key from the data itself. What would happen if a user updates the data but forgets to update the key (or worse, they update the key, but don't remove/reinsert it into the ds)? For something like a binary tree which uses only comparisons, I could design the interface to accept comparators that accept pointers to the satellite data? This makes the structure more generalized, but all the defreferencing has to have an impact on speed. Alternatively, (and would be needed for structures like hashes which need a concrete key), I could accept a pointer to a int toKey(void *data)function..

I'm relatively new to C (and designing software) and am unclear on how good software should be designed for use in the real world..

I've been reading through Introduction To Algorithms 3rd Ed, and I am having difficulty in implementing some practical situations. It's not the theory, or implementing the internals of the data structures themselves, but rather how to design a good interface that makes the data structures useful for storing real data (as opposed to just the keys).

Specifically, I'm told that C has a very "trust the programmer" type philosophy. I just don't know how much trust is too much trust:

1. To what extent should I be encapsulating my implementations? For most structures, you have both: (a) a data structure type, and (b) a type that can be inserted/deleted from the data structure. Should they both be hidden? Clearly if I expose a some node_t with the intention someone only alters key and *data.. theres the possibility prev or next is altered, thus destroying the data structure. A similar risk exists if I expose the data structure type and someone messes around with the root..

2. How should the keys be stored/accessed/compared? Presumably, the keys depend on the satellite data, but if you go the approach as above, you've decoupled the key from the data itself. What would happen if a user updates the data but forgets to update the key (or worse, they update the key, but don't remove/reinsert it into the ds)? For something like a binary tree which uses only comparisons, I could design the interface to accept comparators that accept pointers to the satellite data? This makes the structure more generalized, but all the defreferencing has to have an impact on speed. Alternatively, (and would be needed for structures like hashes which need a concrete key), I could accept a pointer to a int toKey(void *data)function..

I'm unclear on how good software should be designed for use in the real world.