Page 1 of 1

Recursive Generic LinkedList Rate Topic: -----

#1 m-e-g-a-z  Icon User is offline

  • Winning
  • member icon


Reputation: 497
  • View blog
  • Posts: 1,453
  • Joined: 19-October 09

Posted 09 July 2010 - 06:27 AM


Java Tutorial

Recursive Generic LinkedList



In this tutorial, I am going to briefly explain and cover recursion and LinkedList, as this tutorial is aimed at intermediate programmers who are studying these topics and have a basic understanding that they also want to expand on. This tutorial aims to 'kill two birds with one stone' by focusing on concepts I have seen programmers struggle to understand applying recursion with LinkedLists and basic Generics.

Recursion is when a method (function for some other languages) is defined within its own method/function. It is used to solve problems of smaller instances for the same problem where repetition is occurred.

'The greatest common factor (gcf) of two or more non-zero integers, is the largest positive integer that divides the numbers without a remainder.' - Wikipedia

For example, look at this snippet below.

Snippet - Greatest Common Divisor

public class Num {

        static int gcd(int n, int m) {
                   if(n == m)
                      return n;
                   else if (n > m)
                      return gcd(n-m, m);
                   else
                      return gcd(m, m-n);
                }

        public static void main (String [] args){

                System.out.println(gcd(Integer.parseInt(args[0]),Integer.parseInt(args[1])));

        }
}


We can see from the following that the base case for the recursive method is
 if(n == m)
        return n;


Once both integers are equal to each other, the recursion will terminate and return n. We need a base case because if we didn't, the recursion would be too deep and not terminate causing a StackOverflowError runtime error.

Below, is where the recursion happens where we subtract the lowest variable from the highest variable and check for equality. If the variable 'n' is higher than 'm' we recursively call the gcd method passing 'n-m' and 'm'. We take 'n-m' since we need the greatest common divisor 'largest positive integer that divides the numbers without a remainder'. Both n and m need to be equal and since 'n' is higher than 'm' in this case, we recursively call gcd(n-m,m) therefore see whether both n and m are equal, if they aren't, the process is carried on again until the base case n==m is reached. The same applies for the other case else where 'n' is not higher than 'm', we can simply recursively call the gcd method gcd(m,m-n) and again check for equality.
  //if n is higher than m
   else if (n > m)
         //recursively call gcd method again 
       return gcd(n-m, m);
   else
        //if n is not higher than m, recursively call gcd method again
       return gcd(m, m-n);
 
Please note that when a recursive call is executed within a method, it does not make a new copy of the method as the arguments and variables are the only thing thing that is new. Old local variables and parameters are removed from the stack as each recursive call returns, and execution resumes at the point of the call inside the method.

A really nice thing about recursion is that you can easily solve complex problem such as creating a mini 'web crawler' where you can recursively fetch each link from a webpage and recursively call them links whilst storing them. By applying recursion for this problem to solve it, it would perform the same storing, visiting, checking tasks needed repetitively on a wide scale.

Basic pseudocode would look something like this

--links(String url, String domain)
--Check whether URL has been visited
if not
--Visit URL
--Store each URL in Collections data structure such as SET 'storedLinks' as it does not allow duplicates and make sure each URL maches domain since we dont want million links from a big site linked like Microsoft.
--Iterate through storedLinks - String a
--Call method again links(a,domain)

Generics allow type or method to operate on objects of various types while providing compile-time type safety. You might be used to the regualar generics such as LinkedList<Integer> i = new LinkedList<Integer>();. The only problem is that this LinkedList only allows us to hold Integers. In this tutorial, im going to give a generic class which allows you to hold any type.

You may be familiar with this line of code public class RecursiveList <T> apart from the T and may be thing why is there a T there? 'T' is the declaration of the formal type parameters of the class. Type parameters can be used where you would usually use ordinary types such as Integer or String.
In this example, our formal type parameter is going to be of Type T.

Note: we can use any single uppercase character as a formal type parameter, but in this example, I will be using T. I have provided a recursive generic list class in this tutorial as it allows a detailed insight how recursive data structures such as 'Linked Lists' can be used.

Method - head

