Differences between Static & Dynamic data structures

Question

What are the main differences, advantages and disadvantages between static and dynamic data structures?

Under which categories do the most common data structures fall?

How could I know in which situation to use each?

Answer 1

To start with an oversimplification:

There are just a few basic kinds of data structures: arrays, lists and trees. Everything else can be composed by using different types of these two structures (e.g. a hash table can be implemented with an array for the hash values and one list for each hash value to handle collisions).

Of these structures, arrays are static (i.e., their memory footprint does not vary over time as operations are performed on them) and everything else is dynamic (i.e., in the general case the memory footprint changes).

The differences between the two kinds of structures can be derived from the above:

• Static needs the maximum size to be known in advance, while dynamic can adapt on the fly
• Static does not reallocate memory no matter what, so you can have guaranteed memory requirements

There are also other differences, which however only come into play if your data might be sorted. I can't give an extensive list, as there are many dynamic data structures which exhibit different performance characteristics for different operations ("add", "remove", "find") and so they cannot be placed all under the same roof.

A very visible difference is that sorted arrays require moving (possibly a lot of) stuff around in memory for any operation other than "find", while dynamic structures generally perform less work.

So, to recap:

1. If you need a guarantee on maximum memory usage, you have no option other than an array.
2. If you have a hard upper limit for your data size, consider using an array. Arrays can be a good fit for problems which mainly require add/remove operations (keep the array unsorted) and for those which mainly require find operations (keep the array sorted), but not for both at the same time.
3. If you do not have a hard upper limit, or if you require all of add/remove/find to be fast, use an appropriate kind of dynamic structure.

Edit: I did not mention graphs, another kind of dynamic data structure which arguably cannot be composed from simpler parts (by definition, a tree has exactly one link going "into" any node except the root, while graphs may have more than one). However, graphs cannot really be compared with other structures in a "what would be better to use" scenario, because you either need to use a graph or you do not (other structures may exhibit different performance, but in the end they all support the same set of operations).