Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 13 of 13

Thread: LinkedList RemoveAll Method

  1. #1
    Junior Member
    Join Date
    Jun 2012
    Posts
    6
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default LinkedList RemoveAll Method

    Hi guys,

    I am having a problem with my linkedlist class. I am making it from scratch and I want the removeAll method to remove all occurences of item from the linked list. If item is not present, I want the method to quit without throwing.

    It seems simple since I already made a remove method:
    	//removes the first occurance of an object from the list.
    	public void remove(Object data){
    		//nothing to remove if nothing is in the list
    		if(isEmpty()){
    			return;
    		}
     
    		ListNode current=front;
    		//handles if first element is the object we are looking for..
    		if(current.getValue().equals(data)){
    			removeFirst();
    			return;
    		}
     
    		//handles if non-first element is object we are looking for
    		while(!current.getNext().getValue().equals(data)){
    			current=current.getNext();
    		}
    		current.setNext(current.getNext().getNext());
     
     
    	}

    The above method works...however when I try to make my removeAll:
    	public void removeAll(Object data){
    		//nothing to remove if nothing is in the list
    		if(isEmpty()){
    			return;
    		}
     
    		ListNode current=front;
    		while(current!=null){
    			if(current.getValue().equals(data)){
    				removeFirst();
     
    			}
    			else if(current.getNext().getValue().equals(data)){
    				current.setNext(current.getNext().getNext());
    			}
    			else{
    				current=current.getNext();
    			}
    		}
     
    	}

    It always casts a nullpointerexception. I've tried for a couple days now and really I can't figure out what is wrong..I've printed out all the variables and nothing seems to be a problem...do I need to return or something? The loop seems to be running infinitely..

    thanks,
    -dan


  2. #2
    Member
    Join Date
    Apr 2012
    Posts
    161
    Thanks
    0
    Thanked 27 Times in 27 Posts

    Default Re: LinkedList RemoveAll Method

    Since you are checking whether or not the variable is null, once it becomes null and stops the loop it could be throwing that exception. I'd try surrounding the while loop in a try-catch block and go from there.

  3. #3
    Junior Member
    Join Date
    Jun 2012
    Posts
    6
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: LinkedList RemoveAll Method

    Quote Originally Posted by Parranoia View Post
    Since you are checking whether or not the variable is null, once it becomes null and stops the loop it could be throwing that exception. I'd try surrounding the while loop in a try-catch block and go from there.
    Well I actually printed the variable and current remains null constantly so in my mind....so I suppose that is what causing nullpointer, however when I add a try catch block, the loop runs forever...so its like a new problem

  4. #4
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    SW Missouri
    Posts
    20,095
    Thanks
    48
    Thanked 2,152 Times in 2,125 Posts

    Default Re: LinkedList RemoveAll Method

    You should not need a try/catch block for an event that the program should never let happen.
    Can you post code that compiles, executes and shows the problem?
    If you don't understand my answer, don't ignore it, ask a question.

  5. #5
    Junior Member
    Join Date
    Jun 2012
    Posts
    6
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: LinkedList RemoveAll Method

    What do you mean? What I posted above causes an infinite loop for some reason. Nothing about nullpointerexception occurs anymore. This is what is in my driver method:
     
    	public static void main(String[] args){
    		MyLinkedList test = new MyLinkedList();
    		test.addFront("hi");
    		test.addAfter("hi", "how");
    		test.addLast("hi");
    		test.addLast("are");
    		test.addLast("you");
    		test.addLast("hi");
     
    		test.removeAll("hi");
    		System.out.println(test);
    	}

    in the removeAll method, I System.out.println(current.getValue()); and the word "hi" is infinitely printed the screen.

  6. #6
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    SW Missouri
    Posts
    20,095
    Thanks
    48
    Thanked 2,152 Times in 2,125 Posts

    Default Re: LinkedList RemoveAll Method

    How would I compile and test the program?
    If you don't understand my answer, don't ignore it, ask a question.

  7. #7
    Junior Member
    Join Date
    Jun 2012
    Posts
    6
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: LinkedList RemoveAll Method

    ok here is the program:

    public class MyLinkedList {
     
    	//refers to first node in the linked list
    	private ListNode front;
     
    	//default constructor (initializes the front of the list to null)
    	public MyLinkedList(){
    		front=null;
    	}
     
    	//checks if the list is currently empty. (true if yes; false if no)
    	public boolean isEmpty(){
    		return (front==null);
    	}
     
    	//creates a new front for the list.
    	public void addFront(Object data){
    		front = new ListNode(data,front);
    	}
     
    	//inserts specific data after a given targer
    	public void addAfter(Object target, Object data){
    		ListNode current=front;
     
    		//handles if client adds an element before setting a front
    		if(current==null){
    			addFront(data);
    		}
    		else{
    			while(!current.getValue().equals(target)){
    				current = current.getNext();		
    			}
    			current.setNext(new ListNode(data, current.getNext()));
    		}
    	}
     
    	//adds data to the end of the list
    	public void addLast(Object data){
    		ListNode current=front;
     
    		//handles if client wants to add to the end of the list before declaring a front.
    		//in this case, front is declared anyway
    		if(current==null){
    			addFront(data);
    		}
    		else{
    			while(current.getNext()!=null){
    				current = current.getNext();
    			}
    			current.setNext(new ListNode(data, null));
    		}
     
    	}
     
    	//removes the first occurance of an object from the list.
    	public void remove(Object data){
    		//nothing to remove if nothing is in the list
    		if(isEmpty()){
    			return;
    		}
     
    		ListNode current=front;
    		//handles if first element is the object we are looking for..
    		if(current.getValue().equals(data)){
    			removeFirst();
    			return;
    		}
     
    		//handles if non-first element is object we are looking for
    		while(!current.getNext().getValue().equals(data)){
    			current=current.getNext();
    		}
    		current.setNext(current.getNext().getNext());
     
     
    	}
     
     
    	//removes the first element from the list & sets the new front element
    	public void removeFirst(){
    		//handles when list is blank
    		if(isEmpty()){
    			return;
    		}
    		ListNode current=front;
    		front=front.getNext();
    		current.setNext(null);
    	}
     
    	//removes the last item in the list.
    	public void removeLast(){
    		//once front is null, there are no elements, therefore no actions are taken
    		if(isEmpty()){
    			return;
    		}
    		ListNode current = front;
    		//handles if only one element is currently in this list.
    		if(this.size()==1){
    			removeFirst();
    			front=null;
    		}
    		else{
    			while(current.getNext().getNext()!=null){
    				current=current.getNext();		
    			}
    			current.setNext(null);
    		}
     
     
    	}
     
    	//returns the total number of elements in the list
    	public int size(){
    		int counter=0;
    		ListNode current = front;
    		while(current!=null){
    			counter++;
    			current=current.getNext();
    		}
    		return counter;
    	}
     
    	//returns an element based on an index passed in
    	public Object get(int index) throws IndexOutOfBoundsException{
    		ListNode current=front;
     
    		//messages client when index is greater than list size or negative value entered
    		if((index > this.size()-1 || index < 0)){
    			throw new IndexOutOfBoundsException("Invalid Index: Out Of Bounds.");
    		}
    		//otherwise counts to given index and returns the element
    		else{
    			int count=0;
    			while(count!=index){
    				count++;
    				current=current.getNext();
    			}
    			return current.getValue();
    		}
     
    	}
     
    	//determines whether a certain piece of data is inside of the list.
    	public boolean contains(Object data){
    		ListNode current = front;
    		while(current!=null){
    			if(current.getValue().equals(data)){
    				return true;
    			}
    			else{
    				current=current.getNext();
    			}
    		}
    		return false;
    	}
     
    	//string representation of the list.
    	public String toString(){
    		ListNode current = front;
    		String toR=" ";
    		while(current!=null){
    			toR+=current.getValue()+" ";
    			current=current.getNext();
    		}
    		return "[" + toR +"]";
     
    	}
     
     
    	public void removeAll(Object data){
    		//nothing to remove if nothing is in the list
    		if(isEmpty()){
    			return;
    		}
     
    		ListNode current=front;
    		while(current!=null){
    			System.out.println(current.getValue());
    			if(current.getValue().equals(data)){
    				removeFirst();
     
    			}
    			else if(current.getNext().getValue().equals(data)){
    				current.setNext(current.getNext().getNext());
    			}
    			else{
    				current=current.getNext();
    			}
    		}
     
    	}
     
    	public static void main(String[] args){
    		MyLinkedList test = new MyLinkedList();
    		test.addFront("hi");
    		test.addAfter("hi", "how");
    		test.addLast("hi");
    		test.addLast("are");
    		test.addLast("you");
    		test.addLast("hi");
     
    		test.removeAll("hi");
    		System.out.println(test);
    	}
     
    }

  8. #8
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    SW Missouri
    Posts
    20,095
    Thanks
    48
    Thanked 2,152 Times in 2,125 Posts

    Default Re: LinkedList RemoveAll Method

    It's missing the ListNode class definition.
    If you don't understand my answer, don't ignore it, ask a question.

  9. #9
    Junior Member
    Join Date
    Jun 2012
    Posts
    6
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: LinkedList RemoveAll Method

     
    public class ListNode {
    	private Object value;
    	private ListNode next;
     
    	public ListNode(Object v, ListNode n){
    		value=v;
    		next=n;
    	}
     
    	public void setValue(Object v){
    		value=v;
    	}
     
    	public void setNext(ListNode n){
    		next=n;
    	}
     
    	public Object getValue(){
    		return value;
    	}
     
    	public ListNode getNext(){
    		return next;
    	}
    }

    Thank you, I appreciate your help.

  10. #10
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    SW Missouri
    Posts
    20,095
    Thanks
    48
    Thanked 2,152 Times in 2,125 Posts

    Default Re: LinkedList RemoveAll Method

    Now to start debugging the code. I added a toString() method to the ListNode class so it can be printed easily. Print out the value and the next. A side effect is it will print the whole list thru the next variable.
    Until you find the cause of the infinite loop, add some code to exit the while loop after a few loopings, say 20. Define an int: cntr outside the loop and inside the loop:
             if(cntr++ > 20) break; //<<<<<<<<<<<< EXIT LOOP

    Add lots more println statements to show the node and list after every change to the list. I added over a half dozen new printlns.
    If you don't understand my answer, don't ignore it, ask a question.

  11. #11
    Member
    Join Date
    Jan 2012
    Location
    Hellas
    Posts
    284
    Thanks
    11
    Thanked 59 Times in 57 Posts

    Default Re: LinkedList RemoveAll Method

    Hello danthegreat!
    The problem is in the removeAll(Object data) method. The while loop is infinite because the condition never evaluates to false - current is never equal to null in the test you make. To be more specific, in your test case the if statement is always executing.
    Remember that a local variable (such as current) only exists inside the block that it is defined.
    Hope this helps.

  12. #12
    Junior Member
    Join Date
    Jun 2012
    Posts
    6
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: LinkedList RemoveAll Method

    Quote Originally Posted by andreas90 View Post
    Hello danthegreat!
    The problem is in the removeAll(Object data) method. The while loop is infinite because the condition never evaluates to false - current is never equal to null in the test you make. To be more specific, in your test case the if statement is always executing.
    Remember that a local variable (such as current) only exists inside the block that it is defined.
    Hope this helps.

    Thanks for the comments Norm and andreas90.

    @andreas -- shouldn't 'current=current.getNext()' eventually equal null since the last element in the linkedlist has a next of 'null' so after the last element is seen, the method should finish executing?

  13. #13
    Member
    Join Date
    Jan 2012
    Location
    Hellas
    Posts
    284
    Thanks
    11
    Thanked 59 Times in 57 Posts

    Default Re: LinkedList RemoveAll Method

    Quote Originally Posted by danthegreat View Post
    Thanks for the comments Norm and andreas90.

    @andreas -- shouldn't 'current=current.getNext()' eventually equal null since the last element in the linkedlist has a next of 'null' so after the last element is seen, the method should finish executing?
    It seems that it should. But this statement is in the else block and your code never enters that part. It stucks on the if block. You need to have in each of the three blocks a statement that will make the while loop stop executing (i.e. current equal null), otherwise you 'll get an infinite loop when entering that blocks.

Similar Threads

  1. [SOLVED] Sorting LinkedList
    By wdh in forum What's Wrong With My Code?
    Replies: 28
    Last Post: April 29th, 2012, 12:52 PM
  2. Can you rewrite this method without using LinkedList?
    By wholegrain in forum Java Theory & Questions
    Replies: 1
    Last Post: February 12th, 2012, 11:37 PM
  3. Implementation of remove method in linkedlist Iterator
    By jay2you in forum Collections and Generics
    Replies: 3
    Last Post: October 12th, 2011, 09:16 AM
  4. Replies: 4
    Last Post: July 5th, 2011, 03:00 AM
  5. Writing clone() method for LinkedList
    By vluong in forum Collections and Generics
    Replies: 6
    Last Post: October 27th, 2009, 08:41 AM