Thread: Singly Linked List of Integers, get(int i) function throws Null Pointer Exception

Dear Forum,

I have written this neat Java Class as part of my preparation for next week's exams. Somehow, the function IntList get(int i), which is supposed to return a reference to the i-th element of the List throws a null pointer exception and i cant figure out why.

I have gone through the code several times and I am quite certain the get() method is correct. The mistake must be somewhere else. Can you help me?

IntList.txt

IntList.txt

 
public class IntList {
 
	private int info;					//the int data of this list element  
	private IntList next;					//the rest of the list
 
	/**
	* Sets up a new instance of IntList corresponding to the given info and next.
	* @param info the int data of this list element
	* @param next the rest of the list
	*/
	public IntList(int info, IntList next) {
		this.info = info;
		this.next = next;
 
	}
 
	/**
	* A new list where the given info has been prepended.
	* @param info the int data of the new list element
	* @return a new instance of IntList
	*/
	/*
	public IntList prepend(int info) {
		return new IntList(info, this);
 
	}
	*/
 
	/** 
	* A new list where the given info has been appended.
	* @param info the int data of the new list element
	* @return a new instance of IntList
	*/
 
	public IntList append(int info) {
		if(next == null) {
			return new IntList(this.info, new IntList(info, null));
 
		} else {
			return new IntList(this.info, next.append(info));
 
		}
	}
 
	public IntList get(int i) {
		int counter=0;
		IntList current=this;
 
		while(counter < i) {
 
				current=current.next;		
		}	
		counter++;
 
		return current;
	}
	/**
	* Commputes the sum of all elements of this list.
	* @return the sum of all elements
	*/
	public int sum() {
		if(next == null) {
			return info;
 
		} else {
			return info + next.sum();
 
		}
	}
 
	/**
	* Auxiliary function for the reversal of this list.
	* @param acc the list elements accumulated so far
	* @return a new instance of IntList
	*/
	private IntList reverseAux(IntList acc) {
		if(next == null) {
			return new IntList(info, acc);
 
		} else {
			return next.reverseAux(new IntList(info, acc));
 
		}
	}
 
	/**
	* A new list with the elements of this list in reverse order. 
	* @return 	a new instance of the IntList
	*/
	public IntList reverse() {
		return reverseAux(null);
 
	}
 
	/**
	* String representation of this list.
	*/
	@Override
	public String toString() {
		if(next == null) {
			return "" + info;
 
		} else {
			return info + " , " + next;
 
		}
	}
 
	/**
	* An integer array is converted to a list
	* @param values is an array containing integer elements
	* @return a new instance of IntList
	*/
	public static IntList fromArray(int[] values) {
		int n = values.length;
		IntList res = new IntList(values[0] , null);
 
		for(int i = 1; i < n ; i ++) {
			res = res.append(values[i]);
 
		}
		return res;
 
	}
 
	/**
	* The length of a given IntList object is determined
	* @return the length of the list
	*/
	public  int length() {
		int counter = 1;
 
		while(next != null) {
			counter = counter + 1;
 
			next = next.next;
		}
		return counter;
	}
 
	/**
	* A reference to the i-th element of a list is returned
	* @param integer that tells the function which element shall be returned
	* @return A reference to the i-th element
	*/ 
 
 
	/*public IntList map(IntList list) {
		int shorter_list = 0;
 
		IntList ret = new IntList(0 , null);
 
		if(list.length <= this.length) {
			shorter_list = list.length;
 
		} else {
			shorter_list = this.length;
 
		}
 
		for(int i = 0 ; i < shorter_list ; i ++) {
			ret.append()
 
		}
	}
	*/
 
 
 
	public static void main(String[] args) {
		IntList lst = new IntList(1, null);
 
		for(int i = 2 ; i < 10 ; i ++) {
			lst = lst.append(i);	
		}
		System.out.println(lst);
		System.out.println(lst.reverse());
		System.out.println(lst.sum());
		int[] values = new int[4];
		values[0] = 3;
		values[1] = 4;
		values[2] = 5;
		values[3] = 8;
 
 
	  	System.out.println(fromArray(values));
		System.out.println(fromArray(values).length());
 
 
		System.out.println(lst.length());
		System.out.println(lst.get(3));
		System.out.println(lst.get(5));
 
	}	
 
 
 
 
}

Dont be scared by the length of the code, the paragraph that I am having trouble with is the get() method (5 lines).

I also think that the error lies in the append method somehow. I believe that after appending elements to an empty list, the pointer points at null and not at the first list element. But I dont know, since I do this for the first time in my life!

20 dollars to the one who fixes this otherwise fine code. pay via paypal

Hi Norm,
I ran the code through a debugger and it turns out that current.this.next = null. In other words the this pointer does not point at the beginning of the list, but at the end. This is why the get() function cannot count through the list. And this is the reason why the Null Exception is thrown.

Can anybody tell me how to change my append() method in order for the this pointer to point at the beginning of the list?

Thank you !!

how to change my append() method in order for the this pointer to point at the beginning of the list

You want a circular list? The end node points to the first node.
That would keep you from running off the end of the list.

I have never heard of that. It would solve my problem though.
Can you tell me how the circular list is implemented in my code?

Cheers

You have a basic misunderstanding of how Lists work. You have each IntList object pointing at the next IntList object. Whereas how Lists should work is you only have one IntList object and it points at the first (head) Node in the List with each Node pointing at the next Node. The data (in this case an int) is stored in the Node objects. To make life easier you can also have the List point at the last (tail) Node in the List.

I don't think a circular list would work. Say you have a list with one element and the user asks for the 10th element what element would you return?
How do other containers like ArrayList handle it when the get() method asks for a element past the end of the collection? They throw an exception. That's what your code should do.
In your posted code, the last test asks for element 5. There is none -> throw an exception.

At Junky: I theoretically understand how a list works. The problem is I cannot tell if my code does what a list is supposed to do. I do not really understand it. Thats why it would be so helpful if someone would show me so then I could learn how it is done right and spot my mistakes.

At Norm: As far as I can tell, my main method initializes a intList object called lst. I then use the append function to append 9 nodes. Therefore, the length of lst is 9.

My reasoning is that, if I ask the computer to return the 5th element of lst, then having said the above, there should definitely be one.

And again, I would probably understand what you guys are trying to teach me if you were to show me where my mistakes are precisely.

many thanks,

I ll talk to you tomorrow morning since it is 2 am here.
Felix

Taking a rough stab at it I would say the problem is in the append method because you return a new IntList object and assign it to lst. Therefore somewhere along the line that variable is no longer pointing at the IntList object that contains the first value. As I said fannying about with all these IntLists objects is not the correct way to go. Just have a single IntList object and its job is to handle adding/removing new nodes and they should retain the same order. Unless you call reverse but that should create a totally new List.