Question

a.   Write the separate function to delete the head node and tail node of a singly linked list in java programming language?

b.   Write the separate function to delete the head node and tail node of a doubly linked list in java programming language?

c.   Write the best and worst case of the following sort algorithms.

i.   Selection sort
ii.   Bubble sort
iii.   Insertion sort
iv.   Merge sort

Answer 1

singly liked list

public void deleteSLL() {

        //Checks if the list is empty
        if(head == null) {
            System.out.println("List is empty");
            return;
        }
        else {
          
            head=head.next; //remove head and assign head to the node pointing next to head.
          
            if(head.next==null) // list contain two elements.
                    head=null;
            else if(head != tail ) { //Checks whether the list contains more than one element.
                Node current = head;
                //Loop through the list till the second last element such that current.next is pointing to tail
                while(current.next != tail) {
                    current = current.next;
                }
                //Second last element will become new tail of the list
                tail = current;
                tail.next = null;
            }
            //If the list contains only one element
            //Then it will remove it and both head and tail will point to null
            else {
                head = tail = null;
            }
        }
    }

Doubly linked list

public void deleteDLL() {
        //Checks whether list is empty
        if(head == null) {
            return;
        }
        else {
          
            head=head.next ; //remove head.
            if(head.next==null) // list contain two elements.
                    head=null;
             //Checks whether the list contains only one node
            else if(head != tail) {
                //Previous node to the tail will become new tail
                tail = tail.previous;
                //Node next to current tail will be made null
                tail.next = null;
            }
            //If the list contains only one element
            //Then it will remove node and now both head and tail will point to null
            else {
                head = tail = null;
            }
        }
    }