Dynamic memory allocation
Introduction:
Dynamic memory allocation is a fundamental concept in data structures
and programming. It allows programs to allocate memory at runtime,
providing flexibility and efficiency when working with data structures of
varying sizes.
Understanding Dynamic Memory Allocation
In most programming languages, including C++, memory can be
classified into two categories: stack memory and heap memory. Local
variables and function calls are stored in the stack memory, whereas the
more adaptable heap memory can be allocated and released at runtime.
The process of allocating and releasing memory from the heap is known
as dynamic memory allocation. It allows the programmer to manage
memory explicitly, providing the ability to create data structures of
varying sizes and adjust memory requirements dynamically.
Dynamic Memory Allocation Techniques:
In most programming languages, dynamic memory allocation is achieved
through dedicated functions provided by the language or standard library.
Let's explore three commonly used techniques:
1. malloc:
The malloc (memory allocation) function is used to allocate a specified
number of bytes in memory. When memory is allocated successfully, it
returns a pointer to that block, otherwise it returns NULL. By dividing the
necessary number of elements by each one's individual size, the block's
size is calculated. For example:
1. int* ptr = (int*) malloc(5 * sizeof(int)); // Allocates memory for 5 integers
2. calloc:
Resizing a previously allocated memory block is possible with the realloc
(reallocate) function. It accepts two arguments: the new size in bytes and
a pointer to the current block. Upon successful reallocation, a pointer to
the newly allocated memory is returned. If not, NULL is returned. Here's
an example:
1. int* ptr = (int*) calloc(5, sizeof(int)); // Allocates memory for an array of
5 integers
3. realloc:
The realloc (reallocate) function allows you to resize a previously allocated
memory block. It takes a pointer to the existing block and the new size in
bytes as arguments. If reallocation is successful, it returns a pointer to the
reallocated memory. Otherwise, it returns NULL. Example usage:
1. int* ptr = (int*) malloc(5 * sizeof(int)); // Allocates memory for 5 integers
2. ptr = (int*) realloc(ptr, 10 * sizeof(int)); // Reallocates memory for 10 inte
gers
Dynamic Memory Allocation in C++
C++ provides mechanisms for dynamic memory allocation using the new
and delete operators, which are improvements over the malloc() and
free() functions from C.
o Allocating Memory: new Operator
The new operator in C++ is used to allocate memory on-demand. A
pointer to the allocated memory is returned along with the memory
allocation of the given type. Here's the syntax:
1. type* pointerVariable = new type;
For example, to allocate memory for an integer dynamically:
1. int* dynamicInt = new int;
The new operator allocates memory on the heap, which is a region of memory used for
dynamic memory allocation. It ensures that the allocated memory persists until explicitly
deallocated.
o Freeing Memory: delete Operator
Once we are done with the dynamically allocated memory, it is essential to free it to avoid
memory leaks. Memory that has been allocated with the new operator is deallocated using the
delete operator. Here's the syntax:
1. delete pointerVariable;
For example, to deallocate the memory for the dynamically allocated integer:
1. delete dynamicInt;
The delete operator releases the memory back to the system, making it available for future
allocations. It is crucial to ensure that every allocation made using new is accompanied by an
appropriate delete to prevent memory leaks.
Common Data Structures Utilizing Dynamic Memory Allocation:
Several data structures benefit from dynamic memory allocation due to their variable size and
dynamic nature. Here are a few examples:
Arrays:
Dynamic memory allocation allows arrays to be created with a size determined at runtime. It
enables the creation of resizable arrays, commonly known as dynamic arrays or vectors,
which can grow or shrink as needed.
Linked Lists:
Linked lists are data structures made up of nodes, where each node has
information and a link to the node after it. The size of the linked list can vary
based on the number of nodes. Dynamic memory allocation is crucial for creating
and managing nodes efficiently. When a new node needs to be added to the
linked list, memory is dynamically allocated for the new node, and the
appropriate pointers are updated.
Trees:
The hierarchical data structures known as trees are made up of nodes and edges. Binary trees,
balanced search trees like AVL or Red-Black trees, and other tree structures require dynamic
memory allocation to create and manage nodes. The dynamic nature of trees, where nodes
can be inserted or removed, necessitates the allocation and deallocation of memory during
runtime.
Graphs:
Graphs are structures composed of vertices (nodes) connected by edges. Graphs can be
dynamic, with vertices and edges added or removed as needed. Dynamic memory allocation
allows for efficient memory management when creating and managing vertices and edges
dynamically.
Dynamic Memory Allocation and Data Structures
Dynamic memory allocation is especially useful when working with data
structures that have varying sizes or require dynamic resizing. Let's take a look
at an example of dynamically allocating memory for a linked list:
#include <iostream>
using namespace std;
struct Node {
int data;
Node* next;
};
Node* createNode(int value) {
Node* newNode = new Node;
newNode->data = value;
newNode->next = nullptr;
return newNode;
}
void appendNode(Node*& head, int value) {
Node* newNode = createNode(value);
if (head == nullptr) {
head = newNode;
} else {
Node* current = head;
while (current->next != nullptr) {
current = current->next;
}
current->next = newNode;
}
}
1.
int main() {
Node* myList = nullptr;
// Append nodes to the linked list
appendNode(myList, 42);
appendNode(myList, 27);
appendNode(myList, 10);
// Traverse and print the linked list
Node* current = myList;
while (current != nullptr) {
cout << current->data << " ";
current = current->next;
}
// Deallocate the linked list
while (myList != nullptr) {
Node* temp = myList;
myList = myList->next;
delete temp;
}
return 0;
}
Explanation:
o This program demonstrates the implementation of a singly linked list in
C++.
o It defines a struct called The linked list node is represented by this struct.
It has two members: next, a pointer to the following node in the list,
and data, which contains the value kept in the node.
o An integer value is required as an argument for the
function createNode(), which is defined in the programme.
o This function dynamically allocates memory for a new node using the new
operator, initializes its data member with the given value, and sets its next
pointer to nullptr. A pointer to the just generated node is then returned.
o There is another defined function named appendNode(). This function
accepts two inputs: an integer number and a reference to the linked list's
head pointer (Node*& head).
o It creates a new node by calling the createNode() function with the given
value. If the head pointer is nullptr, indicating an empty list, the head
pointer is updated to point to the newly created node.
o Otherwise, it traverses the linked list to find the last node and appends the
new node to the end by updating the next pointer of the last node.
o In the main function, a pointer myList is initialized as nullptr,
representing an empty linked list.
o The program then calls the appendNode() function multiple times to
append nodes with values 42, 27, and 10 to the linked list.
o The programme then iterates across the linked list, printing each node's
data. A while loop is used to repeatedly iterate through the list after
initialising a pointer to the list's head.
o During each iteration, it prints the data of the current node and moves the
current to the next node by updating its next pointer.
o The programme then releases the RAM that the linked list had taken up. It
uses a while loop to traverse the list, deallocates the memory for each
node by using the delete operator, and updates the myList pointer to the
next node before deleting the current node.
Program Output:
The Need for Dynamic Memory Allocation in Data Structures:
Data structures such as linked lists, trees, and graphs often require
variable amounts of memory that cannot be determined at compile-time.
Dynamic memory allocation provides the flexibility to allocate memory
based on the size and complexity of the data structure. For example, in a
linked list, each node may have a different size, and dynamic memory
allocation allows for efficient memory management by allocating memory
for nodes as they are created.
Similarly, trees and graphs can have a varying number of nodes or
vertices, and dynamic memory allocation allows for their efficient creation
and management.
Benefits of Dynamic Memory Allocation in Data Structures
Dynamic memory allocation in data structures offers several key benefits:
o Efficient Memory Utilization: Dynamic memory allocation enables us to
allocate memory as needed. It eliminates the fixed-size limitations of
static memory allocation, allowing data structures to utilize memory more
efficiently. Data structures can grow or shrink dynamically based on the
requirements, ensuring optimal memory usage.
o Flexibility: With dynamic memory allocation, data structures can adapt
to changing requirements during program execution. It enables us to set
aside memory for a certain job and release it when it is finished. This
flexibility is particularly useful for data structures that involve frequent
insertions, deletions, or resizing of elements.
o Reduced Memory Waste: Dynamic memory allocation allows us to only
allocate memory when necessary, in contrast to static memory allocation,
which reserves memory regardless of usage. This helps reduce memory
waste significantly. Data structures can allocate memory dynamically as
elements are added and deallocate it when elements are removed,
resulting in efficient memory management.
Best Practices for Dynamic Memory Allocation:
To ensure proper utilization of dynamic memory allocation, it is essential
to follow these best practices:
Error Handling:
Always check for allocation failures to handle scenarios where the
operating system cannot allocate the requested memory. When using the
'new' operator, it is important to check if the returned pointer is valid or
null before accessing the allocated memory.
Memory Leakage Prevention:
Make sure to use the 'delete' operator to properly deallocate all dynamically allocated
memory. Failure to deallocate memory can result in memory leaks, when memory is
allocated but never released, reducing the amount of memory resources that are available.
Proper Resource Deallocation:
When working with complex data structures, ensure that all allocated memory is deallocated
correctly. In structures like linked lists, trees, or graphs, deallocation may involve recursively
deallocating memory for each node or vertex and its associated components.
Conclusion:
The concept of dynamic memory allocation, which enables programmes to allocate and
deallocate memory dynamically at runtime, is fundamental in data structures. It provides
flexibility in managing memory resources and enables efficient memory utilization.
Programmes can allocate memory for data structures like arrays, linked lists, trees, and
graphs based on their individual requirements thanks to dynamic memory allocation. It
eliminates the limitations of static memory allocation, where the size of data structures must
be known at compile-time.
One of the key advantages of dynamic memory allocation is the ability to allocate memory as
needed, conserving resources and preventing wastage. It allows programs to adapt to
changing requirements and handle variable-sized data structures efficiently. This adaptability
is especially useful in situations when the size of the data structure is unpredictable or subject
to change as the programme is being run.
Dynamic memory allocation also plays a vital role in avoiding memory-related issues such as
stack overflow or insufficient memory. By allocating memory from the heap, programs can
utilize a larger pool of memory compared to the limited stack space. This enables the
handling of large data structures and prevents program crashes due to memory constraints.
However, dynamic memory allocation introduces challenges such as memory
leaks and fragmentation. Memory loss over time results from memory leaks,
which happen when allocated memory is not properly deallocated. Memory
fragmentation is the loss of contiguous memory space as a result of memory
blocks becoming dispersed and broken apart.
To mitigate these challenges, proper memory management practices must be
followed. This includes deallocating memory when it is no longer needed, using
appropriate data structures and algorithms to minimize fragmentation, and
employing techniques such as garbage collection to automatically deallocate
unused memory.
