**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