Circular Single Linked List - All operations

 Click Me
// the linked list node
class Node{
    int data;
    Node next;
    Node(int x){
        this.data=x;
        this.next=null;
    }
}

public class Main {
   // head and tail of the linked list
    Node head;
    Node tail;
 
// function to add a new node at last of linked list
// Time Complexity - O(1) , Space Complexity - O(1)
    public void addNode(int x){
        Node newNode = new Node(x);
     
        if(head==null){
            head=newNode;
            tail=newNode;
            tail.next=head;
            return;
        }
        // else
        tail.next=newNode;
        tail=newNode;
        tail.next=head;
    }
 
// function to traverse the linked list
// Time Complexity - O(n) , Space Complexity - O(1)
    public void traverse(){
        if(head==null){
            System.out.println("Linked list is empty");
            return;
        }
        Node temp= head;
        do {
            System.out.print(temp.data+" ");
            temp=temp.next;
        }while(temp!=head);
        System.out.println();
        System.out.println("Next node of tail or head is : "+tail.next.data);
    }
 
// function to get the total no. of nodes present in linked list
// Time Complexity - O(n) , Space Complexity - O(1)
    public int getCountOfNodes(){
        int count=0;
        if(head==null){
            return count;
        }
     
        Node temp=head;
        do{
            count++;
            temp=temp.next;
        }while(temp!=head);
     
        return count;
    }
 
// function to insert a new node on the given loc
// Time Complexity - O(n) , Space Complexity - O(1)
    public void insertNodeByLoc(int data, int loc){
        if(head==null){
            System.out.println("Linked List is empty");
            return;
        }
        // else if linked list is not empty
     
        // Validate the loc
        int noOfNodes = getCountOfNodes();
     
        if(loc<=0 || loc>noOfNodes+1){
            System.out.println("Not a valid location to insert");
            return;
        }
     
        // if loc is valid
        Node temp=head;
        Node newNode = new Node(data);
     
        // if loc is start
        if(loc==1){
            head=newNode;
            newNode.next=temp;
            tail.next=head;
            return;
        }
        // if loc is end
        else if(loc==noOfNodes+1){
            addNode(data);
        }
        // if loc is anywhere between
        else{
            // bring the temp pointer to previous node
            for(int i=0;i<loc-2;i++){
                temp = temp.next;
            }
            newNode.next=temp.next;
            temp.next=newNode;
        }
     
    }
 
// function to delete a node at the given loc
// Time Complexity - O(n) , Space Complexity - O(1)
    public void deleteNodeByLoc(int loc){
        if(head==null){
            System.out.println("Linked List is empty");
            return;
        }
     
        int noOfNodes = getCountOfNodes();
     
        // check the validity of loc
     
        if(loc<=0 || loc>noOfNodes){
            System.out.println("Not a valid location to delete");
            return;
        }
     
        // if loc is a valid location to delete
     
        // if we have to delete the head node
     
        if(loc==1){
            head=head.next;
            tail.next=head;
            return;
        }
     
     
        Node temp=head;
        Node previous = null;
        // bring temp to node to be deleted and previous to one node behind the node to be deleted
        for(int i=0;i<loc-1;i++){
            previous=temp;
            temp=temp.next;
        }
     
        previous.next=temp.next;
        if(loc==noOfNodes){
            tail=previous;
        }
    }
 
// function to delete a node having given value
// Time Complexity - O(n) , Space Complexity - O(1)
    public void deleteNodeByValue(int data){
        if(head==null){
            System.out.println("Linked list is already empty");
            return;
        }
        Node temp = head;
        Node previous = null;
     
       do{
           // if data to be deleted found in linked list
           if(temp.data==data){
               break;
           }
           // if data to be deleted is not in current node
           previous=temp;
           temp = temp.next;
       }while(temp!=head);
     
       //check if the data to be deleted is at head node
       if(head.data==temp.data && temp.data==data){
           // this means we have to delete head node
           head=head.next;
           tail.next=head;
           return;
       }
     
       // if node to be deleted is last node
       else if(temp==tail){
           previous.next=tail.next;
           tail=previous;
           return;
       }
       // if the node to be deleted is nay node in between
       else{
           previous.next=temp.next;
           return;
       }
     
     
    }
 
// function to delete complete linked list
// Time Complexity - O(1) , Space Complexity - O(1)
    public void deleteCompleteLinkedList(){
        if(head==null){
            System.out.println("Linked list is empty, can't delete");
            return;
        }
        head=null;
        tail=null;
    }

// function to search for a node with the given value in Linked List
    public void searchNode(int x){
        if(head==null){
            System.out.println("Linked List is empty, can't search");
            return;
        }
        Node temp = head;
        int found=-1;
       do{
           if(temp.data==x){
               found=0;
               break;
           }
           temp=temp.next;
       }while(temp!=head);
     
       if(found==0){
           System.out.println("Node with data: "+x+" found in Linked List");
       }
       else{
           System.out.println("Node with data: "+x+" not found in Linked List");
       }
    }
 