So we have got this method head which takes an LinkedList of type T and returns T. Firstly, we know that the head of the list always points at the first element of a list. We can therefore assign the head of the list of type T to index 0. The head will always point to index 0 (the 0'th element) within the list.
/* Type T has a variable called head and will hold index 0 of the LinkedList*/
public  T head (LinkedList  <T> m)
	{
		return m.get(0);
	}



Method - tail

As we have a head, next we need to remove the head which will give us the tail.

So this method tail returns the whole LinkedList apart fom its head, so here tail takes an LinkedList of type 'T' and returns an LinkedList of type 'T'. So we have a local variable m which is an LinkedList and is a copy of t, the parameter. So we remove the 0'th element and then return LinkedList m. So 'm' will be the list minus it's head which is called the tail.

public  LinkedList <T>  tail (LinkedList <T>  t)
	{	/*new LinkedList to hold LinkedList passed*/
		LinkedList <T> m= new LinkedList <T> (t);         /*remove the head*/
		m.remove(0);
             /*return LinkedList*/	
		return m;
	}



Method - empty

This method called empty simply returns a new empty LinkedList of type 'T' which we will use with the recursion later in this tutorial.
public LinkedList <T>  empty ()
	{
		return new LinkedList <T>();
	}



Method - addAll

Right, so what if we wanted to add any head to a following tail? how would we do this? you would add the head then tail giving you a list containing the head and then the tail.

This method addAll takes an element of type 'T' and LinkedList as its parameters and constructs a new LinkedList whose head is the first element 'T' and tail which is LinkedList 'tail'. So it retuns returns an LinkedList consisting of the head and tail. This happens by creating a Local LinkedList and add the first element to s 'the head' and add the rest to s 'the tail' then returning the LinkedList 's' with the head as 'T' and the tail as 'tail'.
public  LinkedList  <T> addAll (T head, LinkedList <T> tail)
	{	
/*new LinkedList to hold LinkedList passed*/
		LinkedList <T> s= new LinkedList <T>();
  /*add the head first then the rest of the tail to LinkedList 's' returning this LinkedList*/
		s.add(head);
		s.addAll(tail);
		return s;
	}



Method - append

The method append takes two LinkedLists of type 'T' within it's parameters. What this method append does is that it appends two lists together using the addAll method which adds the head first 'in our case j' then the tail 'in our case k'. So if j is empty,we return k since there is nothing to append, otherwise we construct the list in which its head is the head of 'j' and appending the tail of the first list 'j' to 'k'. It calls the head method to return the head of the list and tail method to return the tail of the list. It recursively calls the append method to make index 0 of the tail the head and point the rest of the list as the tail. The base case of this method is if LinkedList 'j' is empty which makes since since if there's no head, there's no tail.
	public  LinkedList <T> append (LinkedList <T>  j, LinkedList <T>  k)
	{	
		if (j.isEmpty()) return k;
		else return addAll(head(j),append(tail(j),k));
	}


Method - reverse

This method reverse uses pretty much all the methods defined above to reverse the list. This reverse method has a base case which is of k is empty, return it. If it isn't empty, it uses the append, reverse,tail, addAll, head and empty to reverse the list.

So then, what does this method reverse a list do? It takes a list and returns a list. If T is empty, return T. The reverse of an empty list is just an empty list. Otherwise we reverse the tail of the the list, so we reverse the tail of T. We append to that the list by 'cons'ing the head of T, the head of this list onto the empty list. So in other words, we reverse the tail and stick the head on the end, and that's how we reverse the list.
	public 	 LinkedList <T> reverse (LinkedList <T>  k)
	{	
		if  (k.isEmpty()) return k;
		else return append(reverse(tail(k)),addAll(head(k),empty()));
	}


By now, you may be thinking, wow it's using all these methods and I dont know where my brain is, you may want to check out my LinkedList recursive reverse snippet and refer to all the method I previously covered then get back onto this. If you feel you understand what I have covered so far, lets proceed to the main() class. :)

Right, so now we have a class full of recursive generic methods but we need to use them and be more creative. This is where the serious fun starts, 'geeky i know'.

Firstly, instantiate a RecursiveList object of Integer Type. Like this
static RecursiveList <Integer> L = new RecursiveList <Integer>();


Method - numnum

For testing out these methods, we will need some numbers, heres a recursive method that takes a number and adds it to a list and each time it adds the number -1 on the list

    static LinkedList  <Integer> numnum (int n)
    { 
    //Base Case to terminate the recursion
    if (n==0) return L.addAll(0,L.empty());
    //adds n-1 numbers to List
    else return L.addAll(n,numnum(n-1));
	 }



Method - insertAscending

This method insertAscending takes an integer and a LinkedList within its parameters and returns a LinkedList. It inserts integers into ascending order and does this by checking whether the LinkedList is empty. If the LinkedList passed is empty, it then returns the list adding the head which is 'n' and an empty list. If the LinkedList has integers , we then check if the integer passed is higher than the head. If it is, we then return and add the head whilst recursively checking the variable 'n' against the tail so that it the integer can be placed within ascending order. It will compare the integer against the head of the tail each time at each recursive call with the base case being if LinkedList 'm' is empty.

	static  LinkedList  <Integer> insertAscending (Integer n, LinkedList <Integer> m)
	{
		if (m.isEmpty()) return L.addAll(n, L.empty());

		else if(n>L.head(m)) return L.addAll(L.head(m),insertAscending(n,L.tail(m)));
		else return L.addAll(n,insertAscending(L.head(m),L.tail(m)));
	}



This method takes a LinkedList within it's parameters and returns a LinkedList sorted Ascending. If m is empty, we simply return the LinkedList m. Think of this as our base case to get out of the recursion but also if an empty list was passed, there would not be nothing to sort. The main reason for creating the insertAscending method is so that it can be used in this method below. It uses the insertAscending method to consistently check the head of the LinkedList against the tail of the LinkedList.
Method - sortAscending

static LinkedList <Integer> sortAscending (LinkedList <Integer> m)
		{
			if (m.isEmpty()) return m;
			else return insertAscending((L.head(m)), sortAscending(L.tail(m)));
		}


Source Code - RecursiveList Class

import java.util.*;

public class RecursiveList  <T>
{

	public  T head (LinkedList  <T> m)
	{
		return m.get(0);
	}

	public  LinkedList <T>  tail (LinkedList <T>  t)
	{	
		LinkedList <T> m= new LinkedList <T> (t);
		m.remove(0);	
		return m;
	}

	public  LinkedList <T>  empty ()
	{
		return new LinkedList <T>();
	}

	public  LinkedList  <T> addAll (T head, LinkedList <T> tail)
	{	
		LinkedList <T> s= new LinkedList <T>();
		s.add(head);
		s.addAll(tail);
		return s;
	}

	public  LinkedList <T> append (LinkedList <T>  j, LinkedList <T>  k)
	{	
		if (j.isEmpty()) return k;
		else return addAll(head(j),append(tail(j),k));
	}

	public 	 LinkedList <T> reverse (LinkedList <T>  k)
	{	
		if  (k.isEmpty()) return k;
		else return append(reverse(tail(k)),addAll(head(k),empty ()));
	}
}



Source Code - Testing Class

import java.util.*;

public class Testing {

	static RecursiveList <Integer> L = new RecursiveList <Integer>();

	static LinkedList  <Integer> makeR (int n)
	{
		if (n==0) return L.addAll(0,L.empty());
		else return L.addAll(n,makeR(n-1));
	}

	static  LinkedList  <Integer> insertAscending (Integer n, LinkedList <Integer> m)
	{
		if (m.isEmpty()) return L.addAll(n, L.empty());

		else if(n>L.head(m))
			return L.addAll(L.head(m),insertAscending(n,L.tail(m)));
		else return L.addAll(n,insertAscending(L.head(m),L.tail(m)));
	}

	static LinkedList <Integer> sortAscending (LinkedList <Integer> m)
	{
		if (m.isEmpty()) return m;
		else return insertAscending((L.head(m)), sortAscending(L.tail(m)));
	}

	public static void main(String [] args)
	{
		LinkedList <Integer> m = makeR(Integer.parseInt(args[0]));
		System.out.println("List contains: "+m);
		System.out.println("List reversed: "L.reverse(m));   
	}
}



Please note that you can invoke other methods from the main or simply use the RecursiveList class just like how I did using reverse as an example in this tutorial.

Happy Coding

Is This A Good Question/Topic? 3
  • +

Replies To: Recursive Generic LinkedList

#2 bcranger  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 252
  • View blog
  • Posts: 1,199
  • Joined: 01-February 10

Posted 10 July 2010 - 12:28 AM

Good guide, I might try using some LinkedLists in the future :bananaman:
Was This Post Helpful? 0
  • +
  • -

#3 Guest_Damokles*


Reputation:

Posted 12 July 2010 - 03:01 PM

Okay don't take this too personally but here is my critic.

Maybe you should call the RecursiveList class FunctionalListUtils since it is something like a static utility class with the only difference that the methods are not static. You don't use any private fields. If it would be a real List then e.g., head() and tail() would not have a parameter.

Furthermore all your methods return a LinkedList and not a RecursiveList.

I have no idea why your methods use LinkedList since you don't use any special functions of the LinkedList, you should use the List<T> interface instead.

You create an awful lot of lists, why not use List.subList() instead of new List(x).remove(0).

Could you explain the difference between list.addAll(otherlist) and your RecursiveList.append(list,otherlist), only that yours is really slow?

I think this is some experiment trying to bring some functional aspects to Java, but I hope nobody will use it in any production code since it would be horribly slow.

Lets just go trough this.
RecursiveList.empty() = 1 new List
RecursiveList.tail() = 1 new List
RecursiveList.addAll() = 1 new List
RecursiveList.append(a,x) = call to addAll() + tail() for each element in a => sizeof(a)*2 new Lists
RecursiveList.reverse(a) = call to append() + addAll() + tail() + empty() for each element in a => sizeof(a)*(sizeof(a)*2) + sizeof(a)*3

So lets take a list with 10 elements, you would create 10*3 + 10*10*2 = 230 new lists just to reverse a list with 10 elements...

Quote

Generics allow type or method to operate on objects of various types while providing compile-time type safety. You might be used to the regualar generics such as LinkedList<Integer> i = new LinkedList<Integer>();. The only problem is that this LinkedList only allows us to hold Integers. In this tutorial, im going to give a generic class which allows you to hold any type.


I don't really get what you are trying to say here, LinkedList is in fact generic if you use LinkedList<String> you have a list that is for strings. If you really want a class that can hold any type use LinkedList without generic parameter or LinkedList<Object>.

I hope you learn that functional style programming is not always better and some time even far worse than standard OO style programming. Especially in languages that were not designed to be functional.
Was This Post Helpful? 0

#4 m-e-g-a-z  Icon User is offline

  • Winning
  • member icon


Reputation: 497
  • View blog
  • Posts: 1,453
  • Joined: 19-October 09

Posted 12 July 2010 - 04:43 PM

Thanks for the feedback :) This tutorial is designed to initially expand on basic knowledge others have on LinkedLists, Recursion and Generics.

