Memory Allocation and Deallocation for a Linked List

MEMORY ALLOCATION AND DEALLOCATION FOR A LINKED LIST

We have seen how a linked list is represented in memory. If we want to add a node to an already existing linked list, we will first find free space in the memory and then use it to store the information. For example, consider the linked list given in Figures 11.5 (a) and (b). The linked list contains the roll numbers of the students, marks obtained by them in Biology, and finally a NEXT field which stores the address of the next node in sequence. Now, if a new student joins the class and is asked to appear for the same test that the other students had already taken, then the new student's marks should also be recorded in the linked list. For this purpose, we will find a free space and store the information there. In Figure. 11.5(a), the grey shaded portions show free spaces, thus we have foure locations of memory available and we can use any one of them to store our data.

Now the question is who will take care of the memory- which part of the memory is available and which part is occupied. When we delete a node from a linked list then who will change the status of the memory occupied by it from occupied to available. The answer is the operating system. Discussing the mechanism of how the operating system does all this is out of the scope of this book. So, for the sake of simplicity, we can say that the computer takes care of this without any intervention from the user or the programmer. As a programmer, you just have to take care of the code to perform insertions and deletions in the list.

However, to have an overview of the mechanism, we will briefly discuss the basic concept. The computer maintains a list of all free memory cells. This list of available space is called the free pool.

We have seen that every linked list has a pointer variable START which stores the address of the first node of the list. Likewise, for the free pool (which is a linked list of all free memory cells), we have a pointer variable AVAIL which stores the address of the first free space. Let us revisit the memory representation of the linked list storing the students' marks in Biology. We have another pointer variable AVAIL here which stores the address of the first free space.

Now, when a new student's record has to be added, the memory address pointed by AVAIL is taken and used to store the desired information. After the insertion, the address of the next available free space is stored in AVAIL. For example, in Figure 11.6, when the first free memory space is utilized for inserting the new node, the AVAIL pointer will be set to contain address 6.

This was all about inserting a new node in an already existing linked list. Now we will talk about deleting a node or the entire linked list. When we delete a particular node from an existing linked list or delete the entire linked list, the space occupied by it must be given back to the free pool so that the memory can be reused by some other program that needs memory space.

The operating system does this task of adding the freed memory to the free pool. The operating system will perform this operation whenever it finds the CPU idle or whenever programs fall short of memory. The operating system scans through all the memory cells and marks the cells being used by some other programs. Then, it collects all those cells which are not being used and adds their address to the free pool so that they can be reused by the programs. This process is called garbage collection.