thinkersdelight

Just another WordPress.com site

How To: Singly Linked List of Integer Values in Java.

Hello Everybody!

In my first post, I would like to share some Java code with you, which I recently created. This code is a singly linked list of integer values. For those of you who do not know what a singly linked list is, let me explain quickly. In a singly linked list, you will find two entities. There is the list itself, and there are list elements. The list elements consist of the information they carry and a reference to the list element ahead of them.

It is possible to create a singly linked list in Java using two classes. One class “Nodes” and one class “List” for example. However, one can also do both in one class, as you can see below.

If you have any questions, please let me know in the comments section!

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) { //Constructor
		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));

		}
	}

	/**
	* returns a new IntList object with elements from index start to end of original intList object
	* @param start index and stop index
	* @return New IntList object with some elements from original IntList object
	*/
	public IntList copyRange(int start, int end) {
		int n = length();
		int to_del = n - end;
		int counter = 0;

		//initialize list object that already lacks all elements up to start.
		IntList two = get(start);
		//the task now is to select elements from two wisely
		IntList ret = new IntList(two.info , null);
		//selection happens here
		for(int i = 2 ; i <= (end-start) +1 ; i ++) {
			ret = ret.append(two.get(i).info);

		}
		return ret;
	}

	//helper for concat method. visibility of info is private
	public int getInfo() {
		return info;

	}

	/**
	* @param list object that is to be concatenated to the object upon which concat is called
	* @return new list object consisting of both previous lists
	*/
	public IntList concat(IntList list) {

		//original object is referenced
		IntList ret = this;

		//list from paramter is appended elementwise
		while(list != null) {
			ret = ret.append(list.getInfo());
			list = list.next;
		}

		return ret;
	}

	/**
	* indices start at 1
	* @param the index of the element that is to be deleted
	* @return IntList without the i-th element
	*/
	public IntList remove(int i) {
		//original object is referenced;
		IntList neuesObjekt = get(1);

		//special case, makes dealing with deleting the first element easier
		if(i == 1) {
			IntList ret2 = get(2);
			return ret2;

		}
		IntList ret = new IntList(neuesObjekt.info, null);

		for(int k = 2 ; k < i ; k ++) {
			ret = ret.append(neuesObjekt.get(k).info);

		}

		//looking at the indices of the above and below for loop closely, this is where the i-th element is left out!
		for(int j = i + 1 ; j < neuesObjekt.length() +1; ++j) {
			ret = ret.append(neuesObjekt.get(j).info);

		}
		return ret;
	}

	/**
	* adds two lists elementwise
	* @param listobject that is to be added to the other list
	* @return IntList object whose elements are the sums of the input lists
	*/
	public IntList map(IntList list) {
		//Create references to the object upon which the method is called
		IntList one = get(1);
		IntList two = list.get(1);
		//Create result object to ensure the original object remains unchanged
		IntList result = new IntList(one.info + two.info, null);

		//The execution of map varies with the length of both lists
		if(one.length() == two.length()) {
			for(int i = 2 ;  i < one.length() + 1 ; i ++) {
				result = result.append(one.get(i).info + two.get(i).info);

			} 

		}
		if(one.length() < two.length()) {
			//add the list elements elementwise, until one list is "empty"
			for(int i = 2 ; i < one.length() + 1 ; i ++) {
				result = result.append(one.get(i).info + two.get(i).info);

			}
			//add the remaining elements from the longer list
			for(int j = one.length() + 1 ; j < two.length() + 1 ; j++) {
				result = result.append(two.get(j).info);

			}

		}
		//analogue to the above case
		if(one.length() > two.length()) {
			for(int k = 2 ; k < two.length() + 1 ; k++) {
				result = result.append(one.get(k).info + two.get(k).info);

			}
			for(int l = two.length() + 1 ; l < one.length() + 1 ; l ++) {
				result = result.append(one.get(l).info);

			}

		}
		return result;

	}

	/**
	* indices start at 1!
	* @param position of element that is to be referenced
	* @return new IntList starting at the i-th element
	*/
	public IntList get(int i) {
		IntList current = this;

		for(int k = 0 ; k < i - 1; k++) {
			//check if the next element does exist, so that no invalid get calls can be made
			if(current.next != null) {
				current = current.next;

			}

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

		}
	}
	public static String toString2(int[] input) {
		String str = "";

		for(int i = 0 ; i < input.length ; i ++) {
			str = str + input[i];

		}
		return str;

	}

	/**
	* 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; //length is required for for-loop
		//create IntList object that will be returned by the function. initialize it with the first array element
		IntList res = new IntList(values[0] , null);

		//append the remaining elements
		for(int i = 1; i < n ; i ++) {
			res = res.append(values[i]);

		}
		return res;

	}

	public static int[] toArray(IntList list) {
		int[] ret = new int[list.length()];
		for(int i = 0 ; i < list.length() ; i ++) {
			ret[i] = list.get(i+1).info;

		}

		return ret;
	}
	/**
	* The length of a given IntList object is determined
	* @return the length of the list
	*/
	public int length() {
		if(next != null) {
			//recursive call of length method
			return 1 + next.length();
		//base case
		} else {
			return 1;

		}
	}

	public static void main(String[] args) {

		System.out.println("The following method calls show the working of the above functions: ");
		System.out.println("-------------------------------------------------------------------");
		System.out.println("A new list object lst is created..");

		IntList lst = new IntList(5, null);
		lst = lst.append(4);
		lst = lst.append(2);
		lst = lst.append(9);
		lst = lst.append(1);
		lst = lst.append(7);
		lst = lst.append(3);
		lst = lst.append(6);
		lst = lst.append(8);

		System.out.println(lst);

		System.out.println("..and reversed..");
		System.out.println(lst.reverse());
		System.out.println("..its length is determined");
		System.out.println(lst.length());
		System.out.println("Now, lets construct an integer array and build a list from it: ");

		int[] values = new int[4];
		values[0] = 3;
		values[1] = 4;
		values[2] = 5;
		values[3] = 8;

		int[] values2 = new int[6];
		values2[0] = 1;
		values2[1] = 2;
		values2[2] = 3;
		values2[3] = 4;
		values2[4] = 5;
		values2[5] = 6;

		System.out.println(fromArray(values2));
		System.out.println("..print elements 2 to 5..");
		System.out.println(fromArray(values2).copyRange(2,5));
		System.out.println("And now concatenate this list to the list lst..");
		System.out.println(lst.concat(fromArray(values2).copyRange(2,5)));
		System.out.println("Let's remove the first one of the first 5 elements from lst...");
		for(int i = 1 ; i < 6 ; i ++) {
			System.out.println("element " + i + " removed: ");
			System.out.println(lst.remove(i));

		}
		System.out.println("And finally, lets map lst and the list generated from the array values2 together! .. ");
		System.out.println(lst.map(fromArray(values2)));
		System.out.println("...lets even map the list generated from the array values to the other 2! ...");
		System.out.println(lst.map(fromArray(values2).map(fromArray(values))));
		System.out.println("-------------------------------------------------------------------");
		System.out.println("Done.");

	}
}
Advertisements