Doubly LinkedList Operations

Need to run and correct few errors in output

import java.util.*;
import java.lang.*;
import java.io.*;

class SinglyLinkedList {
    private static Node head;
    private static Node last;

    private static void create(int[] data) {
        // create first Node
        head = new Node(null, data[0], null);
        // if only single element 
        if(data.length == 1) {
            return;
        }
        Node last = head;
        for(int i = 1; i < data.length; i++) {
            Node newNode = new Node(last, data[i], null);
            last.setNext(newNode);
            // reset last node 
            last = newNode;
        }
        SinglyLinkedList.last = last;
    }

    private static void display() {
        if(head == null) {
            System.out.println("No nodes to print in linkedlist");
            return;
        }
        Node current = head;
        while(current != null) {
            System.out.print(" " + current.data);
            // move next node 
            current = current.getNext();
        }
    }

    private static void displayRecursive(Node head) {
        if(head == null) {
            return;
        }
        System.out.print(" " + head.getData());
        displayRecursive(head.getNext());
    }

    private static int count() {
        if(head == null) {
            return 0;
        }
        Node current = head;
        int counter = 0;
        while(current != null) {
            counter++;
            // move next node 
            current = current.getNext();
        }
        return counter;
    }

    private static int countRecursive(Node head) {
        if(head == null) {
            return 0;
        }
        return 1 + countRecursive(head.getNext());
    }

    private static int sum() {
        if(head == null) {
            return 0;
        }
        Node current = head;
        int sum = 0;
        while(current != null) {
            sum += current.getData();
            // move next node 
            current = current.getNext();
        }
        return sum;
    }

    private static int sumRecursive(Node head) {
        if(head == null) {
            return 0;
        }
        return head.getData() + sumRecursive(head.getNext());
    }

    private static int max() {
        if(head == null) {
            return 0;
        }
        Node current = head;
        int max = Integer.MIN_VALUE;
        while(current != null) {
            if(current.getData() > max) {
                max = current.getData();
            }
            // move next node 
            current = current.getNext();
        }
        return max;
    }

    private static int maxRecursive(Node head) {
        if(head == null) {
            return Integer.MIN_VALUE;
        }
        int max = maxRecursive(head.getNext());
        return max > head.getData() ? max : head.getData();
    }

    private static int min() {
        if(head == null) {
            return 0;
        }
        Node current = head;
        int min = Integer.MAX_VALUE;
        while(current != null) {
            if(current.getData() < min) {
                min = current.getData();
            }
            // move next node 
            current = current.getNext();
        }
        return min;
    }

    private static int minRecursive(Node head) {
        if(head == null) {
            return Integer.MAX_VALUE;
        }
        int min = minRecursive(head.getNext());
        return min < head.getData() ? min : head.getData();
    }

    private static boolean search(int key) {
        if(head == null) {
            return false;
        }
        Node left = head;
        Node right = last;
        while(left != right) {
            if(left.getData() == key || right.getData() == key) {
                return true;
            }
            // move next node 
            left = left.getNext();
            right = right.getPrev();
        }
        return false;
    }

    private static void insertAtFirst(int data) {
        Node newNode = new Node(null, data, head);
        head.setPrev(newNode);
        head = newNode;
    }

    private static void insertAtLast(int data) {
        Node newNode = new Node(last, data, null);
        if(head == null) {
            head = newNode;
            return;
        }
        last.setNext(newNode);
        last = newNode;
    }

    private static void insertAfter(int data, int position) {
        if(head == null) {
            head = new Node(null, data, null);;
        } else if(position == 0) {
            // insert before head
            insertAtFirst(data);
        } else {
            Node current = head;
            // If position is 0 or 1 then node will be inserted after 1st node
            for(int i = 1; i < position && current.getNext() != null; i++) {
                current = current.getNext();
            }
            // set data and newNode's prev to current node 
            Node newNode = new Node(current, data, null);
            // set newNode's next to next node
            newNode.setNext(current.getNext());
            if(current.getNext() != null) {
                newNode.getNext().setPrev(newNode);
            }
            current.setNext(newNode);   
        }
    }

