Most often we face situations in programming where the data is dynamic in nature. That is, the number of data items keep changing during execution of the program. For example, consider a program for processing the list of customers of a corporation. The list grows when names are added and shrinks when names are deleted. When list grows we need to allocate more memory space to the list to accommodate additional data items. Such situations can be handled more easily and effectively by using what is known as dynamic data structures in conjunction with dynamic memory allocation management techniques.
Introduction
Dynamic data structures provide flexibility in adding, deleting or rearranging data items at run time. Dynamic memory management techniques permit us to allocate additional memory space or to release unwanted space at run time, thus, optimizing the use of storage space.
This chapter discusses the concept of linked lists, one of the basic types of dynamic data structures. Before we take up linked lists, we shall briefly introduce the dynamic storage management functions that are available in C. These functions would be extensively used in processing linked lists.
Dynamic Memory Allocation
C language requires the number of elements in an array to be specified at compile time. But we may not be able to do SO always. Our initial judgement of size, if it is wrong, may cause failure of the program or wastage of memory space.
Many languages permit a programmer to specify an array’s size at run time. Such languages have the ability to calculate and assign, during execution, the memory space required by the variables in a program. Process of allocating memory at run time is known as dynamic memory allocation.
Although C does not inherently have this facility, there are four library routines known as “memory management functions” that can be used for allocating and freeing memory during program execution.
They are listed in Table. These functions help us build complex application programs that use the available memory intelligently.
Memory Allocation Functions
| Function | Task |
| malloc | Allocates request size of bytes and returns a pointer to the first byte of the allocated space. |
| calloc | Allocates space for an array of elements, initializes them to zero and then returns a pointer to the memory. |
| free | Frees previously allocated space. |
| realloc | Modifies the size of previously allocated space. |
Memory Allocation Process
Before we discuss these functions, let us look at the memory allocation process associated with a C program. Figure shows the conceptual view of storage of a C program in memory.
The program instructions and global and static variables are stored in a region known as permanent storage area and the local variables are stored in another area called stack. The memory space that is located between these two regions is available for dynamic allocation during execution of the program.
This free memory region is called the heap. The size of the heap keeps changing when program is executed due to creation and death of variables that are local to functions and blocks.
Therefore, it is possible to encounter memory “overflow” during dynamic allocation process. In such situations, the memory allocation functions mentioned above return a NULL pointer (when they fail to locate enough memory requested).
