problem in making metthod

Question

jemz -1 Master Poster

14 Years Ago

hello can you help me i don't know how to make this method remove(Node n),in SinglyLinkedList can anyone give a hand on this..
thank you in advance.hoping for your positive responds...

public class SinglyLinkedList
{
	
	private Node head; 
	private Node tail;
	private int size = 0;
	
	public Node add(Node n)
	{		
		if(isEmpty())
		{
			//if list is empty new node n should be the tail and head
			head = n;
			tail = head;
		}
		else
		{
			
			tail.next = n;			
			tail = n;
		}
		
		size++;
		return n;
	}
	public Node addFirst(Node n)
	{
		if(isEmpty())
		{
			head = n;
			tail = n;
		}
		else		
		{
			n.next = head;
			head = n;
		}
		return n;
	}
	
	public Node getFirst()
	{
		return head;
	}
		
	public Node getLast()
	{
		return tail;
	}

	
	public boolean isEmpty()
	{
		return head == null;
	}
	
	public int getSize()
	{
		size++;
		return size;
	}
	
	
	public Node insertAfter(Node n, Node target)	 
   {
	  
	   if (head==null)
		 {
		   head=n;
	       tail=n;
		 }
		else
		 {
		   n.next=target.next;
			target.next=n;
		 }	
		   return n;
  }			 
			      
 public Node remove(Node n)
 {
 		
 }
  
  
  	 	
	public static void main(String[] args)
	{
		SinglyLinkedList list = new SinglyLinkedList();
		
		
		for(int i=0;i<10;i++)
		{
			Node n = new Node();
			n.value = "jemzgimz" + (i + 1);		
			list.add(n);
		
		}
		// insertAfter
	     Node x = new Node();
		 x.value = "jemz";
		 Node target = list.getFirst();
		 list.insertAfter(x,target);
		 
		 System.out.println("The size of list: " + list.size);
		 
		 Node s = list.getLast();
	
	    

	 
		Node n = list.getFirst();	
	
		while(n!= null)
		{
			System.out.println(n.value);
			n = n.next;
		
		}
	}
}

java

Edited 14 Years Ago by jemz because: n/a

3 Contributors
10 Replies
268 Views
4 Days Discussion Span
Latest Post 14 Years Ago Latest Post by jemz

tong1 22 Posting Whiz

14 Years Ago

skyzer, Is the n an instance of Node or that of String?
I think some things in jemz declare of the method "remove" should be altered as :
public boolean remove(String n) {...}
provided the definition of the class Node is wirtten as :

class Node {
String item;
Node next;
}

tong1 22 Posting Whiz

14 Years Ago

jemz, I have comments on your program:

(1) In your program, the declaration of some methods should be changed.
For example, public Node addFirst(Node n) // in line 26
It does not make sense if you have to return a node after successfully inserting the new node.So, when you are going to insert a new node n into the list the return type should altered with boolean or void.

After 37 line you should insert a code:
Size++; .// since you have inserted a new code before the head.

tong1 22 Posting Whiz

14 Years Ago

jemz, when removing a node from a list one has to specify which node is going to be deleted. For example, if you are going to delete a node where the data member value is a specific string, e.g. "wonderful". You may have to do a search for the specific string in the list. In this case the signature of the method should be:
Node remove(String s) {...} rather than Node remove(Node n){....} unless you just want to delete a specific node n.
Anyway, I write the following two methods to delete 1. the head or 2. the tail node for your reference. Provided that Node definition is:

class Node{
String value;
Node next;
}

public Node removeFirst(){// delete the head node of the list
	if (isEmpty()) // if the list is empty
	return null;   // return null, i.e. no node can be returned
	else {  // if the list is not empty
	Node p = head; // make node p to represent the head node
	head = head.next; // after delete the head the next node of the original head will be the new head
	return p;  // return the previous head represented by p
	}
}
	
