(Part 3) Singly Linked List with Generified Node element

This post is the continuation of "Singly Linked List with Generified Node element - Part 2".

Sometimes you wish to reverse a Linked List.
Reversing the Singly Linked List with constant extra space is a little tricky matter.
This is a question generally asked in technical interviews as well :D
Here is a function for it.

    public boolean reverse()
    {
        temp = head;
        int i;
        if(head.next!=null)
        {
            try
            {
                node<E> temp2=head.next;
                node<E> temp3=head.next.next;
                tail = head;
                tail.next = null;
                while(true)
                {
                    temp2.next = head;
                    head = temp2;
                    if(temp3 != null) {temp2 = temp3;}
                    else {break;};
                    if(temp3.next !=null)    {temp3 = temp3.next;}
                    else            {temp3 = null;};
                }
                head = temp2;
                return true;
            }
            catch(Exception e)
            {
                e.printStackTrace();
                return false;
            }
        }
        else
        {
            return true;
        }
    } 

Well, this function basically traverses the list viewing three nodes at a time and reverses the node.next member variable of the middle node. It reverses the list using O(1) extra space.



These were all public methods exposed to the user for use. Now comes some private methods.These are not seen by the user but are required for the internal working of the class.

getNode(E elem) method is required to fetch the node element(first node element if multiple such nodes exists) of the Linked List which has element 'elem' same as the 'elem' passed as arguement.
Note: 'same as' means that true is returned when you call object1.equals(object2). More on this in my next post.

    private node<E> getNode(E e)
    {
        temp = head;
        boolean flag = false;
        int i;
        for (i=0; i<size-1 ; i++)
        {
            if (temp.elem.equals(e))
            {
                flag = true;
                break;    
            } 
            temp = temp.next;
        }
        if(flag ==true)
         {
            return temp;
        }
        else
        {
            return null;
        }

    }

Sometimes for testing purpose, you need to print all the elements in the Linked List. I constructed a function for the same.

    public void printAll()
    {
        temp = head;
        int i;
        //System.out.println("Call to Printall function initiated");
        System.out.println();
        //System.out.println("The first element is "+head.elem);
        System.out.println("Size of the list is "+size);
        for (i=0; i<size ; i++)
        {
            try
            {
                System.out.println(temp.elem);
            }
            catch (NullPointerException e)
            {
                e.printStackTrace();
                System.out.println(i);
            }
            if (i!=size-1) temp = temp.next;
        }
    } 

Now lets talk about a function which rarely comes into use but we you need it, you really really need it !!
This function returns an array of E type with elements which are in the list after the specified element (passed as arguement).

    public E[] getRest(E e)
    {
        E[] temp_array=(E[])Array.newInstance(e.getClass(),remaining(e));
        temp = this.getNode(e);
        int i;   
        int array_index=0;
        do
        {
            try
            {
                temp_array[array_index] = temp.elem;
            }
            catch (NullPointerException ex)
            {
                ex.printStackTrace();
                //System.out.println(i);
            }
            array_index++;
            //if (temp.next!=null) temp = temp.next;
        }
        while ((temp = temp.next) != null);
        return temp_array;
    }  

Note: The element passed as arguement is also included in the returned array.
Note: For getRest(E e) function, you will need to import java.lang.reflect.Array in your code.
Note: This function generates a compiler warning as i am casting an object of 'Object' Class (newInstance returns an object of Object Class) into (E[]). This is also known as unchecked casts. It generates a compile time warning. But it is type safe so don't worry and go ahead.

In this function, I retrieved the Class Object associated with the elem e and then passed it along with the required size in the newInstance method of 'Array' class to create an array of the required type and size.
After that, I just traversed to the list assigning the required elements to the newly created array.


That is it.
You are done.
For the complete code, go here.
Do post your comments about the post.

(Part 2) Singly Linked List with Generified Node element

This is the continuation of the post " Singly Linked List with Generified Node element - Part 1".

Sometimes we want to add an element at some specific index. For that, we need another function.

    public E addElem(E e,int index)
    {

        if(index ==0)
        {
            node<E> newNode = new node<E>();
            newNode.elem = e;
            newNode.next = head;
            head = newNode;
            this.size++;
        }
        else
        {
            temp = head;
            for (int i=0; i<index-1 ; i++)
            {
                 temp = temp.next;
            }
            node<E> newNode = new node<E>();
            newNode.next = temp.next;
            newNode.elem = e;
            temp.next = newNode;
            this.size++;
        }
        return e;
    } 

