Dynamic vs Static
Types of Data Structure
Data structures are either:
Strong Data Structures
Strong types are the standard types, ie standard variable types typically available in a programming language. Examples:
These strong types provide the basis for all other types, for example a Static array is an array of a strong type.
Strong types are allocated a fixed amount of memory when defined.
Static Data Structure
With a static data structure, the size of the structure is fixed. Static data structures are very good for storing a well-defined number of data items. For example a programmer might be coding an 'Undo' function where the last 10 user actions are kept in case they want to undo their actions. In this case the maximum allowed is 10 steps and so he decides to form a 10 item data structure.
- The memory allocation is fixed and so there will be no problem with adding and removing data items.
- Easier to program as there is no need to check on data structure size at any point.
- Can be very inefficient as the memory for the data structure has been set aside regardless of whether it is needed or not whilst the program is executing.
Dynamic Data Structure
There are many situations where the number of items to be stored is not known before hand. Memory is allocated to the data structure dynamically i.e. as the program executes.
In this case the programmer will consider using a dynamic data structure. This means the data structure is allowed to grow and shrink as the demand for storage arises. The programmer should also set a maximum size to help avoid memory collisions.
For example a programmer coding a print spooler will have to maintain a data structure to store print jobs, but he cannot know before hand how many jobs there will be.
- Makes the most efficient use of memory as the data structure only uses as much memory as it needs
- Because the memory allocation is dynamic, it is possible for the structure to 'overflow' should it exceed its allowed limit. It can also 'underflow' should it become empty.
- Harder to program as the software needs to keep track of its size and data item locations at all times
The heap consists of a pool of memory which can be allocated to variables during the execution of the program. The heap makes dynamic variables possible, because these are variables which change in size during execution. The heap allows more efficient use of memory when dealing with data of an unknown and changing size.
Memory leaks occur when the program assigns memory for a dynamic variable but doesn't release it back to the heap after it has finished. The program then runs again, using a new memory location without releasing. This repeats, and eventually the heap runs out of memory the program crashes.
Most languages have a function to release the memory, in C# it is Dispose. Many high level languages have automated features, such as garbage collectors, to prevent memory leaks.
A garbage collector is a common feature of modern programming languages, it checks all the memory allocated to dynamic variables and if a dynamic variable has finished being used (i.e. nothing points to that memory any more) it will automatically free it. This way memory leaks should be avoided!