(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.