A data structure is a way of storing, organizing, and efficiently maintaining data concerning both time and space. Data structures can be of two types, static and dynamic data structures. Static data structures are the ones in which the size of the structure is predefined and fixed. On the other hand, dynamic data structures are the ones whose size and data both can be modified at the runtime. Sometimes, we cannot predict the size of the data structure beforehand, therefore in such situations, we use dynamic data structures since it is flexible to increase or decrease the size. Some of the examples of dynamic data structures are LinkedList, Stack, Vector, etc. You can refer to the article What is Data Structure? for more information on data structures.

## Takeaways

- A dynamic data structure can grow or shrink in size as required.
- Major disadvantage of dynamic data structures is that there is a possibility of underflow or overflow while performing allocation or deallocation of memory.
- Dynamic memory allocation can be done both on the stack and the heap.

## What is Dynamic Data Structure?

There are many situations where we do not know how much data needs to be stored in the memory beforehand, that is where dynamic data structures come to our rescue. The dynamic data structures are the ones that do not have a fixed size. Therefore, these structures have the flexibility to increase or decrease their size during runtime. These data structures grow or shrink in size as per the demand comes. It gives the power to the programmer to control exactly how much memory should be utilized while storing the data by occupying only that amount of space as much as there is the data to be stored. These data structures can allocate or deallocate the unused memory as per the need. However, since the allocation of memory is not fixed, therefore, there is a possibility of overflow if the data structure exceeds the maximum memory limit or underflow if the structure becomes empty.

## Use of Dynamic Data Structure

The main use of dynamic data structures is that they easily facilitate the change in size without affecting the other operations that are performed on the data structures during runtime. However, the dynamic data structures are also widely used in competitive programming where the constraints on the memory limit are high and we cannot exceed the memory limit specified in the constraints. Given a high memory constraint, we cannot allocate a static data structure of such a large size therefore, dynamic data structures are useful in such cases.

## Dynamic Data Structures VS Static Data Structures

Static data structure | Dynamic data structure |
---|---|

1. A static data structure has a fixed and predefined size because of which it can store only a particular amount of data in the memory. | 1. Dynamic data structures can store any amount of data in the memory since it does not have a fixed size. |

2. The size of the structure cannot grow or shrink. | 2. It can easily grow or shrink in size as per the need. |

3. A static data structure can only modify the data in the memory. | 3. A dynamic data structure can modify both the data items as well as the size of the structure during runtime. |

4. They are not very efficient as compared to dynamic data structures as they have a fixed size. | 4. The size of the dynamic data structures is randomly updated during runtime which is why it is considered more efficient. |

5. Static memory allocation can only be done on the stack. | 5. Dynamic memory allocation can be done on both stack and heap. |

6. They are not as flexible as the dynamic data structures because of their fixed size. | 6. The dynamic data structure is more flexible than the static data structures because of their easily growable and shrinkable size. |

7. An example of a static data structure is an array. | 7. An example of a dynamic data structure can be a linked list. |

## Example for Dynamic Data Structure

Some major examples of the dynamic data structures include –

- Vector
- Linked List
- Stack
- Queue
- Tree

All these above examples are dynamic data structures because of their dynamic size. However, their size need not to specified in advance as in the case of a static data structure. Linked List is one of the dynamic data structures as it can grow or shrink its size as per the elements stored in it. Moreover, it does not need to specify the size of the structure in advance. Now, let us implement a linked list to understand the usage of a dynamic data structure with more clarity. The below program implements a singly linked list with three functions to insert in the front, end and printing the elements of the list.

```
import java.io.*;
public class LinkedList {
```*//head of the linkedlist*
Node head;
static class Node {
int val;
Node next;
*//constructor*
Node(int v){
val = v;
next = null;
}
}
*//adding a node in the front of the list*
public void insertFront(int new_val){
*//Allocating and putting the value into a node*
Node new_node = new Node(new_val);
*//Making the new node's next as the head and the head as the new node*
new_node.next = head;
head = new_node;
}
*//Inserting an element in the last of the linked list*
public void insertLast(int new_val){
*//Allocating and putting the value into a node*
Node new_node = new Node(new_val);
*//if there is not element in the linked list, add the new node and make it head*
if (head == null){
head = new Node(new_val);
return;
}
*//make the new node's next as null as it will be the last element*
new_node.next = null;
Node temp = head;
*//traversing till the last element*
while (temp.next != null)
temp = temp.next;
*//making the next of the last element to be the new node*
temp.next = new_node;
return;
}
*// Printing the elements of a LinkedList.*
public static void print(LinkedList list){
Node temp = list.head;
System.out.print("LinkedList Elements: ");
*//traversing the list and printing each value*
while (temp != null) {
System.out.print(temp.val + " ");
temp = temp.next;
}
}
*//main function*
public static void main(String[] args){
*//Creating an empty list*
LinkedList list = new LinkedList();
*//adding element in the front*
list.insertFront(1);
list.insertFront(2);
*//adding element in the last*
list.insertLast(8);
list.insertLast(9);
list.insertFront(5);
list.insertLast(4);
*// Print the LinkedList*
print(list);
}
}

Output:

```
LinkedList Elements: 5 2 1 8 9 4
```

In the above program, we do not need to fix or predefine the size of the list since it is a dynamic data structure.

We have implemented two insertion functions, insertFront() and insertLast() that are used to insert an element in the front and in the last respectively, and a print() function to print the elements present in the list. Therefore, we can clearly see that as we get the elements, we keep storing them in the front and in the last by calling any of the functions, and the size of the linked list is increased automatically at the runtime.

## Advantages and Disadvantages of Dynamic Data Structures

The advantages of the dynamic data structures are listed below.

- It makes efficient use of space in the memory.
- It only uses that amount of space that is needed at any time for storage.
- The unused space of the memory can be returned to the system for other purposes.

However, the disadvantages of the dynamic data structures are as follows:

- It is difficult to program the dynamic data structures as the system needs to keep track of the size and data item’s locations at all times.
- Since the memory allocation is dynamic, there is a possibility of overflow and underflow in case the structure exceeds its maximum limit or if the structure becomes empty respectively.
- It is slow for implementing searches such as accessing an element in a linked list takes a linear time.

## Conclusion

- A dynamic data structure has a dynamic size, that is, its size can grow and shrink based on the elements present in it at runtime.
- It makes efficient use of memory by using only that amount of space in memory that is required at any time.
- Dynamic memory allocation can be done in both the stack and the heap.
- However, they are difficult to program as the system needs to keep track of the size and data item’s locations at all times.
- It is more flexible because of its growable and shrinkable size.