CIRCULAR LINKED LIST

Circular Linked List :
A circular linked list is a linked list where the last element contains a pointer to the first element.

Sample Code (in Java) :

import java.util.Scanner;

class LLNode {
    int key;
    LLNode next;
    LLNode(int key) {
        this.key=key;
    }
}

public class LList {
    LLNode temp, first;
    int size;
   
    LList() {
        temp=null;
        first=null;
        size=0;
    }
   
    public void insert(int key) {
        LLNode data=new LLNode(key);
        if(first==null) {
            first=data;
            temp=data;
            temp.next=temp;
        }
        else {
            temp=first;
            while(temp.next!=first) {
                temp=temp.next;
            }
            temp.next=data;
            temp.next.next=first;
        }
        size++;
    }
   
    public void remove(int key) {
        if(size==0) {
            System.out.println("\nEmpty LL");
            return;
        }
        temp=first;
        if(temp.key==key) {
            first=first.next;
            size--;
            return;
        }
        else {
            while(temp.next!=null) {
                if(temp.next.key==key) {
                    if(temp.next.next==null) {
                        temp.next=null;
                        size--;
                        return;
                    }
                    temp.next=temp.next.next;
                    size--;
                    return;
                }
                temp=temp.next;
            }
        }
        System.out.println("\nElement Not Found");
    }
   
    public boolean hasLoop() {
        LLNode slow=first;
        LLNode fast=first;
        while(fast!=null) {
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow) {
                return true;
            }
        }
        return false;
    }
   
    public void disp() {
        temp=first;
        while(temp!=null) {
            System.out.println(temp.key);
            temp=temp.next;
        }
    }
   
    public static void main(String args[]) {
        Scanner sc=new Scanner(System.in);
        LList ll=new LList();
        while(true) {
            System.out.print("\n1. Insert\n2. Remove\n3. Display\n4. hasLoop\nCHOICE: ");
            int ch=sc.nextInt();
            switch(ch) {
                case 1:
                    System.out.println("\nEnter A Number: ");
                    int num=sc.nextInt();
                    ll.insert(num);
                    break;
                case 2:
                    System.out.println("\nEnter A Number: ");
                    num=sc.nextInt();
                    ll.remove(num);
                    break;
                case 3:
                    ll.disp();
                    break;
                case 4:
                    System.out.println(ll.hasLoop());
                    break;
                default :
                    System.exit(0);
            }
        }
    }
}

Binary Search Tree

Binary Search Tree (BST) :
Binary Search Tree is a binary tree in which each internal node X stores an element such that the elements stored on its left sub-tree are smaller or equal to X and elements stored on its right sub-tree are greater then X. It can be implemented using a linked data structure where each node is an object with 3 pointer fields. These pointer fields are left, right and parent and they correspond to left child, right child and parent respectively.
root : the node which don't have any parent element.
parent node : if  C and D are on left and right of A then A is their parent node.
child node : if  C and D are on left and right of A then they both are child nodes of node A.
leaf node : the node which don't have any child node.

Sample Code (in Java) :

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;

/********** BST **********/
class Node {
    Node parent, left, right;
    int data;
    Node(int data) {
        this.data=data;
    }
    public String toString() {
        return ""+data;
    }
}

public class BST {
    static Node root;
   
    /********** INSERT **********/
    public static void insert(int data) {
        root=insert(root,data);
    }
    public static Node insert(Node node,int data) {
        if(node==null) {
            node=new Node(data);
        }
        else if(data<node.data) {
            node.left=insert(node.left,data);
            node.left.parent=node;
        }
        else {
            node.right=insert(node.right,data);
            node.right.parent=node;
        }
        return node;
    }
   
    /********** DELETE **********/
    public static void swap(Node a, Node b) {
        if(a.parent==null) {
            root=b;
        }
        else if(a==a.left.parent) {
            a.left.parent=b;
        }
        else {
            a.right.parent=b;
        }
    }
    public static void delete(int data) {
        delete(root,data);
    }
    public static void delete(Node node,int data) {
        if(node==null){
            return;
        }
        else if(data==node.data) {
            if(node.left==null) {
                swap(node,node.left);
            }
            else if(node.right==null) {
                swap(node,node.right);
            }
            else {
                Node midNode= node.right;
                while(midNode.left!=null) {
                    midNode=midNode.left;
                }
                if(midNode.parent!=node) {
                    swap(midNode,midNode.right);
                    midNode.right=node.right;
                    midNode.right.parent=midNode;
                }
                swap(node,midNode);
                midNode.left=node.left;
                midNode.left.parent=midNode;
            }
        }
        else if(data<node.data) {
            delete(node.left,data);
        }
        else {
            delete(node.right,data);
        }
    }
   
