the java virtual machine definition requires that the memory heap be able to quickly allocate memory for new objectsbut it does not specify the data structure that we should use to do this one popular method is to keep contiguous "holesof available free memory in doubly linked listcalled the free list the links joining these holes are stored inside the holes themselvessince their memory is not being used as memory is allocated and deallocatedthe collection of holes in the free lists changeswith the unused memory being separated into disjoint holes divided by blocks of used memory this separation of unused memory into separate holes is known as fragmentation of coursewe would like to minimize fragmentation as much as possible there are two kinds of fragmentation that can occur internal fragmentation occurs when portion of an allocated memory block is not actually used for examplea program may request an array of size but only use the first cells of this array there isn' much that run-time environment can do to reduce internal fragmentation external fragmentationon the other handoccurs when the there is significant amount of unused memory between several contiguous blocks of allocated memory since the run-time environment has control over where to allocate memory when it is requested (for examplewhen the new keyword is used in java)the run-time environment should allocate memory in way that tries to reduce external fragmentation as much as reasonably possible several heuristics have been suggested for allocating memory from the heap so as to minimize external fragmentation the best-fit algorithm searches the entire free list to find the hole whose size is closest to the amount of memory being requested the first-fit algorithm searches from the beginning of the free list for the first hole that is large enough the next-fit algorithm is similarin that it also searches the free list for the first hole that is large enoughbut it begins its search from where it left off previouslyviewing the free list as circularly linked list (section the worst-fit algorithm searches the free list to find the largest hole of available memorywhich might be done faster than search of the entire free list if this list were maintained as priority queue (in each algorithmthe requested amount of memory is subtracted from the chosen memory hole and the leftover part of that hole is returned to the free list although it might sound good at firstthe best-fit algorithm tends to produce the worst external fragmentationsince the leftover parts of the chosen holes tend to be small the first-fit algorithm is fastbut it tends to produce lot of external