chap lists and arrays revisited figure garbage cycle example all memory elements in the cycle have non-zero reference counts because each element has one pointer to iteven though the entire cycle is garbage the memory objects are linked together without cyclessuch as the unix file system where files can only be organized as dag another approach to garbage collection is the mark/sweep strategy hereeach memory object needs only single mark bit rather than reference counter field when free store is exhausteda separate garbage collection phase takes place as follows clear all mark bits perform depth-first search (dfsfollowing pointers from each variable on the system' list of variables each memory element encountered during the dfs has its mark bit turned on "sweepis made through the memory poolvisiting all elements unmarked elements are considered garbage and placed in free store the advantages of the mark/sweep approach are that it needs less space than is necessary for reference countsand it works for cycles howeverthere is major disadvantage this is "hiddenspace requirement needed to do the processing dfs is recursive algorithmeither it must be implemented recursivelyin which case the compiler' runtime system maintains stackor else the memory manager can maintain its own stack what happens if all memory is contained in single linked listthen the depth of the recursion (or the size of the stackis the number of memory cellsunfortunatelythe space for the dfs stack must be available at the worst conceivable timethat iswhen free memory has been exhausted fortunatelya clever technique allows dfs to be performed without requiring additional space for stack insteadthe structure being traversed is used to hold the stack at each step deeper into the traversalinstead of storing pointer on the stackwe "borrowthe pointer being followed this pointer is set to point back to the node we just came from in the previous stepas illustrated by figure each borrowed pointer stores an additional bit to tell us whether we came down the left branch or the right branch of the link node being pointed to at any given instant we have passed down only one path from the rootand we can follow the trail of pointers back up as we return (equivalent to popping the recursion stack)we set the pointer back to its original position so as to return the structure to its