Live Nodes, Garbage Collection in Java
Not what you're looking for?
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?
Purchase this Solution
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
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 ...
Purchase this Solution
Free BrainMass Quizzes
C# variables and classes
This quiz contains questions about C# classes and variables.
Basic Networking Questions
This quiz consists of some basic networking questions.
Inserting and deleting in a linked list
This quiz tests your understanding of how to insert and delete elements in a linked list. Understanding of the use of linked lists, and the related performance aspects, is an important fundamental skill of computer science data structures.
Basic Computer Terms
We use many basic terms like bit, pixel in our usual conversations about computers. Are we aware of what these mean? This little quiz is an attempt towards discovering that.
Basic UNIX commands
Use this quiz to check your knowledge of a few common UNIX commands. The quiz covers some of the most essential UNIX commands and their basic usage. If you can pass this quiz then you are clearly on your way to becoming an effective UNIX command line user.