Share
Explore BrainMass

Live Nodes, Garbage Collection in Java

class Node
{
int value;
Node next;
Node(int value, Node next)
{
this.value = value;
this.next = next;
}
Node(int value)
{
this.value = value;
}
}
class List {
Node start;
void inverse()
{
Node p = null;
for (Node q = start; q != null; q = q.next)
{
p = new Node(q.value,p);
}
start = p;
}

Please provide answers to the following questions based on above Java classes.

1. For a list with n Nodes, what is the maximum number of nodes that are "live" (i.e., accessible from a "root set" of variables) during the method inverse(), and when does this maximum occur?

2. Give a simple modification of the method inverse() above that minimizes the number of "live" nodes that are necessary for the method to work, so that any item that will not be used later can be immediately reclaimed as "garbage."

3. Suppose there is "heap space" for 10,000 nodes as Java objects and a list of 7,000 nodes which are stored in that heap. When method inverse() with the modification in (2) is applied to that list, at what stages of the computation does garbage collection take place?

Solution Preview

1. For a list with n Nodes, the maximum number of nodes that will be live during the method inverse(), will be 2*n, and this will happen after the for loop is executed completely but "start = p;" is not.

Before the for loop,
root set of variables = {start, p}
total live nodes = {n + 0} = n
total nodes available for garbage collection = 0

Inside the for loop,
root set of variables = {start, q, p}
total live nodes = {n + i} where i = 1 to n
total nodes available for garbage collection = 0

Since start and q initially point to same list; even though number of live nodes reachable via q reduces by 1 in each iteration of for loop, it does not really make any difference to the liveness of nodes in the original list (as they are all the while reachable via variable start, inside the for loop).

As inverse list is being built by adding a new node to list p in each iteration, it adds to the count of live nodes by 1 in each iteration.

Just after the for loop,
root set of variables = {start, p} (q was a local variable inside for loop.)
total live nodes = {n + n} = 2*n (A copy of original list is made ...

Solution Summary

A detailed step-by-step explanation is provided. An excerpt is given below.

Before the for loop,
root set of variables = {start, p}
total live nodes = {n + 0} = n
total nodes available for garbage collection = 0

$2.19