What is Dynamic Data Structure?
Dynamic data structures are flexible in size and can grow or shrink as needed during program execution. This adaptability makes them suitable for handling data of varying sizes or when the size is unknown beforehand. Examples of dynamic data structures include linked lists, stacks, queues, and trees.
Features of Dynamic Data Structures:
There are many features of dynamic data structures. Let’s discuss the most popular of them:
- Dynamic Memory Allocation: Dynamic data structures allocate memory at runtime, rather than being pre-allocated at compile-time. This memory is stored in the program’s heap.
- Flexible Memory Usage: Unlike static data structures, the memory used by dynamic data structures is not limited to a fixed size. It can expand or contract as needed during program execution.
- Manual Memory Management: The memory allocated to dynamic data structures does not automatically deallocate when the structure goes out of scope. The programmer is responsible for manually deallocating this memory, often using functions like free() or delete(), to avoid memory leaks.
- Non-Contiguous Memory: The memory locations used by dynamic data structures are not guaranteed to be contiguous. This means additional metadata must be stored to track the locations of each element within the data structure.
Advantages of Dynamic Data Structures:
- Dynamic data structures can grow or shrink in size as needed, allowing for efficient use of memory.
- They can allocate and deallocate memory dynamically, preventing wastage of memory.
- Dynamic data structures can handle large and varying amounts of data without pre-defining the size.
- They provide a simpler programming interface compared to static data structures.
Disadvantages of Dynamic Data Structures:
- Dynamic memory allocation and deallocation can incur additional overhead compared to static data structures.
- Dynamic data structures can be more complex to implement and maintain than static data structures.
- Improper handling of dynamic memory can lead to memory leaks, which can cause performance issues.
- The performance of dynamic data structures can be less predictable than static data structures, especially in real-time systems.
Examples of Dynamic Data Structures:
Linked List : Linked Lists are linear data structures where the elements are not stored in contiguous locations and every element is a separate object with a data part and address part. The elements are linked using pointers and addresses. Each element is known as a node. Due to the dynamicity and ease of insertions and deletions, they are preferred over the arrays.
Implementation:
#include <iostream>
using namespace std;
// defining a linked list
class LinkedList {
public:
int data;
LinkedList* next;
};
int main()
{
// creating a linked list
class LinkedList* node1 = new LinkedList();
node1->data = 1;
class LinkedList* node2 = new LinkedList();
node2->data = 2;
class LinkedList* node3 = new LinkedList();
node3->data = 3;
// linking all the nodes
node1->next = node2;
node2->next = node3;
node3->next = NULL;
// printing value of linked list
cout << node1->data << " " << node2->data << " "
<< node3->data << endl;
return 0;
}
public class LinkedList {
int data;
LinkedList next;
public static void main(String[] args)
{
// creating a linked list
LinkedList node1 = new LinkedList();
node1.data = 1;
LinkedList node2 = new LinkedList();
node2.data = 2;
LinkedList node3 = new LinkedList();
node3.data = 3;
// linking all the nodes
node1.next = node2;
node2.next = node3;
node3.next = null;
// printing value of linked list
System.out.println(node1.data + " " + node2.data
+ " " + node3.data);
}
}
// This code is contributed by Shivam
class LinkedList:
def __init__(self):
self.data = None
self.next = None
# creating a linked list
node1 = LinkedList()
node1.data = 1
node2 = LinkedList()
node2.data = 2
node3 = LinkedList()
node3.data = 3
# linking all the nodes
node1.next = node2
node2.next = node3
node3.next = None
# printing value of linked list
print(node1.data, node2.data, node3.data)
# This code is contributed by shivam
class LinkedList {
constructor(data) {
this.data = data;
this.next = null;
}
}
function main() {
// creating a linked list
let node1 = new LinkedList(1);
let node2 = new LinkedList(2);
let node3 = new LinkedList(3);
// linking all the nodes
node1.next = node2;
node2.next = node3;
node3.next = null;
// printing value of linked list
let currentNode = node1;
let output = "";
while (currentNode !== null) {
output += currentNode.data + " ";
currentNode = currentNode.next;
}
console.log(output.trim());
}
main();
Output
1 2 3
In the above code: A class LinkedList is defined with two members: data (an integer) and next (a pointer to the next node) and three nodes (node1, node2, node3) are created with data values of 1, 2, and 3 respectively. These nodes are then linked together to form a linked list: node1 points to node2, node2 points to node3, and node3 points to NULL, indicating the end of the list. Finally, the data values of the nodes are printed out, resulting in the output 1 2 3.
Static and Dynamic Data Structures
Data structures are the fundamental building blocks of computer programming. They determine how data is organized, stored, and manipulated within a software application. There are two main categories of data structures: static and dynamic. Static data structures have a fixed size and are allocated in memory during compile-time, while dynamic data structures can grow and shrink in size during runtime. This article will provide an overview of the key differences between static and dynamic data structures, their use cases, and the trade-offs to consider when choosing between them.
Table of Content
- What is Static Data structure?
- Features of Static Data Structures
- Advantages of Static Data Structures
- Disadvantages of Static Data Structures
- Examples of Static Data Structures
- What is Dynamic Data Structure?
- Features of Dynamic Data Structures
- Advantages of Dynamic Data Structures
- Disadvantages of Dynamic Data Structures
- Examples of Dynamic Data Structures
- Difference between Static and Dynamic Data Structure