This function constructs a new node with the provided element, inserts it between the Linked List at the specified index by playing a little bit with the member variables of the adjoining nodes.
Again, we need to consider two cases:

1. The provided index is 0, i.e. the user wants to insert the new element at the begining of the list. In such a case, we need to modify the head variable.
2. The provided index is between 0(exclusive) and size-1(inclusive). In such a case, we construct a new node, change the 'next' variable of (index-1)th node to this new node, initialize 'next' of this new node to the (index+1)th node.

After storing your elements in the list, you do need to retrieve them and use them. So we do need a function which fetches the data from the Linked List.

    public E getElem(int index)
    {
            temp = head;
            for (int i=0; i<index ; i++)
            {
                 temp = temp.next;
            }
            return temp.elem;
    }

This function will traverse the list to reach the specified index, retrieve the node and return the element stored at it.


Sometimes you will need to know where in the list, a particular element is situated. You need a indexOf() function  for this.

    public int indexOf(E e)
    {
        temp = head;
        boolean flag = false;
        int i;
        for (i=0; i<size-1 ; i++)
        {
            if (temp.elem.equals(e))
            {
                flag = true;
                break;    
            } 
            temp = temp.next;
        }
        if(flag ==true)
        {
            return i;
        }
        else
        {
            return -1;
        }

    }

This function will traverse the list to find a node with 'elem' 'same as' the specified 'e' (passed as arguement).


Sometimes you need to know how many elements are remaining in the list after a particular element. You can construct a function for this as well :)

public int remaining(E e)
 {
  int tempindex = this.indexOf(e);
  int remainingnum = size - tempindex;
  return remainingnum;
 } 

Note: The node with 'elem' = e, is also counted.


It might happen that you want to remove a particular element in the Linked List and save some processing time when you are going through the list again and again. For this you need to make a remove function. Remove function comes in two flavours:

1. remove(E elem)
2. remove(int index)

remove(E elem) method removes a particular node whose element 'elem' is 'same as'  the 'elem' passed as arguement.
Note: 'same as' means that true is returned when you call object1.equals(object2). More on this in my next post.

    public E remove(E e)
    {
        temp = head;
        int i;
        E e_temp;
        boolean flag= false;
        node<E> temp2=head;

        for (i=0; i<size; i++)
        {
            if(temp.elem.equals(e))
            {
                flag = true;
                break;
            }
            temp2 = temp;
            temp = temp.next;
        }
        if (flag == true)
        {
            if (i ==0)
            {
                e_temp = head.elem;
                head = head.next;
                this.size--;
                return e_temp;
            }
            else if (i == size-1)
            {
                e_temp= tail.elem;
                tail = temp2;
                tail.next = null;
                this.size--;
                return e_temp;
            }
            else
            {
                temp2.next = temp.next;
                this.size--;
                return temp.elem;
            }
        }
        else
        {
            return null;
        }

    }

This function traverses the list to find the first occurence of the element 'e' and then takes change the pointers of the adjoining nodes to remove the node from the list. We have to take into account three cases.

1. The node to be removed is the head node.
2. The node to be removed is the tail node.
3. The node to be removed is any other node in between.

remove(int index) removes the element at index='index' (passed as arguement) in the function.
Note: Index starts from 0.

    public E remove(int index)
    {
        temp = head;
        int i;
        E e_temp;
        
        if(index == 0)
        {
            e_temp = head.elem;
            head = head.next;
        }
        else if(index == size-1)
        {
            e_temp = tail.elem;
            for (i=0; i<size-2; i++)
            {
                temp = temp.next;
            }
            tail = temp;
            tail.next = null;
        }
        else
        {
            for (i=0; i<index-1; i++)
            {
                temp = temp.next;
            }
            e_temp = temp.next.elem;
            temp.next = temp.next.next;
        }
        this.size--;
        return e_temp;
    } 

This function traverses the list to get to the specified index and then changes the pointers of the adjoining nodes to remove the node from the list. Again we have to take into account three cases.

1. The node to be removed is the head node.
2. The node to be removed is the tail node.
3. The node to be removed is any other node in between.

Go to the next post "Singly Linked List with Generified Node element - Part 3" for more function.