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:
Code :
//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:
Code :
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
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.
Re: LinkedList RemoveAll Method
Quote:
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
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?
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:
Code :
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.
Re: LinkedList RemoveAll Method
How would I compile and test the program?
Re: LinkedList RemoveAll Method
ok here is the program:
Code :
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);
}
}
Re: LinkedList RemoveAll Method
It's missing the ListNode class definition.
Re: LinkedList RemoveAll Method
Code :
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.
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:
Code :
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.
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.
Re: LinkedList RemoveAll Method
Quote:
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?
Re: LinkedList RemoveAll Method
Quote:
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.
