3. Dynamic and Static data structures

Reminder: A data structure is a collection of data items, in addition a number of operations are provided by the software to manipulate the data structure.

There are two approaches to creating a data structure.

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

2. DYNAMIC DATA STRUCTURE

There are many situations where the number of items to be stored is not known before hand.

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.

The table below compared the two approaches

Dynamic and Static data structures
DYNAMIC	STATIC
Memory is allocated to the data structure dynamically i.e. as the program executes.	Memory is allocated at compile time. Fixed size.
Disadvantage: 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.	Advantage: The memory allocation is fixed and so there will be no problem with adding and removing data items.
Advantage: Makes the most efficient use of memory as the data structure only uses as much memory as it needs	Disadvantage: 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.
Disadvantage: Harder to program as the software needs to keep track of its size and data item locations at all times	Advantage: Easier to program as there is no need to check on data structure size at any point.