Double Linked List - All Operations

 Click Me

// The Double linked list node
class Node{
    int data;
    Node next;
    Node prev;
    
    Node(int x){
        this.data=x;
        this.next=null;
        this.prev=null;
    }
}

public class Main {
    
    // the head and tail of the linked list
    Node head;
    Node tail;
    
    // function to add a new node to the last of linked list
// Time Complexity - O(1), Space Complexity - O(1)
    public void addNode(int x){
        Node newNode = new Node(x);
        // if linked list is empty
        if(head==null){
            head=newNode;
            tail=newNode;
            return;
        }
        // else if linked list is not empty
        tail.next=newNode;
        newNode.prev=tail;
        tail=newNode;
    }
    
    // function to traverse the linked list from left to right
// Time Complexity - O(n), Space Complexity - O(1)
    public void traverseForward(){
        // if linked list is empty
        if(head==null){
            System.out.println("Linked list is empty");
            return;
        }
        // else if linked list is not empty
        Node temp=head;
        while(temp!=null){
            System.out.print(temp.data+" ");
            temp=temp.next;
        }
        System.out.println();
    }
    
    // function to traverse the linked list from right to left
// Time Complexity - O(n), Space Complexity - O(1)
    public void traverseBackward(){
        // if linked list is empty
        if(head==null){
            System.out.println("Linked list is empty");
            return;
        }
        // if linked list is not empty
        Node temp=tail;
        while(temp!=null){
            System.out.print(temp.data+" ");
            temp=temp.prev;
        }
        System.out.println();
    }
    
    // function to get total no of nodes present in linked list
// Time Complexity - O(n), Space Complexity - O(1)
    private int getCountOfNodes(){
        int count=0;
        Node temp=head;
        while(temp!=null){
            count++;
            temp=temp.next;
        }
        return count;
    }
    
    // function to insert a new node with value as 'data' in linked list at specified location 'loc'
// Time Complexity - O(n), Space Complexity - O(1)
    public void insertNodeByLoc(int data, int loc){
        
        int countOfNodes = getCountOfNodes();
        // check validity of loc
        if(loc<=0 || loc>countOfNodes+1){
            System.out.println("Not a valid location to insert");
            return;
        }
        
        // if loc is valid:
        
        Node newNode = new Node(data);
        
        
        // if insert at start
        if(loc==1){
            newNode.next=head;
            head.prev=newNode;
            head=newNode;
            return;
        }
        // if insert at end
        else if(loc==countOfNodes+1){
            tail.next=newNode;
            newNode.prev=tail;
            tail=newNode;
            return;
        }
        // if insert anywhere in between
        else{
            Node temp=head;
            // bring temp to one node before loc node
            for(int i=0;i<loc-2;i++){
                temp=temp.next;
            }
            // do the linking and unlinking
            newNode.next=temp.next;
            temp.next.prev=newNode;
            temp.next=newNode;
            newNode.prev=temp;
        }
        
    }
    
    // function to delete a node at specified location
// Time Complexity - O(n), Space Complexity - O(1)
    public void deleteNodeByLoc(int loc){
        // if linked list is empty
        if(head==null){
            System.out.println("Linked List is empty");
            return;
        }
        
        // else if linked list is not empty
        
        int countOfNodes = getCountOfNodes();
        // check if given loc is valid is not
        if(loc<=0 || loc>countOfNodes+1){
            System.out.println("Not a valid location to delete");
            return;
        }
        // if node to be deleted is head node
        if(loc==1){
            head=head.next;
            head.prev=null;
            return;
        }
        // if node to be deleted is tail node
        else if(loc==countOfNodes){
            tail=tail.prev;
            tail.next=null;
        }
        // if node to be deleted is anywhere in between
        else{
            // bring the temp node to one node before the node to be deleted
            Node temp=head;
            for(int i=0;i<loc-2;i++){
                temp=temp.next;
            }
            // here currentNode is the node to be deleted
            Node currentNode = temp.next;
            // do the linking and unlinking
            temp.next=currentNode.next;
            currentNode.next.prev=temp;
            return;
        }
        
    }
    
    // function to search for a node with given data 'x' and return that node if present
// Time Complexity - O(n), Space Complexity - O(1)
    public Node searchNode(int x){
        // if linked list is empty
        if(head==null){
            System.out.println("Linked List is empty");
            return null;
        }
        // else if linked list is not empty
        
        Node temp=head;
        // traverse through the linked list and see if the node with given data is there or not
        while(temp!=null){
            // if found then return that node
            if(temp.data==x){
                return temp;
            }
            temp=temp.next;
        }
        // if not found return null
        return null;
    }
    
    // function to delete a node only on the basis of the value given 
// Time Complexity - O(n), Space Complexity - O(1)
    public void deleteNodeByValue(int x){
        // if linked list is empty
        if(head==null){
            System.out.println("Linked list is empty");
            return;
        }
        // else if linked list is not empty
        
        // search for the node with given value
        Node nodeToDelete = searchNode(x);
        // if node with given value is not found in linked list
        if(nodeToDelete==null){
            System.out.println("Node with given data is not present in linked list");
            return;
        }
        // if node with given value is found in linked list:
        
        // if node to be deleted is head node
        if(nodeToDelete==head){
            head=head.next;
            head.prev=null;
            return;
        }
        
        // if node to be deleted is tail node
        else if(nodeToDelete==tail){
            tail = tail.prev;
            tail.next=null;
            return;
        }
        // if node to be deleted is anywhere in between head and tail node
        else{
            Node previousNode=nodeToDelete.prev;
            previousNode.next=nodeToDelete.next;
            nodeToDelete.next.prev=previousNode;
            return;
        }
        
        
    }
    
    // function to delete  complete linked list
// Time Complexity - O(n), Space Complexity - O(1)
    public void deleteCompleteLinkedList(){
        // if linked list is empty
        if(head==null){
            System.out.println("Linked List is already empty, hence can't delete Linked List");
            return;
        }
        // first we remove all the prev links
        Node temp=head;
        while(temp!=null){
            temp.prev=null;
            temp=temp.next;
        }
        // Now we make the head null adn tail null
        head=null;
        tail=null;
    }
    
    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.traverseForward();
       ll.traverseBackward();
       ll.insertNodeByLoc(0,5);
       ll.traverseForward();
       ll.traverseBackward();
       ll.deleteNodeByLoc(3);
       ll.traverseForward();
       ll.traverseBackward();
       System.out.println(ll.searchNode(1));
       ll.deleteNodeByValue(0);
       ll.traverseForward();
       ll.traverseBackward();
       ll.deleteCompleteLinkedList();
       ll.traverseForward();
       ll.traverseBackward();
       
    }

}

Output:

1 2 3 4 
4 3 2 1 
1 2 3 4 0 
0 4 3 2 1 
1 2 4 0 
0 4 2 1 
Node@6b884d57
1 2 4 
4 2 1 
Linked list is empty
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