Back

An introduction to data structures - static v dynamic structures

Static verses dynamic implementation of data structures
The method used to structure data in a computer's memory can be classified in one of two ways, either as a static data structure or as a dynamic data structure.

Static data structures
A static data structure is one whose size is fixed. An example of a static data structure is an array. To use an array, the programmer needs to state a number of things:

array
 

    • Give the array a name.
    • Say what data type the array will hold.
    • Give the size of the array, state how many data items it can hold.

It is relatively easy (compared to dynamic data structures) to write the code that sets up an array. This type of structure allows fast access to the data held in it because you can use random access (hashing algorithms) or index sequential algorithms with arrays. In addition, when an array is defined, space is reserved in memory for it when the program is compiled - space for the data in the array will therefore always be available. However,

    • The size of the array is fixed before it is used. If the array has no data in it, it will still be taking up the space in memory that was allocated to it when it was compiled. This is not a very efficient use of memory.
    • Sometimes, estimating the array size needed is difficult.
    • Once the array is full, that is it! You can't put any more data into it.

pros_cons

Dynamic data structures
A dynamic data structure (such as linked lists, stacks, queues and trees) is one whose size can vary, depending upon the data storage needs of the program. With these types of structure, you don't need to fix the size in advance. The available RAM is used very efficiently because only the required space for actual data in the structure is used while the rest of the RAM is available for other applications. However,

    • These structures are more complicated to program than arrays.
    • Some structures can be slow. For example, linked lists only allow serial access not random access to data. If you had to search serially through one million records of drivers to find Zebb’s record, it would take a long time!

Back