Dynamic Memory Allocation in Data Structures
"Learn about dynamic memory allocation in data structures, including pointers, allocators, and the use of malloc, new, and free. Understand the differences between C and C++ in handling dynamic memory. Explore allocation methods with examples using malloc and new. Enhance your understanding of pointers and arrays in memory allocation techniques."
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
EECE.3220 Data Structures Instructor: Dr. Michael Geiger Fall 2019 Lecture 11: Dynamic allocation
Announcements/reminders HW 1 due 9/30 Exam 1: Thursday, 10/3, 2-4 PM, Ball 328 Posted form to complete if you need an alternate time for the exam Program 2 to be posted next week Today s lecture Dynamic allocation 6/25/2025 2 Data Structures: Lecture 11
Refresher on pointers Allocators (malloc, new) return pointer to allocated space Pointer: address of another object Can get address of existing object using & Can get value of existing pointer using * Pointer declaration: <base type>* <pointer name> Base type determines how reference is interpreted Be careful when declaring multiple pointers Be sure to initialize pointer before use 6/25/2025 3 Data Structures: Lecture 11
Refresher on pointers, pt. 2 Can assign pointers to one another; e.g. int x, *xp, *ip; xp = &x; ip = xp; Array/pointer duality Array name is pointer to first element Can dereference array name (*arr) Can treat pointers like arrays (ptr[i]) 6/25/2025 4 Data Structures: Lecture 11
Dynamic memory allocation Up until now, allocated memory statically Assumed we knew data size at compile time What if data size is input-dependent and unknown until run time? In C, dynamic memory allocation handled through malloc and free In C++, we use newanddelete Allocator (new) returns pointer to allocated space 6/25/2025 5 Data Structures: Lecture 11
Allocation with new In C, malloc()allocates space on heap malloc(sizeof(int))allocates space for 1 integer malloc(20*sizeof(int))allocates an array of 20 integers Both calls return pointer to first byte of element In C++, we use new new int allocates space for 1 integer new int[20] allocates an array of 20 integers As with malloc(), newreturns pointer to first byte Directly initialize with value in parentheses e.g. new int(3) 6/25/2025 6 Data Structures: Lecture 11
Example int *iPtr; iPtr = new int; double *dPtr; dPtr = new double[20]; // 160 bytes allocated // dPtr points to 1st byte ? iPtr 4 bytes allocated for single int variable // 4 bytes are allocated // iPtr points to 1st byte heap ? ? ? dPtr ? 160 bytes allocated for 20 double variables ? 6/25/2025 7 Data Structures: Lecture 11
Dynamic allocation example int main() { int *iPtr, *jPtr, i; iPtr = new int; jPtr = new int(3); double *dPtr; dPtr = new double[6]; *iPtr = 7; cout << *iPtr << ',' << *jPtr << endl; for(i=0; i<6; i++) dPtr[i] = 5; for(i=0; i<6; i++) cout << (*dPtr)++ << ' '; cout << endl; for(i=0; i<6; i++) cout << dPtr[i] << ' '; return 0; } OUTPUT 7, 3 5 6 7 8 9 10 11 5 5 5 5 5 Why? 6/25/2025 8 Data Structures: Lecture 11
Dynamically allocated objects May want to dynamically allocate objects Ex. array of Points where size is unknown at compile time Point *pointArray; int numPoints; cin >> numPoints; pointArray = new Point[numPoints]; Ex. linked list data structure to add an element to the list, must allocate new element class linkedList { private: int elem; linkedList *next; public: linkedList(); linkedList(int val); void addElement(int i); ... } void linkedList::addElement(int i) { next = new linkedList(i); } 6/25/2025 9 Data Structures: Lecture 11
Referencing objects through pointers Recall: use dot operator (.) to reference members of object, e.g: Point p1; p1.setX(2); With pointers, use -> linkedList *list1 = new linkedList; list1->addElement(2); 6/25/2025 10 Data Structures: Lecture 11
Deallocation with delete Space allocated using new should be freed In C, we used free() In C++, we use delete You should only use delete to free memory allocated by new Any other use will result in an error 6/25/2025 11 Data Structures: Lecture 11
delete example int *ptr; ptr = new int (100); ptr 100 delete ptr; //free the memory ptr ? delete frees space on heap ... ... but ptr still points to same address! Solution: assign freed pointers to NULL: ptr = NULL; 6/25/2025 12 Data Structures: Lecture 11
Example: delete with arrays double *dptr; const int SIZE = 10; dptr = new double[SIZE]; //80 bytes for(int i=0; i<SIZE; ++i) cin >> dptr[i]; fun1(dptr, SIZE); // pass array to fun1 delete [] dptr; //free all 10 elements dptr = NULL; 6/25/2025 13 Data Structures: Lecture 11
Final notes Next time Vectors Reminders: HW 1 due 9/30 Exam 1: Thursday, 10/3, 2-4 PM, Ball 328 Posted form to complete if you need an alternate time for the exam Program 2 to be posted next week 6/25/2025 14 Data Structures: Lecture 11