    public static void main(String[] args) throws Exception {
        Main ll = new Main();
        ll.addNode(1);
        ll.addNode(2);
        ll.addNode(3);
        ll.addNode(4);
        ll.traverse();
        System.out.println(ll.getCountOfNodes());
        ll.insertNodeByLoc(0,3);
        ll.traverse();
        ll.deleteNodeByValue(0);
        ll.traverse();
        ll.deleteNodeByLoc(3);
        ll.traverse();
        ll.searchNode(3);
        ll.searchNode(4);
        ll.deleteCompleteLinkedList();
        ll.traverse();
    }
}


Output:

1 2 3 4 
Next node of tail or head is : 1
4
1 2 0 3 4 
Next node of tail or head is : 1
1 2 3 4 
Next node of tail or head is : 1
1 2 4 
Next node of tail or head is : 1
Node with data: 3 not found in Linked List
Node with data: 4 found in Linked List
Linked list is empty

Comments

Post a Comment

Popular posts from this blog

Binary Heap - Introduction

Image
#Image Credit - GeeksForGeeks Types of heap: Min Heap - every node is less than or equal to  its children(s) Max Heap - every node is more than or equal to its children(s) Operations on any heap : create insert extract/delete - we can extract/delete only the top node in any heap traverse delete entire heap get size of heap peek top of heap We should prefer implementing binary heap using arrays and not linked list, as during bottom to top heapify, in reaching the bottom rightmost node we take only 0(1) time in case of array but we take 0(n) time in case of linked list because first, we need to level order traverse the binary heap tree to get bottom-most rightmost element.  Heaps are used to efficiently implement:  Prim's Algorithm Heapsort Priority queue
Read more

Divide and Conquer - Introduction

Image
What is Divide and Conquer? Divide and Conquer is an algorithm paradigm in which we break down a given problem into smaller sub-problems of similar type until the sub-problems are small enough to be solved directly. The solution to these sub-problems are then combined to give a solution to the original problem.  Study the diagram below, it will then make more sense about what we do in Divide and Conquer : Where to Apply Divide and Conquer? The Divide and Conquer can be applied to all those problems that show Optimal Substructure property.  So, What is this Optimal Substructure property now? If we can break down a problem into similar sub-problems and the solution of these sub-problems can be used to create the solution of the whole problem, then that problem is said to have the Optimal Substructure property. For eg. : Fibonacci(n) = Fibonacci(n-1) + Fibonacci(n-2),    In this example, we can see that if we want to find the Fibonacci number at the nth place, we can br...
Read more

Bubble Sort

Time complexity - O(n^2)  || Space Complexity - O(1) Bubble sort is an inplace sorting algorithm, that means we do not any extra space while bubble sorting public class Main {     public static void main(String[] args) throws Exception {         int[] arr={1,4,4,5,6,2,3,90,120,43,0};                  System.out.println("UnSorted Array :");         for(int i=0;i<arr.length;i++){             System.out.print(arr[i]+" ");         }         System.out.println();         // bubble sort         for(int i=0;i<arr.length-1;i++){ // iterates through first to last cell             for(int j=0;j<arr.length-1-i;j++){ // inner loop controls swapping and extent to which swapping is to be performed in array     ...
Read more