I disagree with certain points especially this:

Quote

don't really get what you are trying to say here, LinkedList is in fact generic if you use LinkedList<String> you have a list that is for strings. If you really want a class that can hold any type use LinkedList without generic parameter or LinkedList<Object>.


You may want to read this - here

Wiki Says -

Quote

The following block of Java code illustrates a problem that exists when not using generics. First, it declares an ArrayList of type Object. Then, it adds a String to the ArrayList. Finally, it attempts to retrieve the added String and cast it to an Integer.
  List v = new ArrayList();
  v.add("test");
  Integer i = (Integer)v.get(0);        // Run time error


Although the code compiles without error, it throws a runtime exception (java.lang.ClassCastException) when executing the third line of code. This type of problem can be avoided by using generics and is the primary motivation for using generics.

Using generics, the above code fragment can be rewritten as follows:
  List<String> v = new ArrayList<String>();
  v.add("test");
  Integer i = v.get(0); // (type error)  Compile time error


The type parameter String within the angle brackets declares the ArrayList to be constituted of String (a descendant of the ArrayList's generic Object constituents). With generics, it is no longer necessary to cast the third line to any particular type, because the result of v.get(0) is defined as String by the code generated by the compiler.

Compiling the third line of this fragment with J2SE 5.0 (or later) will yield a compile-time error because the compiler will detect that v.get(0) returns String instead of Integer. For a more elaborate example, see [3].



I have given a generic class as an introducion into how you can define a class to hold any type since you wouldn't want to set the class to hold <String> and then pass Integers. Having formal type parameters allows for a more robust reusable class.

You can actually have a head() and tail() with parameters.

This does not make sense, why would you want to do that?

Quote

If you really want a class that can hold any type use LinkedList without generic parameter

This post has been edited by m-e-g-a-z: 13 July 2010 - 03:22 AM

Was This Post Helpful? 0
  • +
  • -

#5 Guest_Damokles*


Reputation:

Posted 13 July 2010 - 03:29 AM

View Postm-e-g-a-z, on 12 July 2010 - 03:43 PM, said:

Thanks for the feedback :) This tutorial is designed to initially expand on basic knowledge others have on LinkedLists, Recursion and Generics.


