Deleting a specific node

What is wrong with my code? I get a NullPointerException when I try to

Page 1 of 1

3 Replies - 1541 Views - Last Post: 13 March 2007 - 05:26 PM Rate Topic: -----

#1 sublime   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 6
  • Joined: 27-November 06

Deleting a specific node

Posted 11 March 2007 - 01:57 AM

 public boolean delete( Node nodeToDelete ) {
		Node rover = head;
		Node bago = new Node();
		bago = head.next;
			
		while( ( rover.equals( nodeToDelete ) ) == false && ( rover != null ) ) {
			bago = bago.next;
			rover = rover.next;
		}
		if( rover == null )
			return false;
			
		else{
		
			if ( rover == head ) {
				head = head.next;
			} 
			
			else {
			
				if ( rover == tail ) {
					tail = bago;
				}
				
				bago.next = bago.next.next;
			}
			return true;
		}
	} // end method delete


Is This A Good Question/Topic? 0
  • +

Replies To: Deleting a specific node

#2 Programmist   User is offline

  • Refactorer in Chief
  • member icon

Reputation: 255
  • View blog
  • Posts: 1,843
  • Joined: 02-January 06

Re: Deleting a specific node

Posted 11 March 2007 - 07:22 AM

The first thing that jumps out at me is this:
while( ( rover.equals( nodeToDelete ) ) == false && ( rover != null ) )

You have the test for null second, which means that if rover is null then the call to rover.equals( ... ) will throw a NullPointerException. Here's an equivalent way do to this:

while ( ( rover != null ) && !rover.equals( nodeToDelete ) )

This post has been edited by alcdotcom: 11 March 2007 - 07:24 AM

Was This Post Helpful? 0
  • +
  • -

#3 keems21   User is offline

  • D.I.C Head
  • member icon

Reputation: 6
  • View blog
  • Posts: 185
  • Joined: 03-February 07

Re: Deleting a specific node

Posted 11 March 2007 - 03:34 PM

Ok, I think that I see your problem. The condition in the while loop that you're checking wrong is what is giving you an error. You set up two nodes, bago and rover.

You're starting rover at the first node in the chain, and bago at the second node in the chain. When you are going through your while loop, you are checking to see if rover equals null. When this is the case, bago will already have been null and you would have tried to do bago = bago.next (the code at the bottom of your while loop).

So here's the solution:

First of all, I don't see why you are using two nodes to transverse this chain. One will do, so just get rid of bago all together.

Start off with the while loop that aldotcom modified with this small modification:
while ( ( rover.next != null ) && !rover.next.equals( nodeToDelete ) )



Ok, what this holding your spot in the node you are currently in, but checking the next one in line to see if it is what you are looking for. If you find the node you are looking for, rover will be pointing to the node right before it. Here's a pretty lousy picture:
[0]--[1]--[2]--[3]--[4]--[5]--[6]--[7]--null
			   ^	^
	rover---|	 |---the node you want to remove


There are three conditions that you need to take into account when removing a node from a chain. Whether the node is in the first slot, a middle slot, or the last slot.

Here's how to deal with all of these:

1) The one problem with the given while loop is that it does not check to see if the first node is the one that you are looking for. Therefore, you need to take care of this before you enter the while loop. This is easily done with an if conditional:
if(head.equals(nodeToDelete)
{
  head = head.next;
  return true;
}


Nice and simple, all you do is move the pointer from the first node to the second. Now, everytime you call for the head node, it will return the second one in the chain. (lousy picture):
[0]--[1]--[2]--[3]--[4]--[5]--[6]--[7]--null
		^
		 |---head



2) Now, if the node you're looking at removing is in the middle, this is nice and easy. Remember, after your while loop, your chain looks like this:
[0]--[1]--[2]--[3]--[4]--[5]--[6]--[7]--null
			   ^	^
	rover---|	 |---the node you want to remove


So, if rover is pointing at node 2, and you want to remove node 3, what you do is
rover.next = rover.next.next;



Afterwards, the chain looks something like this:
[0]--[1]--[2]	[3]--[4]--[5]--[6]--[7]--null
			   |			 ^ 
			   |________|


In other words, node #2.next = node #4. Node #3 is completely cut out and unaccessable.


3) Finally, if the node is at the end of the chain. This occurs when the while loop terminates, (in this instance) node #7 is equal to nodeToDelete. This means that rover will be pointing at node #6, which is the second to last node in the chain. To see if this is the case, use the following if conditional:
if(rover.next.next = null)
{
rover.next = null;
}



This code will cut off the last node from the chain.

So, here's what you want, all of the code put together.
public boolean delete( Node nodeToDelete ) 
{
  Node rover = head;
			
  if(rover.equals(nodeToDelete) //if the head node is the one you want to delete
  {
	head = head.next; //move the head node to the next node
	return true;  
  }

  while( ( rover.next != null && rover.next.equals(nodeToDelete)
  {
	rover = rover.next;	
  }
  
  if(rover.next.next == null) //if the node to remove is the last node
	rover.next = null
  else 
	if(rover.next == null) //this means that nodeToDelete was never found
	  return false;
	else  //the node to remove occurs somewhere else in the loop
	  rover.next = rover.next.next;
	  
  return true;
} // end method delete



I hope that this works. I have nothing to test it on becaues I don't have enough code. Anyway, as long as you understand what is being done here, I have no problem with you using this code.

I hope that this helps.

This post has been edited by keems21: 11 March 2007 - 03:37 PM

Was This Post Helpful? 0
  • +
  • -

#4 sublime   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 6
  • Joined: 27-November 06

Re: Deleting a specific node

Posted 13 March 2007 - 05:26 PM

thanks a lot! it really helped! :D
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1