Tag Archives: ISC 2014

Append a node in Linklist

ISC Computer Science

Question 13.

A linked list is formed from the object of the class:

class Node{
     int number;
     Node nextNode;
}

Write an Algorithm OR a Method to add a node at the end of an existing linked list.

The method declaration is as follows:

void addnode( Node start, int num )

Java implementation of appending a node in linked list is as follows:

public void addNode( Node start, int num ){
	try{
		Node newNode = new Node();
		newNode.number = num;
		newNode.nextNode = null;
		if( start == null ){
			start = newNode;
		}else{
			for( Node temp = start; temp.next!=null; temp=temp.next );
			temp.next = newNode;	
		}
	}catch( OutOfMemoryError e ){
		start = null ;
		System.out.println("Overflow");
		System.exit( 1 );
	}
}

Notice the use of try-catch to detect failure of creation of new node. It’s necessary to assign start to null inside the catch block because no memory is free when the control reaches the catch block, not even for displaying a message. When we allocate memory using the operator new there is possibility that it would fail if there is no heap memory left. In that case JVM would throw OutOfMemoryError. This is actually our overflow condition. Notice that in the catch block we are assigning top to null. This is important because when all memory is exhausted we cannot do anything, not even display a message because println() function also requires some memory to execute. Now, since all the memory is exhausted it is obvious that we cannot continue. We must free some memory so that we can recover from memory crises and take some alternative action. As soon as we assign null to top. The block of memory which top was referring to would be eligible for garbage collection. This implies that JVM would free that block of memory. As soon as this happens there would be no one referring to the second node now because the next part of the fist node is now gone. Thus, the memory allocated to the second node would also be free. This would go on till all the memory occupied by all the nodes is free.