    /********** LOOKUP **********/
    public static boolean lookup(int data) {
        return lookup(root,data);
    }
    public static boolean lookup(Node node,int data) {
        if(node==null)
            return false;
        else if(data==node.data) {
            return true;
        }
        else if(data<node.data) {
            return lookup(node.left,data);
        }
        else {
            return lookup(node.right,data);
        }
    }
   
    /********** SIZE **********/
    public static int size() {
        return size(root);
    }
    public static int size(Node node) {
        if(node==null) {
            return 0;
        }
        int leftSize=size(node.left);
        int rightSize=size(node.right);
        int size=leftSize+rightSize+1;
        return size;
    }
   
    /********** HEIGHT **********/
    public static int height() {
        return height(root);
    }
    public static int height(Node node) {
        if(node==null) {
            return 0;
        }
        int leftHeight=height(node.left);
        int rightHeight=height(node.right);
        int height=leftHeight>rightHeight?leftHeight+1:rightHeight+1;
        return height;
    }
   
    /********** MIN VALUE **********/
    public static int minVal() {
        return minVal(root);
    }
    public static int minVal(Node node) {
        if(node==null) {
            return 0;
        }
        Node cursor=node;
        while(cursor.left!=null) {
            cursor=cursor.left;
        }
        return cursor.data;
    }
   
    /********** MAX VALUE **********/
    public static int maxVal() {
        return maxVal(root);
    }
    public static int maxVal(Node node) {
        if(node==null) {
            return 0;
        }
        Node cursor=node;
        while(cursor.right!=null) {
            cursor=cursor.right;
        }
        return cursor.data;
    }
   
    /********** INORDER **********/
    public static void inOrder() {
        inOrder(root);
    }
    public static void inOrder(Node node) {
        if(node==null) {
            return;
        }
        inOrder(node.left);
        System.out.print(node.data+" ");
        inOrder(node.right);
    }
   
    /********** PATH **********/
    private static String path(int data) {
        return path(root,data);
    }
    static String path="";
    private static String path(Node node,int data) {
       
        if(node==null) {
            return null;
        }
        else if(data==node.data) {
            path=path+node.data;
            String path1=path;
            path="";
            return path1;
        }
        else if(data<node.data) {
            path=path+node.data+"->";
            return path(node.left,data);
        }
        else {
            path=path+node.data+"->";
            return path(node.right,data);
        }
    }
   
    /********** COMMON ANCESTOR **********/
    public static int LCA(int data1,int data2) {
        return LCA(root,data1,data2);
    }
    static int ancestor;
    public static int LCA(Node node,int data1,int data2) {
        if(node==null) {
            return 0;
        }
        if(data1<node.data || data2<node.data) {
            if(data1>node.data || data2>node.data) {
                ancestor=node.data;
                return ancestor;
            }
        }
        if(data1<node.data && data2<node.data) {
            return LCA(node.left,data1,data2);
        }
        else {
            return LCA(node.right,data1,data2);
        }
    }
   
    /********** LevelOrder **********/
    public static void LOT() {
        LOT(root);
    }
    public static void LOT(Node node) {
        Node temp;
        Queue queue=new LinkedList();
        if(node==null) {
            return;
        }
        queue.add(node);
        while(!queue.isEmpty()) {
            temp=(Node) queue.remove();
            System.out.print(temp.data+" ");
            if(temp.left!=null)
                queue.add(temp.left);
            if(temp.right!=null)
                queue.add(temp.right);
        }
        queue.removeAll(queue);
    }
   
    /********** LevelOrder ZIG ZAG **********/
    public static void LOTZigZag() {
        LOTZigZag(root);
    }
    public static void LOTZigZag(Node node) {
        Node temp;
        boolean LtoR=true;
        Stack currentLevel=new Stack();
        Stack nextLevel=new Stack();
        if(node==null) {
            return;
        }
        currentLevel.push(node);
        while(!currentLevel.isEmpty()) {
            temp=(Node) currentLevel.pop();
            if(temp!=null) {
                System.out.print(temp.data+" ");
                if(LtoR) {
                    nextLevel.push(temp.left);
                    nextLevel.push(temp.right);
                }
                else {
                    nextLevel.push(temp.right);
                    nextLevel.push(temp.left);
                }
            }
            if(currentLevel.isEmpty()) {
                System.out.print("\n");
                LtoR=!LtoR;
                Stack tempo=currentLevel;
                currentLevel=nextLevel;
                nextLevel=tempo;
            }
        }
    }
   
