SinglyLinkedList Operations 


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

class SinglyLinkedList {
    private static Node head;

    private static void create(int[] data) {
        // create first Node
        head = new Node(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(data[i], null);
            last.setNext(newNode);
            // reset last node 
            last = newNode;
        }
    }

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

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

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

    private static int count() {
        if(head == null) {
            return 0;
        }
        Node temp = head;
        int counter = 0;
        while(temp != null) {
            counter++;
            // move next node 
            temp = temp.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 temp = head;
        int sum = 0;
        while(temp != null) {
            sum += temp.getData();
            // move next node 
            temp = temp.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 temp = head;
        int max = Integer.MIN_VALUE;
        while(temp != null) {
            if(temp.getData() > max) {
                max = temp.getData();
            }
            // move next node 
            temp = temp.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 temp = head;
        int min = Integer.MAX_VALUE;
        while(temp != null) {
            if(temp.getData() < min) {
                min = temp.getData();
            }
            // move next node 
            temp = temp.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 temp = head;
        while(temp != null) {
            if(temp.getData() == key) {
                return true;
            }
            // move next node 
            temp = temp.getNext();
        }
        return false;
    }

    private static boolean searchRecursive(Node head, int key) {
        if(head == null) {
            return false;
        }
        return head.getData() == key ? true : searchRecursive(head.getNext(), key);
    }

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

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

    private static void insertAfter(int data, int position) {
        Node newNode = new Node(data, null);
        if(head == null) {
            head = newNode;
            return;
        }
        Node temp = head;
        // If position is 0 or 1 then node will be inserted after 1st node
        for(int i = 0; i < position - 1 && temp.getNext() != null; i++) {
            temp = temp.getNext();
        }
        newNode.setNext(temp.getNext());
        temp.setNext(newNode);
    }

    private static void insertInSortedList(int data) {
        Node newNode = new Node(data, null);
        if(head == null) {
            head = newNode;
            return;
        }
        Node current, previous;
        current = previous = head;
        while(current != null && current.getData() < data) {
            previous = current;
            current = current.getNext();
        }
        // insert as first node 
        if(current == head) {
            newNode.setNext(head);
            head = newNode;
            return;
        }
        newNode.setNext(previous.getNext());
        previous.setNext(newNode);
    }

    private static boolean delete(int position) {
        // check list empty and validate input index 
        if(head == null || position <= 0) {
            return false;
        }
        // if we want to delete index 1 
        if(position == 1) {
            head = head.getNext();
            return true;
        }
        Node current, previous;
        current = previous = head;
        for(int i = 0; i < position -1 && current != null; i++) {
            previous = current;
            current = current.getNext();
        }
        if(current != null) {
            previous.setNext(current.getNext());
            return true;
        }
        return false; // input position exceeded the available nodes in list 
    }

    // Assuming list sorted in accending order 
    private static boolean isSorted() {
        if(head == null) {
            return true;
        }
        Node current, previous;
        current = previous = head;
        while(current.getNext() != null) {
            previous = current; 
            current = current.getNext();
            if(previous.getData() > current.getData()) {
                return false;
            }
        }
        return true;
    }

    private static void removeDuplicates() {
        if(head == null) {
            return;
        }
        Node current, previous;
        previous = head;
        current = previous.getNext();
        while(current != null) {
            if(previous.getData() != current.getData()) {
                previous = current;
                current = current.getNext();
                continue;
            }
            previous.setNext(current.getNext());
            current = current.getNext();
        }
    }

    private static void removeDuplicates2() {
        if(head == null) {
            return;
        }
        Node current = head;
        while(current != null && current.getNext() != null) {
            if(current.getData() == current.getNext().getData()) {
                current.setNext(current.getNext().getNext());
            } else {
             current = current.getNext();   
            }
        }
    }

    private static void reverse() {
        if(head == null) {
            return;
        }
        Node current = head;
        // Make fist node as last node 
        Node reverseList = null;
        Node temp;
        while(current != null) {
            temp = current;
            current = current.getNext();
            temp.setNext(reverseList);
            reverseList = temp;
        }
        // point new list to the head 
        head = reverseList;
    }

    private static void reverseRecursive(Node previousNode, Node currentNode) {
        if(currentNode != null) {
            reverseRecursive(currentNode, currentNode.getNext());
            currentNode.setNext(previousNode);
        } else {
            head = previousNode;
        }
    }

    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,2};
	    create(data);
	    display();
	    System.out.println();
	    displayRecursive(head);
	    System.out.println();
	    displayReverseRecursive(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));
	    System.out.println(key + " found : " + searchRecursive(head, key));
	    key = 100;
	    System.out.println(key + " found : " + search(key));
	    System.out.println(key + " found : " + searchRecursive(head, key));
	    insertAtFirst(1);
	    insertAtLast(33);
	    display();
	    System.out.println();
	    insertAfter(0, 0);
	    insertAfter(4, 4);
	    insertAfter(100, 100);
	    display();
	    System.out.println();
	    head = null;
	    for(int d : data) {
	        insertInSortedList(d);
	    }
	    display();
	    System.out.println("\nDeleted position 0 : " + delete(0));
	    System.out.println("Deleted position 1 : " + delete(1));
	    System.out.println("Deleted position 2 : " + delete(2));
	    System.out.println("Deleted position 20 : " + delete(20));
	    display();
	    System.out.println("\nIs sorted : " + isSorted());
	    System.out.println("Duplicate the list");
	    for(int d : data) {
	        insertInSortedList(d);
	    }
	    insertInSortedList(32);
	    insertInSortedList(32);
	    insertInSortedList(32);
	    insertInSortedList(32);
	    insertInSortedList(32);
	    display();
	    System.out.println("\nRemove duplicates.");
	    removeDuplicates2();
	    display();
	    System.out.println("\nReverse list.");
	    // reverse();
	    reverseRecursive(null, head);
	    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 int data;
	    private Node next;

	    private Node() {}

	    public Node(int data, Node next) {
	        this.data = data;
	        this.next = next;
	    }

	    // Setters and getters methods
	    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;
	    }
	}
}