    private static void insertInSortedList(int data) {
        Node newNode = new Node(null, data, null);
        if(head == null) {
            // return new node if list is empty
            head = newNode;
        } else if(head.getData() >= data) {
            // add to head if new element is smaller than head
            newNode.setNext(head);
            head.setPrev(newNode);
            head = newNode;
        } else {
            //In a loop, find the appropriate node after which the input node is to be inserted.
            Node current = head;
            while(current.getNext() != null && current.getNext().getData() < data) {
                current = current.getNext();
            }
            newNode.setPrev(current);
            newNode.setNext(current.getNext());
            newNode.getPrev().setNext(newNode);
            if(newNode.getNext() != null) {
                newNode.getNext().setPrev(newNode);   
            }
        }
    }

    private static int deleteAt(int position) {
        // check list empty and validate input index 
        if(head == null || position <= 0 || position > count()) {
            return -1;
        }
        Node current = head;
        for(int i = 1; i < position; i++) {
            current = current.getNext();
        }
        int x = current.getData();
        // delete first node
        if(current == head) {
            if(head.getNext() == null) {
                // only node in the list
                head = null;
            } else {
                // More node following first node
                head = head.getNext();
                head.setPrev(null);
            }
        } else {
            if(current.getNext() != null) {
                // step for middle node 
                current.getNext().setPrev(current.getPrev());
            } 
            // delete last node 
            current.getPrev().setNext(current.getNext());
        }
        return x;
    }

    // Assuming list sorted in accending order 
    private static boolean isSorted() {
        // detect early return | return true if no node or single node
        if(head == null || head.getNext() == null) {
            return true;
        }
        Node current = head.getNext();
        while(current != null) {
            // return false if previous element is greater than following element 
            if(current.getPrev().getData() > current.getData()) {
                return false;
            }
            current = current.getNext();
        }
        return true;
    }

    private static void removeDuplicates() {
        // early return 
        if(head == null || head.getNext() == null) {
            return;
        }
        // reaching here means we have atleast 2 nodes
        Node current = head.getNext();
        while(current != null) {
            if(current.getPrev().getData() == current.getData()) {
               current.getPrev().setNext(current.getNext());
               if(current.getNext() != null) {
                   current.getNext().setPrev(current.getPrev());
               }
            }
            current = current.getNext();
        }
    }

    private static void reverse() {
        Node temp = head;
        head = last;
        last = head;
    }

    private static Node concat(Node first, Node second) {
        if(first == null) {
            return second;
        }
        if(second == null) {
            return first;
        }
        Node current = first;
        while(current.getNext() != null) {
            current = current.getNext();
        }
        current.setNext(second);
        return first;
    }

    private static Node mergeSortedList(Node first, Node second) {
        if(first == null) {
            return second;
        }
        if(second == null) {
            return first;
        }
        Node sorted;
        if(first.getData() < second.getData()) {
            sorted = first;
            first = first.getNext();
        } else {
            sorted = second;
            second = second.getNext();
        }
        Node temp = sorted;
        while(first.getNext() != null && second.getNext() != null) {
            if(first.getData() < second.getData()) {
            temp.setNext(first);
            first = first.getNext();
            } else {
                temp.setNext(second);
                second = second.getNext();
            }
            temp = temp.getNext();
        }
        if(first.getNext() != null) {
            temp.setNext(first);
        }
        if(second.getNext() != null) {
            temp.setNext(second);
        }
        return sorted;
    }
    
    private static boolean isLoop(Node list) {
        Node slow, fast;
        slow = fast = list;
        do {
            slow = slow.getNext();
            fast = fast.getNext();
            fast = fast != null ? fast.getNext() : fast;
        } while(slow != null && fast != null && slow != fast);
        return slow == fast;
    }
    