    /********** MAIN FUNCTION **********/
    public static void main(String args[]) {
        Scanner sc=new Scanner(System.in);
        BST bst=new BST();
        while(true) {
            System.out.print("\n*************\n     BST     \n*************\n  1. INSERT\n  2. DELETE\n  3. DISPLAY\n  4. SIZE\n  5. HEIGHT\n  6. MINVAL\n  7. MAXVAL\n  8. PATH\n  9. Ancestor\n  10.LOT\n  11. ZigZag\n*************\nCHOICE: ");
            int ch=sc.nextInt();
            switch(ch) {
                case 1:
                    System.out.print("\nEnter The Number: ");
                    int data=sc.nextInt();
                    insert(data);
                    break;
                case 2:
                    System.out.print("\nEnter The Number: ");
                    data=sc.nextInt();
                    delete(data);
                    break;
                case 3:
                    inOrder();
                    break;
                case 4:
                    System.out.println("\nSize: "+size());
                    break;
                case 5:
                    System.out.println("\nHeight: "+height());
                    break;
                case 6:
                    System.out.println("\nMinValue: "+minVal());
                    break;
                case 7:
                    System.out.println("\nMaxValue: "+maxVal());
                    break;
                case 8:
                    System.out.print("\nEnter The Number: ");
                    data=sc.nextInt();
                    System.out.println("\nPath: "+path(data));
                    break;
                case 9:
                    System.out.print("\nEnter The Numbers: ");
                    int data1=sc.nextInt();
                    int data2=sc.nextInt();
                    System.out.println("\nAncestor: "+LCA(data1,data2));
                    break;
                case 10:
                    LOT();
                    break;
                case 11:
                    LOTZigZag();
                    break;
                default:
                    System.exit(0);
            }
        }
    }
}

Linked List (basic)

Linked List:
A linked list is a data structure where each element contain a pointer to the next element.

Sample Code (in Java) :

import java.util.Scanner;

class LLNode {
    int key;
    LLNode next;
    LLNode(int key) {
        this.key=key;
    }
}

public class LL {
    LLNode temp, first;
    int size;
   
    LL() {
        temp=null;
        first=null;
        size=0;
    }
   
    public void insert(int key) {
        LLNode data=new LLNode(key);
        if(first==null) {
            first=data;
            temp=data;
        }
        else {
            temp=first;
            while(temp.next!=null) {
                temp=temp.next;
            }
            temp.next=data;
        }
        size++;
    }
   
    public void remove(int key) {
        if(size==0) {
            System.out.println("\nEmpty LL");
            return;
        }
        temp=first;
        if(temp.key==key) {
            first=first.next;
            size--;
            return;
        }
        else {
            while(temp.next!=null){
                if(temp.next.key==key) {
                    if(temp.next.next==null) {
                        temp.next=null;
                        size--;
                        return;
                    }
                    temp.next=temp.next.next;
                    size--;
                    return;
                }
                temp=temp.next;
            }
        }
        System.out.println("\nElement Not Found");
    }
   
    public void disp() {
        temp=first;
        while(temp!=null) {
            System.out.println(temp.key);
            temp=temp.next;
        }
    }
   
    public static void main(String args[]) {
        Scanner sc=new Scanner(System.in);
        LL ll=new LL();
        while(true) {
            System.out.print("\n1. Insert\n2. Remove\n3. Display\nCHOICE: ");
            int ch=sc.nextInt();
            switch(ch) {
                case 1:
                    System.out.println("\nEnter A Number: ");
                    int num=sc.nextInt();
                    ll.insert(num);
                    break;
                case 2:
                    System.out.println("\nEnter A Number: ");
                    num=sc.nextInt();
                    ll.remove(num);
                    break;
                case 3:
                    ll.disp();
                    break;
                default :
                    System.exit(0);
            }
        }
    }
}

Queues (basic)

Queues:
A queue is a data structure which implements FIFO(first-in-first-out) concept. The first entry in the queue is the first to come out. For eaxmple if we enter 1, 2, 3 in a queue, then 1 will be the first to come out followed by 2 then 3.

 Sample Code (in Java):

import java.util.Scanner;

public class Queues {
    Object arr[];
    int size, front, pos;
 
    Queues(int n) {
        size=n;
        pos=-1;
        arr=new Object[n];
    }
 
