$29
Recitation 3 Dynamic Memory Solution
Objectives
1. Dynamic memory
2. Freeing memory
3. Destructors
4. Linked Lists Introduction
5. Exercise
1. Dynamic Memory
What is static memory allocation?
When we declare variables, we are preparing the variables that will be used. This way a compiler can know that the variable is an important part of the program. So, the compiler allocates spaces to all these variables during compilation of the program. The variables allocated using static memory allocation will be stored in STACK.
But wait, what if the input is not known during compilation? Say, you want to pass input in the command line arguments (During runtime). The size of the input is not known beforehand during compilation.
The need for dynamic memory!!
We suffer in terms of inefficient storage use and lack or excess of slots to enter data. This is when dynamic memory play an important role. This method allows us to create storage blocks or room for variables during run time. Now there is no wastage. The variables allocated using dynamic memory allocation will be stored in HEAP.
Tip!
Fine dining restaurant vs drive thru
Most of the times we reserve space at a fine dining restaurant by calling them up or reserving online. (The space is wasted if you do not show up even after reserving). The restaurant can also not accommodate more than its capacity. (Static memory)
Consider McDonalds drive-thru, you don’t reserve space, you will somehow find a spot in the queue and just manage to grab your order. Here you are not reserving any seats beforehand, but still you can manage to get a meal. The restaurant can serve multiple
1
CSCI 2270 – Data Structures
Dynamic Memory
customers even if they have not reserved. (Dynamic memory)
Dynamic memory allocation example.
int main()
{
// Dynamic memory allocation
int *ptr1 = new int;
int *ptr2 = new int[10];
}
2. Freeing Memory
Once a programmer allocates a memory dynamically as shown in the previous section, it is the responsibility of the programmer to delete/free the memory which is created. If not deleted/freed, even though the variable/array is still not used, the memory will continue to be occupied. This causes memory leak.
To delete a variable ptr1allocated dynamically
delete ptr1;
To delete an array ptr2 allocated dynamically
delete [] ptr2;
3. Destructors
Destructor is a member function which destructs or deletes an object.
Destructor is automatically called when any object defined in the program goes out of scope. An object goes out of scope when:
1. A function ends.
2. The program ends.
2
CSCI 2270 – Data Structures
Dynamic Memory
3. A block containing local variables ends.
4. A delete operator is called.
Destructors have same name as the class preceded by tilde(~). They don’t take any argument and don’t return anything.
Example usage of destructors.
class DestructorExample
{
private:
char *s;
int size;
public:
DestructorExample(char *); // constructor
~DestructorExample(); // destructor
};
DestructorExample::DestructorExample(char *c)
{
size = strlen(c);
• = new char[size+1];
strcpy(s,c);
}
DestructorExample::~DestructorExample()
{
delete []s;
}
Questions:
1. What is the need of a custom destructor ?
2. In the exercise given in this recitation can you think of a situation (or in absence of which line) when there will be a memory leak ?
3
CSCI 2270 – Data Structures
Dynamic Memory
4. Linked List Introduction
A linked list is a data structure that stores a list, where each element in the list points to the next element.
Let’s elaborate:
Linked List is a sequence of links which contains items. Each link contains a connection to another link. Linked list is the second most-used data structure after array. Following are the important terms to understand the concept of Linked List.
• Node− Each Node of a linked list can store data and a link.
• Link− Each Node of a linked list contains a link to the next Node (unit of Linked List), often called ‘next’ in code.
• Linked List− A Linked List contains a connection link from the first link called Head. Every Link after the head points to another Node (unit of Linked List). The last node points to NULL.
In code, each node of the linked list will be represented by a class or struct. These will, at a minimum, contain two pieces of information - the data that node contains, and a pointer to the next node. Example code to create these is below:
class Node
{
public:
int data;
Node *next;
};
struct node
{
int data;
Node *next;
};
4
CSCI 2270 – Data Structures
Dynamic Memory
5. Exercise
Open your exercise file and complete the TODOs in the C++ program which does the following:
1. It will read from a text file. Each line of the file contains a number. Provide the file name as a command line argument. Number of lines in the file is not known.
2. Create an array dynamically of a capacity (say 10) and store each number as you read from the file.
3. If you exhaust the array but yet to reach end of file dynamically resize/double the array and keep on adding.
5
