Circular LinkedList Operations

No node can have null in circular linked list.

class CircularSinglyLinkedList {
    private static Node head;
    
    private static void create(int[] data) {
        // if data is empty early return
        if(data.length == 0) {
            return;
        }
        // create first node 
        head = new Node(data[0], null);
        // point next as self
        head.setNext(head);
        Node last = head;
        // add node 2 to n
        for(int i = 1; i < data.length; i++) {
            Node newNode = new Node(data[i], head);
            last.setNext(newNode);
            last = newNode;
        }
    }
    
    private static void display() {
        if(head == null) {
            return;
        }
        Node current = head;
        do {
            System.out.print(" " + current.getData());
            current = current.getNext();
        } while(current != head);
    }
    
    private static void displayRecursive(Node current, boolean flag) {
        if(current != head || flag) {
            flag = false;
            System.out.print(" " + current.getData());
            displayRecursive(current.getNext(), false);
        }
    }
    
    private static void insertFirst(int data) {
        Node newNode = new Node(data, head);
        // if no previous data
        if(head == null) {
            head = newNode;
            head.setNext(head);
            return;
        }
        // point last node to new node
        Node last = head;
        while(last.getNext() != head) {
            last = last.getNext();
        }
        last.setNext(newNode);
        // point head to new Node
        head = newNode;
    }
    
    private static void insertLast(int data) {
        Node newNode = new Node(data, head);
        // if No list availale 
        if(head == null) {
            head = newNode;
            head.setNext(head);
            return;
        }
        // point last to last Node
        Node last = head;
        while(last.getNext() != head) {
            last = last.getNext();
        }
        last.setNext(newNode);
    }
    
    private static void insertAfter(int data, int pos) {
        // insert at head 
        if(pos == 0) {
            insertFirst(data);
            return;
        }
        // point current to pos 
        Node current = head;
        for(int i = 1; i < pos && current.getNext() != head; i++) {
            current = current.getNext();
        }
        Node newNode = new Node(data, head);
        if(current.getNext() != head) {
            // insert in middle
            newNode.setNext(current.getNext());
        }
        current.setNext(newNode);   
    }
    
    private static int deleteFirst() {
        // if no nodes, return -1
        if(head == null) {
            return -1;
        }
        // point last node 
        Node last = head;
        while(last.getNext() != head) {
            last = last.getNext();
        }
        int x = head.getData();
        // if there was only 1 Node
        if(head == last) {
            head = null;
        } else {
            // set new head
            head = head.getNext();
            // set new last.next 
            last.setNext(head);
        }
        return x;
    }
    
    private static int deleteLast() {
        // if no nodes, return -1
        if(head == null) {
            return -1;
        }
        // point last node 
        Node last = head;
        Node previous = head;
        while(last.getNext() != head) {
            previous = last;
            last = last.getNext();
        }
        int x = last.getData();
        // if there was only 1 Node
        if(previous == last) {
            head = null;
        } else {
            // set new head
            previous.setNext(last.getNext());
        }
        return x;
    }
    
    private static int deleteAt(int pos) {
        // if no nodes 
        if(head == null) {
            return -1;
        } else if(pos <= 1) {
            return deleteFirst();
        } else {
            // delete middle or last element 
            Node current = head;
            // point current to (pos - 1)th Node
            for(int i = 1; i < pos - 1 && current.getNext() != head; i++) {
                current = current.getNext();
            }
            // pos is out of range 
            if(current.getNext() == head) {
                return -1;
            }
            int x = current.getNext().getData();
            current.setNext(current.getNext().getNext());
            return x;
        }
    }
    
    public static void main(String[] args) {
        int[] data = new int[] {3,5,7,10,25,8,32};
        System.out.println("Create list");
        create(data);
        display();
        System.out.println("\nDisplay list using recursive method");
        displayRecursive(head, true);
        System.out.println("\nInsert first");
        insertFirst(2);
        display();
        System.out.println("\nInsert after 0th position");
        insertAfter(/*data=*/1, /*pos=*/0);
        display();
        System.out.println("\nInsert last");
        insertLast(33);
        display();
        System.out.println("\nInsert after 34th position");
        insertAfter(/*data=*/34, /*pos=*/34);
        display();
        System.out.println("\nDelete first : " + deleteFirst());
        System.out.println("Delete 1st node : " + deleteAt(/*pos=*/1));
        System.out.println("Delete 3rd node : " + deleteAt(/*pos=*/3));
        System.out.println("Delete last : " + deleteLast());
        System.out.println("Delete 34rth node : " + deleteAt(/*pos=*/34));
        display();
    }
    
    private static class Node {
        private int data;
        private Node next;
        public Node(int data, Node next) {
            this.data = data;
            this.next = next;
        }
        private void setData(int data) {
            this.data = data;
        }
        private void setNext(Node next) {
            this.next = next;
        }
        private int getData() {
            return data;
        }
        private Node getNext() {
            return next;
        }
    }
}

Output
Create list
 3 5 7 10 25 8 32
Display list using recursive method
 3 5 7 10 25 8 32
Insert first
 2 3 5 7 10 25 8 32
Insert after 0th position
 1 2 3 5 7 10 25 8 32
Insert last
 1 2 3 5 7 10 25 8 32 33
Insert after 34th position
 1 2 3 5 7 10 25 8 32 33 34
Delete first : 1
Delete 1st node : 2
Delete 3rd node : 7
Delete last : 34
Delete 34rth node : -1
 3 5 10 25 8 32 33

Comments

Popular posts from this blog

gsutil Vs Storage Transfer Service Vs Transfer Appliance

SQL basic interview question