Thread: 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

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.

Originally Posted by Parranoia

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

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.

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);
	}
 
}

 
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.

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.

Originally Posted by andreas90

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?

Originally Posted by danthegreat

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.