public Node removeLast(){ // delete the tail of the list
	if (isEmpty()) // if the list is empty
	return null;   // return no node
	else { // if the list is not empty
	Node p = head; // make p to represent the original head
	while(p.next !=tail) //when the next node of the p is not the tail node
	p = p.next; // make the node p to represent its next node
    /* after the while loop is executed, the p will be the node just before the tail node */
	Node pp = tail; //make node pp represent the tail
	tail=p; // the node p becomes the new tail
	tail.next=null; // the next of the new tail should be null
	return pp; // return the original tail represented by pp
}

Edited 14 Years Ago by tong1 because: n/a

Reply to this topic

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.

skyzer 0 Light Poster · Answer 1 · 2010-08-13T17:39:04+00:00

/**
 * Delete a specified item from the list, if that item is present.
 * If multiple copies of the item are present in the list, only
 * the one that comes first in the list is deleted.
 * @param n the item to be deleted
 * @return true if the item was found and deleted, or false if the item
 *    was not in the list.
 */
public boolean remove(Node n) {

   if ( head == null ) {
          // The list is empty, so it certainly doesn't contain item.
      return false;
   }
   else if ( head.item.equals(n) ) {
           // The item is the first item of the list.  Remove it.
      head = head.next;
      return true;
   }
   else {
          // The item, if it occurs at all, is somewhere beyond the 
          // first element of the list.  Search the list.
      Node runner;     // A node for traversing the list.
      Node previous;   // Always points to the node preceding runner.
      runner = head.next;   // Start by looking at the SECOND list node.
      previous = head;
      while ( runner != null && runner.item.compareTo(n) < 0 ) {
             // Move previous and runner along the list until runner
             // falls off the end or hits a list element that is
             // greater than or equal to n.  When this 
             // loop ends, runner indicates the position where
             // n must be, if it is in the list.
         previous = runner;
         runner = runner.next;
      }
      if ( runner != null && runner.item.equals(n) ) {
             // Runner points to the item that is to be deleted.
             // Remove it by changing the pointer in the previous node.
         previous.next = runner.next;
         return true;
      }
      else {
             // The item does not exist in the list.
         return false;
      }
   }

} // end delete()

jemz -1 Master Poster · Answer 2 · 2010-08-14T08:33:30+00:00

/**
 * Delete a specified item from the list, if that item is present.
 * If multiple copies of the item are present in the list, only
 * the one that comes first in the list is deleted.
 * @param n the item to be deleted
 * @return true if the item was found and deleted, or false if the item
 *    was not in the list.
 */
public boolean remove(Node n) {

   if ( head == null ) {
          // The list is empty, so it certainly doesn't contain item.
      return false;
   }
   else if ( head.item.equals(n) ) {
           // The item is the first item of the list.  Remove it.
      head = head.next;
      return true;
   }
   else {
          // The item, if it occurs at all, is somewhere beyond the 
          // first element of the list.  Search the list.
      Node runner;     // A node for traversing the list.
      Node previous;   // Always points to the node preceding runner.
      runner = head.next;   // Start by looking at the SECOND list node.
      previous = head;
      while ( runner != null && runner.item.compareTo(n) < 0 ) {
             // Move previous and runner along the list until runner
             // falls off the end or hits a list element that is
             // greater than or equal to n.  When this 
             // loop ends, runner indicates the position where
             // n must be, if it is in the list.
         previous = runner;
         runner = runner.next;
      }
      if ( runner != null && runner.item.equals(n) ) {
             // Runner points to the item that is to be deleted.
             // Remove it by changing the pointer in the previous node.
         previous.next = runner.next;
         return true;
      }
      else {
             // The item does not exist in the list.
         return false;
      }
   }

} // end delete()

hello sir thank you for the reply and putting some comments it really helps me and also to the people who will read this thread...i will write again if i have doubt..more power to you...

jemz -1 Master Poster · Answer 3 · 2010-08-16T08:46:16+00:00

jemz, when removing a node from a list one has to specify which node is going to be deleted. For example, if you are going to delete a node where the data member value is a specific string, e.g. "wonderful". You may have to do a search for the specific string in the list. In this case the signature of the method should be:
Node remove(String s) {...} rather than Node remove(Node n){....} unless you just want to delete a specific node n.
Anyway, I write the following two methods to delete 1. the head or 2. the tail node for your reference. Provided that Node definition is:
class Node{
String value;
Node next;
}
public Node removeFirst(){// delete the head node of the list
	if (isEmpty()) // if the list is empty
	return null;   // return null, i.e. no node can be returned
	else {  // if the list is not empty
	Node p = head; // make node p to represent the head node
	head = head.next; // after delete the head the next node of the original head will be the new head
	return p;  // return the previous head represented by p
	}
}
	
public Node removeLast(){ // delete the tail of the list
	if (isEmpty()) // if the list is empty
	return null;   // return no node
	else { // if the list is not empty
	Node p = head; // make p to represent the original head
	while(p.next !=tail) //when the next node of the p is not the tail node
	p = p.next; // make the node p to represent its next node
    /* after the while loop is executed, the p will be the node just before the tail node */
	Node pp = tail; //make node pp represent the tail
	tail=p; // the node p becomes the new tail
	tail.next=null; // the next of the new tail should be null
	return pp; // return the original tail represented by pp
}

hello sir tong1,

i tried it and it works...but my problem now how i am going to search and element example n.value.equals("jemz") this will print found if in the list otherwise not found can you help me please..hoping for your positive responds...
here is my code i get an error...

public Boolean search(Node n)
   {
   	 Node f = head;
   	 boolean find=false;
   	 while(f!=null)
   	 {
   	 	if(f.value.equals("jemz"))
   	 	{
   	 		find=true;
   	 		break;
   	 	}   
   	 		
   	 }
   	   if(find)
   	   {
   	   	System.out.println("found");
   	   	return true;
   	   }
   	 	
   	 	else
   	 	{
   	 		System.out.println("Not found");
   	 		return false;
   	 	}
   	 	f= f.next;

   }
  static void print(SinglyLinkedList list)
   {
   	 // System.out.println("\n");
   	  Node n = list.getFirst();
   	  while(n!=null)
   	  {
   	  	System.out.print( n.value+ ",");
   	  	n=n.next;
   	  	
   	  }
   	
   	  System.out.println("\n");
   }
  	 	
	public static void main(String[] args)
	{
		SinglyLinkedList list = new SinglyLinkedList();
		//construct a sample list
		for(int i=0;i<10;i++)
		{
			Node n = new Node();
			n.value = "Miguel " + (i + 1);		
			list.add(n);
		//	list.addFirst(n);
		}
		print(list);
		// insertAfter
	     Node x = new Node();
		 x.value = "jemz";
		 Node target = list.getFirst();
		 list.insertAfter(x,target);
		 
		 
	    System.out.println("The size of list: " + list.size);
		 
	
	     list.removeFirst();
	     print(list);
			 
	      System.out.println(list.contains(x));
	      print(list);
	   
	       System.out.println(list.search(x));//here i got problem also i don;t know here.
		 
	  	 
	
	
	}
}

tong1 22 Posting Whiz · Answer 4 · 2010-08-16T09:00:58+00:00

Are you going to search for a specific string "jemz" in a list? If so, your seach method should be declared as follows:
(1) public Boolean search(String s);
where the argument s will contain a string, such as "jemz". If there is a node where the data member value is "jemz" in the list, the method returns true. If not it returns false.
Or
(2) public Node search(String s); if there is a node where the data member value is "jemz" then the method returns that node.

(3) Your declaration is :
public Boolean search(Node n); which means this method is going to search for a specific Node.

Depending on different situations you have to choose only one from the above 3 declaration.

jemz -1 Master Poster · Answer 5 · 2010-08-16T09:09:55+00:00

Are you going to search for a specific string "jemz" in a list? If so, your seach method should be declared as follows:
(1) public Boolean search(String s);
where the argument s will contain a string, such as "jemz". If there is a node where the data member value is "jemz" in the list, the method returns true. If not it returns false.
Or
(2) public Node search(String s); if there is a node where the data member value is "jemz" then the method returns that node.
(3) Your declaration is :
public Boolean search(Node n); which means this method is going to search for a specific Node.
Depending on different situations you have to choose only one from the above 3 declaration.

hello sir thank you for the reply, please correct me if i am wrong..
here is my code i think it is in your number 3 options i have coded

public Boolean search(Node n)
   {
   	 Node f = head;
   	 boolean find=false;
   	 while(f!=null)
   	 {
   	 	if(f.value.equals("jemz"))
   	 	{
   	 		find=true;
   	 		break;
   	 	}   
   	 	f=f.next;	 	 		
   	 }
   	   if (find)
   	   {
   	   	System.out.println("found");
        return true; 
   	   }
      else
      {
      	System.out.println("Not found");
      	return false;
      }
   }
 static void print(SinglyLinkedList list)
   {
   	 // System.out.println("\n");
   	  Node n = list.getFirst();
   	  while(n!=null)
   	  {
   	  	System.out.print( n.value+ ",");
   	  	n=n.next;
   	  	
   	  }
   	
   	  System.out.println("\n");
   }
  	 	
	public static void main(String[] args)
	{
		SinglyLinkedList list = new SinglyLinkedList();
		//construct a sample list
		for(int i=0;i<10;i++)
		{
			Node n = new Node();
			n.value = "Miguel" + (i + 1);		
			list.add(n);
		//	list.addFirst(n);
		}
		print(list);
		// insertAfter
	         Node x = new Node();
		 x.value = "jemz";
		 Node target = list.getFirst();
		 list.insertAfter(x,target);
		 
		 
		 System.out.println("The size of list: " + list.size);
		 
	
	    // list.removeFirst();
	       print(list);
			 
	      System.out.println(list.contains(x));
	      print(list);
	   
		System.out.println("found" +list.search(x));
		 
	  	 
	
	
	}
}

sir tong1 am i correct?hoping for your postive responds...thank you in advance

tong1 22 Posting Whiz · Answer 6 · 2010-08-16T09:41:47+00:00

If it is the case (3), in the method body the argument n (the instance of Node) rather than "jemz" should be used for comparison. The content of the data member of the node n could be any string. You are searching for the node n in the list which has nothing to do with "jemz". So there are some misunderstandings in your method body. If I were you I would choose (2) which may make more sense.
If you understand me could you please write a search method based on the choice (2)?

jemz -1 Master Poster · Answer 7 · 2010-08-17T20:47:32+00:00

If it is the case (3), in the method body the argument n (the instance of Node) rather than "jemz" should be used for comparison. The content of the data member of the node n could be any string. You are searching for the node n in the list which has nothing to do with "jemz". So there are some misunderstandings in your method body. If I were you I would choose (2) which may make more sense.
If you understand me could you please write a search method based on the choice (2)?

Hello sir tong1,

Thank you for helping me and giving idea...more power to you....