Output :
 3 5 7 10 25 8 32 2
 3 5 7 10 25 8 32 2
 2 32 8 25 10 7 5 3
Total number of nodes : 8
Total number of nodes : 8
Sum of nodes : 92
Sum of nodes : 92
Max element : 32
Max element : 32
Min element : 2
Min element : 2
32 found : true
32 found : true
100 found : false
100 found : false
 1 3 5 7 10 25 8 32 2 33
 1 0 3 5 4 7 10 25 8 32 2 33 100
 2 3 5 7 8 10 25 32
Deleted position 0 : false
Deleted position 1 : true
Deleted position 2 : true
Deleted position 20 : false
 3 7 8 10 25 32
Is sorted : true
Duplicate the list
 2 3 3 5 7 7 8 8 10 10 25 25 32 32 32 32 32 32 32
Remove duplicates.
 2 3 5 7 8 10 25 32
Reverse list.
 32 25 10 8 7 5 3 2
Concat list.
 32 25 10 8 7 5 3 2 3 5 7 10 25 8 32 2
Merging 2 sorted list.
 2 2 3 3 3 4 5 5 6 7 7 8 8 10 25 32
Is loop? false

Is loop? true

Comments

Post a Comment

Popular posts from this blog

SQL basic interview question

Image
Question #1) What is SQL? Structured Query Language is a database tool which is used to create and access database to support software application. Question #2) What are tables in SQL? The table is a collection of record and its information at a single view. Question #3) What are different types of statements supported by SQL? There are 3 types of SQL statements 1) DDL (Data Definition Language):  It is used to define the database structure such as tables. It includes three statements such as Create, Alter, and Drop. Some of the DDL Commands are listed below CREATE : It is used for creating the table. 1 CREATE   TABLE &amp;amp;amp;nbsp;table_name 2 column_name1 data_type( size ), 3 column_name2 data_type( size ), 4 column_name3 data_type( size ), ALTER:  The ALTER table is used for modifying the existing table object in the database. ALTER TABLE table_name ADD column_name datatype OR ALTER TABLE table_name DROP ...
Read more

gsutil Vs Storage Transfer Service Vs Transfer Appliance

When transferring data from an on-premiss location, use gsutil When transferring data from another cloud storage provider, use storage transfer service gsutil is a Python application that lets you access Cloud Storage from the command line. You can use gsutil to do a wide range of bucket and object management tasks, including: Creating and deleting buckets. Uploading, downloading, and deleting objects. Listing buckets and objects. Moving, copying, and renaming objects. Editing object and bucket ACLs. gsutil performs all operations, including uploads and downloads, using HTTPS and transport-layer security (TLS). For a complete list of guides to completing tasks with gsutil, see  Cloud Storage How-to Guides . Storage Transfer Service is a product that enables you to: Move or backup data to a Cloud Storage bucket either from other cloud storage providers or from your  on-premises  storage. Move data from one Cloud Storage bucket to another, so that it is available to differe...
Read more