Explain memory allocation and de-allocation for linked lists.
1 Answer

Linked list in memory is represented in tabular form where there are two main pointers:

START pointer refers to the first location of linked list as shown below:

enter image description here

Figure: Representation of linked list in memory

The above figure shows that nodes need not to be stored in sequence and using the next pointer, we can refer to next node of linked list. -1 represents the end of linked list that means this linked list holds two nodes. The highlighted empty rows represents the available memory locations. Now suppose if we want to add another node to current linked list then AVAIL pointer comes into picture.

AVAIL pointer: The computer maintains a list of free available memory cells and this free space is called the free pool. AVAIL pointer stores the address of first free space in memory cells.

enter image description here

For adding new node in linked, computer checks if there is free memory cell exists. If there are multiple cells free then computer checks the address of memory that AVAIL pointer holds. Now, new node is added to memory which was pointed by AVAIL previously.

enter image description here

The above figure shows a new entry in linked list wherein AVAIL pointer holds the address of new free memory cell. This is how memory is allocated for linked lists.

Now, if we want to delete a node from linked list then that free space occupied by node must be given back to free pool so that memory can be reused by other programs that need 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 the programs are falling short of memory space.

The operating system scans through all the memory cells and marks those cells that are being used by some program. Then it collects all the cells which are not being used and adds their address to the free pool, so that these cells can be reused by other programs. This process is called garbage collection.

Please log in to add an answer.