Dynamic Data Structures

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

Example for Dynamic Data Structure

Some major examples of the dynamic data structures include –

1. Vector
2. Linked List
3. Stack
4. Queue
5. 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.

1. It makes efficient use of space in the memory.
2. It only uses that amount of space that is needed at any time for storage.
3. 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:

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