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

Answer 2

Its always vice-versa, if you go with static then you loose memory whereas in case of dynamic, performance will be decreased. A best design would use the data structures efficiently, there is no one perfect answer.

Answer 3

Static data structures(SDS) are fixed sized (eg Arrays), the amount of memory once allocated to them cannot change on run time whereas Dynamic data structures(DDS)(eg Linked Lists) have flexible size , they can grow or shrink as needed to contain the data to be stored.

SDS are linear data structures which allow fast access to elements stored in them but the insertion/deletion operations are expensive compared to DDS where the access to the elements is slower but insertion/deletion is faster.

Most of the DS are Dynamic DS.

In case of SDS space is allocated before the actual data insertion so space may go wasted or may be insufficient some times so they should be used only in case the exact amount of data to be inserted is known in advance, if that is to be known at run time DDS should be used.