I don't know why you highlight LinkedList, your code would work the same if you used ArrayList everywhere. You don't go into what a LinkedList is so I don't think you should highlight it in your post. And my most important point would be that you make clear this is a showcase for functional style recursion that has serious performance issues in Java. I added altReverse() as an alternative that is recursive and only creates one copy of the input.

Quote

Quote

don't really get what you are trying to say here, LinkedList is in fact generic if you use LinkedList<String> you have a list that is for strings. If you really want a class that can hold any type use LinkedList without generic parameter or LinkedList<Object>.


I have given a generic class as an introducion into how you can define a class to hold any type since you wouldn't want to set the class to hold <String> and then pass Integers. Having formal type parameters allows for a more robust reusable class.


What I was trying to say is that your wording is ambiguous. It seemed to suggest that LinkedList itself was not real generic.

Quote

You can actually have a head() and tail() with parameters.

My point is that you try the functional style and not the OO way. In OO head() and tail() would be invoked an the object itself and not pass the object as parameter. That is why I changed the name of your class.

Here I rewrote your class, it uses static methods now. I also changed some of your methods. And use the interface List<T> instead of LinkedList.
I didn't change the semantics of your code so every method will create a new List and work with that instead of changing the passed list.
package foo;

import java.util.*;

public class ListFunctions {

