With the daily evolution of information technology, computer is used for many purposes than it was used to. So that, resource usage of a computer is increasing, such as memory usage and processing. With the increasing usage of system resources, it is a must to ensure effective and efficient use of available resources. Data Structure is a way of storing and organizing data, effectively. There are two major categories of Data Structures called ˜’Static Structures’ and ‘˜Dynamic Structures’. Each has its own set of advantages and disadvantages.
Static Data Structures
As same as the word static suggests, static data structures are designed to store static “set of data”. However, static “set of data”, doesn’t mean that we can not change the assigned values of elements. It is the memory size allocated to “data”, which is static. So that, it is possible to change content of a static structure but without increasing the memory space allocated to it.
Dynamic Data Structures
Dynamic data structures are designed to facilitate change of data structures in the runtime. It is possible to change the assigned values of elements, as it was with static structures. Also, in dynamic structures the initially allocated memory size is not a problem. It is possible to add new elements, remove existing elements or do any kind of operation on data set without considering about the memory space allocated initially.
Static Data Structures vs. Dynamic Data Structures
Static data structure is given a fixed area of memory which it can operate within. It is not possible to expand this fixed size in the run time. So that, locations of each element is fixed and known by the program. Dynamic data structure also has an area where it can operate. However, this size of the area is flexible, not fixed as it was with static data structures. It is possible to expand or contract the area as required, by adding or removing elements from data structure.
From here onwards an example of a static array and a dynamic linked list, will be considered to discuss differences.
Access to elements.
Static data structure has a fixed size. Also, elements of static data structures have fixed locations. But in dynamic structures, elements are added dynamically. So that, the locations of elements are dynamic and determined at runtime. A program will have to refer a common object or, go through the structure to find required element. Consider the example data structures.
Consider that values denoted as “AXX” are memory address. Memory addresses are noting similar to this, but these values are used, just for the purpose of discussion. Consider that we need to access element “D”. In the static structure, it is possible to directly access the memory location “A04″ as it is already known by the program. However in dynamic structure, elements are added to the data structure dynamically. Sometimes even by different components of a program. Consider the scenario of linked lists. When we need to access element “D”, program doesn’t know that it is located in “A65″ memory location. So program starts with the initial element which is “A” located in “A01″. Element A points to the next element, which is B. B points to C and C in turn points to D. In order to access a single element, it was required to go though the linked list.
However it is possible to create a common object which keep track of memory location of each object and use it to directly access an element of a dynamic structure. Even in that case, it is a must to access number of object to do so. It is clear that access to elements of data structures is efficient with static structures, more than it is with dynamic structures.
Insertions and Removals
As discussed earlier, static structure has fixed sizes. It is possible to remove the value of an element, but the element is still there in the structure. Only difference is that element doesn’t contain any data. Such removal is not going to free the memory occupied by the element and can be considered as a waste of resources.
What about adding new elements to a static structure? As you already know it is not possible because static data structure has a fixed size. In order to add new element, we should create a new static structure with number of elements required and move the data from existing structure to new structure and assign additional elements with required values.
Unlike static data structures, dynamic data structures are flexible. They do not have a fixed number of element or fixed size. So it is possible to add or remove elements easily. Consider a linked list as an example. As discussed earlier, elements of a linked list points to next element of the list. Imagine that you want to remove element “C” of below linked list. As you can see “B” is pointing at “C” and “C” is pointing at element “D”. If we remove element “C”, element “B” should point to element “D”, to keep the linked list unbroken. So what we have to do is just changing the pointers and assign element “C” with a NULL value, so that garbage collator (or similar mechanism) will remove the object and release the memory consumed by that object. An example is shown below.
Addition of new items to an dynamic data structure is also similar to the process of removal. Imagine that we want to add an element after element “B” and before element “C”. What we have to do is simply adding the new element to memory, changing pointer of B to point to newly added element and setting pointer of new element to point at element “C”.
So it is clear that, removal of an element from Static Data Structure is not possible. It is possible to remove or null the value of element, but it will not free the memory consumed by the element. It is possible to create a new static data structure and move the data from previous structure, excluding the valued needed to be removed. However, it is a resource consuming process, as it creates number of instances of data structures to complete the process.
When it comes to dynamic data structures, removal is efficient and easy to manage. In linked lists, it is all about setting an object to null and changing some pointers. No new objects will be created and resource consume is at minimum.
Insertion is also same, static structures have a fixed size, so insertion of elements in not possible. The only way of inserting elements to a static data structure is creating a new data structure with required number of elements and copying the previous values in to new structure. This is again a resource consuming process. Think of a array containing 1000 elements and you want to add a new element at the end. You’ll have to create a new array with 1001 elements and move values from previous array to new array making number of calls.
But when it comes to dynamic structure, addition of an element is a simple process. In linked lists, it is just creation of an object and changing two pointers. When compared with static data structures, resource consume is at minimum and resources are used effectively.
Advantages and Disadvantages
According to above discussion it is clear that dynamic data structures share following characteristics
- Ability to efficiently add, remove or modify elements
- Flexible size
- Effective use of resources – because resources are allocated at the runtime, as required.
- Slower access to elements (when compared with static data structures)
- Faster access to elements (when compared with dynamic data structures)
- Add, remove or modify elements is not directly possible. If done, it is a resource consuming process.
- Fixed size.
- Resources allocated at creation of data structure, even if elements are not contain any value.
So it is clear that both data structures share advantages and disadvantages. It is not effective to use dynamic structures to store set of data that is known, not to change. Using static data structure in such case will save system resources and also provide faster access to elements. Users or developers are responsible to use appropriate data structures, according to the situation.