[m-e-g-a-z]

Java Tutorial
Recursive Generic LinkedList

By m-e-g-a-z

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

[bcranger]

Good guide, I might try using some LinkedLists in the future

[m-e-g-a-z]

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