	public static <T> List<T> listOf(T... x) {	
		return Arrays.asList(x);
	}
	
	public static <T> T head(List<T> m) {
		return m.get(0);
	}

	public static <T> List<T> tail(List<T> t) {		
		return new LinkedList<T>(t.subList(1, t.size()));
	}

	public static <T> List<T> addAll(T head, List<T> tail) {
		List<T> s = new LinkedList<T>();
		s.add(head);
		s.addAll(tail);
		return s;
	}
	
	public static <T> List<T> append(List<T> j, T head) {
		List<T> s = new LinkedList<T>();
		s.add(head);
		return j;
	}

	public static <T> List<T> reverse(List<T> k) {
		if (k.size() == 1)
			return k;
		else
			return append(reverse(tail(k)), head(k));
	}	
	
	public static <T> List<T> altReverse(List<T> k) {
		return altReverse(new ArrayList<T>(k), 0, k.size()-1);
	}
	
	public static <T> List<T> altReverse(List<T> a, int l, int r) {
		if (l>=r) return a;
		else {
			T temp = a.get(l);
			a.set(l, a.get(r));
			a.set(r, temp);
			return altReverse(a, ++l, --r);
		}
	}

	//just for completeness - not used any more
	public static <T> List<T> append(List<T> j, List<T> k) {
		j.addAll(k);
		return j;		
	}
}



import java.util.*;

import static foo.ListFunctions.*;

public class Testing {


	static List <Integer> makeR (int n)
	{
		if (n==0) return listOf(0);
		else return addAll(n,makeR(n-1));
	}

	static  List  <Integer> insertAscending (Integer n, List <Integer> m)
	{
		if (m.isEmpty()) return listOf(n);

		else if(n>head(m))
			return addAll(head(m),insertAscending(n,tail(m)));
		else return addAll(n,insertAscending(head(m),tail(m)));
	}

	static List <Integer> sortAscending (List <Integer> m)
	{
		if (m.isEmpty()) return m;
		else return insertAscending((head(m)), sortAscending(tail(m)));
	}

	public static void main(String [] args)
	{
		//List <Integer> m = makeR(Integer.parseInt(args[0]));
		List <Integer> m = makeR(50);
		System.out.println("List contains: "+m);
		System.out.println("List reversed: "+reverse(m));   
	}
}


Was This Post Helpful? 0

Page 1 of 1