    //TO ENTER THE ELEMENTS IN THE QUEUE//
    public void enqueue(int num) {
        pos++;
        if(pos<size)
            arr[pos]=num;
        else
            System.out.println("\nQueue Is Full");
    }
 
    //TO REMOVE ELEMENTS FROM THE QUEUE//
    public void dequeue() {
        if(pos>-1) {
            System.out.println("\nDequed element: "+arr[0]);
            for(int i=0,j=i+1; i<size-1; i++, j++) {
                arr[i]=arr[j];
            }
            arr[pos]=null;
            pos--;
        }
        else
            System.out.println("\nEmpty Queue");    
    }
 
    //TO DISPLAY ELEMENTS PRESENT IN QUEUE//
    public void disp() {
        if(pos>-1){
            for(int i=pos; i>=0; i--) {
                System.out.println("|"+arr[i]+"|");
            }
        }
        else
            System.out.println("\nEmpty Queue");
    }
 
    //TO DISPLAY IF QUEUE IS EMPTY OR NOT//
    public void isEmpty() {
        if(pos==-1)
            System.out.println("\nEmpty");
        else
            System.out.println("\nNot Empty");
    }
 
    //main METHOD//
    public static void main(String args[]) {
        Scanner sc=new Scanner(System.in);
     
        System.out.print("\nEnter Size of Array: ");
        int n=sc.nextInt();
        Queues stack=new Queues(n);
        while(true) {
            System.out.print("\n1. Enqueue\n2. Dequeue\n3. Display\n4. IsEmpty\nCHOICE: ");
            int ch=sc.nextInt();
            switch(ch) {
                case 1:
                    System.out.print("Enter Number: ");
                    int num=sc.nextInt();
                    stack.enqueue(num);
                    break;
                case 2:
                    stack.dequeue();
                    break;
                case 3:
                    stack.disp();
                    break;
                case 4:
                    stack.isEmpty();
                    break;
                default:
                    System.exit(0);                  
            }
        }
    }
}

Stack (basic)

STACKS:
A stack is a datastructure which folows LIFO(last-in-first-out) concept. i.e. the last element pushed in the stack is the first one to pop out. For example if the last card we put on the deck of cards is an ace, then the first card we pulled from the tp is the same

                                   

Sample Code (in Java) :

import java.util.Scanner;

public class Stack {
    Object arr[];
    int size, top;
 
    //CONSTRUCTOR//
    Stack(int n) {
        size=n;
        top=-1;
        arr=new Object[size];
    }
 
    //PUSH THE ELEMENT INTO STACK//
    public void push(int n) {
        top++;
        if(top<size) {
            arr[top]=n;
        }
        else
            System.out.println("\nSTACK Is Full");
    }
 
    //POP THE ELEMENT FROM STACK//
    public void pop() {
        if(top>-1) {
            top--;
            System.out.println("\nDeleted Element: "+arr[top+1]);
        }
        else
            System.out.println("\nEmpty Stack");
    }
 
    //DISPLAY THE ELEMENTS IN STACK//
    public void disp() {
        if(top>-1) {
            for(int d=top; d>=0; d--) {
                System.out.println("|"+arr[d]+"|");
            }
        }
        else
            System.out.println("\nEmpty Stack");
    }
 
    //DISPLAY THE PEEK ELEMENT//
    public void peek() {
        if(top>-1)
            System.out.println("\nPeek Element: "+arr[top]);
        else
            System.out.println("\nEmpty Stack");
    }
 
    //DISPLAYS IF STACK IS EMPTY OR NOT//
    public void isEmpty() {
        if(top==-1)
            System.out.println("\nEmpty");
        else
            System.out.println("\nNot Empty");
    }
 
    //main METHOD//
    public static void main(String args[]) {
        Scanner sc=new Scanner(System.in);
     
        System.out.print("\nEnter Size of Array: ");
        int n=sc.nextInt();
        Stack stack=new Stack(n);
        while(true) {
            System.out.print("\n1. Push\n2. Pop\n3. Display\n4. Peek\n5. IsEmpty\nCHOICE: ");
            int ch=sc.nextInt();
            switch(ch) {
                case 1:
                    System.out.print("Enter Number: ");
                    int num=sc.nextInt();
                    stack.push(num);
                    break;
                case 2:
                    stack.pop();
                    break;
                case 3:
                    stack.disp();
                    break;
                case 4:
                    stack.peek();
                    break;
                case 5:
                    stack.isEmpty();
                    break;
                default:
                    System.exit(0);                  
            }
        }
    }
}