In this blog, we are going to learn about the Memory Allocation, Garbage Collection, Overflow and Underflow in Linked List Data Structures.

Memory Allocation

Together with the linked list, a special list is maintained which consists of unused memory cells.

• This list has its own pointer.
• This list is called List of available space or Free-storage list or Free pool.

Free Pool

Linked list with free pool or list of Available space.

Garbage Collection

• Garbage collection is a technique of collecting all the deleted spaces or unused spaces in memory.
• The OS of a computer may periodically collect all the deleted space onto the free-storage list.
• Garbage collection may take place when there is only some minimum amount of space or no space is left in free storage list.
• Garbage collection is invisible to the programmer.

Principles Of Garbage Collection

The basic principles of garbage collection are:

• Find data objects in a program that cannot be accessed in the future.
• Reclaim the resources used by those objects.

Garbage Collection Process

Garbage collection takes place in two steps.

1. The computer runs through all lists tagging those cells which are currently in use.
2. Then computer runs through the memory, collecting all the untagged spaces onto the free storage list.

Overflow and Underflow

1. Overflow: When a new data are to be inserted into a data structure but there is no available space i.e. the free storage list is empty.

   • Overflow occurs when AVAIL = NULL, and we want insert an element.
   • Overflow can be handled by printing the ‘OVERFLOW’ message and/or by adding space to the underlying data structure.

2. Underflow: When a data item is to be deleted from an empty data structure.

   • Underflow occurs when START = NULL, and we want to delete an element.
   • Underflow can be handled by printing the ‘UNDERFLOW’ message.