    public static void main (String[] args) {
        int[] data = new int[] {3,5,7,10,25,8,32};
        System.out.println("Display list");
        create(data);
        display();
        // System.out.println("\nDisplay list recursive method");
        // displayRecursive(head);
        // System.out.println("\nTotal number of nodes : " + count());
        // System.out.println("Total number of nodes : " + countRecursive(head));
        // System.out.println("Sum of nodes : " + sum());
        // System.out.println("Sum of nodes : " + sumRecursive(head));
        // System.out.println("Max element : " + max());
        // System.out.println("Max element : " + maxRecursive(head));
        // System.out.println("Min element : " + min());
        // System.out.println("Min element : " + minRecursive(head));
        // int key = 32;
        // System.out.println(key + " found : " + search(key));
        // key = 100;
        // System.out.println(key + " found : " + search(key));
        // System.out.println("Insert 2");
        // insertAtFirst(2);
        // display();
        // System.out.println("\nInsert 33 at last");
        // insertAtLast(33);
        // display();
        // System.out.println("\nInsert 1 after 0th node");
        // insertAfter(/*data=*/1, /*pos=*/0);
        // display();
        // System.out.println("\nInsert 4 after 3rd node");
        // insertAfter(4, 4);
        // display();
        // System.out.println("\nInsert 100 after 100th node");
        // insertAfter(100, 100);
        // display()
        // System.out.println("\nIs sorted : " + isSorted());
        System.out.println("\nCreate and display sorted list");
        head = null;
        for(int d : data) {
            insertInSortedList(d);
        }
        display();
        System.out.println("\nIs sorted : " + isSorted());
        System.out.println("\nDeleted position 0 : " + deleteAt(0));
        System.out.println("Deleted position 1 : " + deleteAt(1));
        System.out.println("Deleted position 2 : " + deleteAt(2));
        System.out.println("Deleted position 20 : " + deleteAt(20));
        display();
        System.out.println("\nDuplicate the list");
        for(int d : data) {
            insertInSortedList(d);
        }
        insertInSortedList(32);
        insertInSortedList(32);
        insertInSortedList(32);
        insertInSortedList(32);
        insertInSortedList(32);
        display();
        System.out.println("\nRemove duplicates.");
        removeDuplicates();
        display();
        //System.out.println("\nReverse list.");
        //reverse();
        //display();
	    System.out.println("\nConcat list.");
	    Node temp = head;
	    create(data);
	    head = concat(temp, head);
	    display();
	    System.out.println("\nMerging 2 sorted list.");
	    head = null;
	    for(int d : data) {
	        insertInSortedList(d);
	    }
	    temp = head;
	    head = null;
	    data = new int[] {4,5,3,6,2,7,8,9,3};
	    for(int d : data) {
	        insertInSortedList(d);
	    }
	    head = mergeSortedList(temp, head);
	    display();
	    System.out.println("\nIs loop? " + isLoop(head));
	    // Create loop
	    Node temp1 = head.getNext();
	    Node temp2 = head.getNext().getNext().getNext().getNext().getNext().getNext().getNext()
	    .getNext().getNext().getNext().getNext().getNext().getNext().getNext().getNext();
	    temp2.setNext(temp1);
	    System.out.println("\nIs loop? " + isLoop(head));
	}

	private static class Node {
	    private Node prev;
	    private int data;
	    private Node next;
	    private Node() {}
	    public Node(Node prev, int data, Node next) {
	        this.prev = prev;
	        this.data = data;
	        this.next = next;
	    }
	    // Setters and getters methods
	    public Node getPrev() {
	        return prev;
	    }
	    public void setPrev(Node prev) {
	        this.prev = prev;
	    }
	    public int getData() {
	        return data;
	    }
	    public void setData(int data) {
	        this.data = data;
	    }
	    public Node getNext() {
	        return next;
	    }
	    public void setNext(Node next) {
	        this.next = next;
	    }
	}
}

Comments

Popular posts from this blog

SQL basic interview question

gsutil Vs Storage Transfer Service Vs Transfer Appliance