Static vs dynamic data structures

Data structures exist in computer memory, usually on the heap. There are two main ways of allocating memory. Static data structures allocated a fixed amount of heap memory when they are created. Dynamic data structures allocate memory as needed, and can increase in size if required.

Static data structures

A good example of a static data structure is an array. An array is declared with a particular size, for example it might be able to hold 10 elements. The size is fixed, and it can never more or less the declared number of elements (10 in this case).

Static data structures are simple, and use the minimum amount of memory required to store the data. In early versions of languages such as C, the compiler only provided static data structures such as arrays and strings, and if programmers needed dynamic structures they would use an external library or simply write their own implementation.

Static data structures are ideal if you will never need to change the size of the data structure. If you are not sure how large the data structure needs to be, for example if you are implementing a queue and you don't know how many elements need to be queued, you might sometimes need to guess the required size. This can waste memory of you over estimate, or cause program errors if you under estimate.

Dynamic data structures

A good example of a dynamic data structure is a list. A list can start off small, or even empty, and grow automatically as you add more elements. It has no maximum size, and can keep growing until there is no memory left.

Dynamic structures make life easier for programmers because you don't need to try to guess how big to make the structure, and you don't need to worry what happens when it runs out of space. Generally, dynamic structures use slightly more memory and run slightly slower, but this is not usually an issue with modern computers.

Must current languages support dynamic data structures, and they are generally preferred over static structures except in special cases, such as when you are handling large amounts of binary data (for example, image data). Python, for example, does not use static arrays at all for general programming, you would always use lists instead - the exceptions are a few special types of array for images and data analysis.

See also

• Abstract data types
• Arrays
• Lists
• Array lists
• Linked lists
• Queues
• List based queues
• Circular queues