Stack

Stack is a data structure in which last element inserted is the first to come out, Last In First Out (LIFO).

Static Stack is implemented with array, and pointer (end) for inserting and removing element from the array. Stack has pushpopdisplay methods.

class stk{
    int data[];
    int top;
    public stk(){
        data = new int[10];
        top = -1;
    }
    public void push(int x){
        if(top<10){
            ++top;
            data[top] = x;
        }
    }
    public void pop(){
        if(top>-1){
            System.out.println("Popped: "+stk[top]);
            --top 
        }
    }
}

Queue

Queue is a data structure in which first element inserted is the first element to come out first (FIFO).

Static queue is implemented using an array and two pointers (ends): rear and front. Elements are inserted from rear end and removed from front end.

class qu{
    int rear, front;
    int data[];
    public qu(){
        rear = -1;
        front = 0;
        data = new int[10];
    }
    public void insert(int a){
        if(rear <10){
            ++rear;
            data[rear] = a;
        }
    }
    public void remove(){
        if(rear == -1){
            System.out.println("Removed: "+data[front]);
            ++front;
        }
    }
}

Link List

This code snippet shows how to create a simple linked list with very few nodes. A node class is defined, it has two attributes: data and next; methods: two constructors, and method to get value stored in a node.

class node{
    int data;
    node next;
    public node(int d){
        data = d;
        next = null;
    }
    public node(){
        data = 0;
        next = null;
    }
    public int getData(){
        return data; 
    }
}

Another class Linked_LIST is defined with objects of node class as attributes, a constructor, method to insert data after given node, method to delete node after given node.

class Linked_LIST{
    node n1,n2,n3,n4,n5;
    public Linked_LIST(){
        n1 = new node(33);
        n2 = new node(44);
        n3 = new node(55);
        n4 = new node(66);
        n5 = new node(99);
        n1.next = n2;
        n2.next = n3;
        n3.next = n4;
        n4.next = n5; 
    }
    public void insertAfter(int p, int d){
        int i; 
        node t = n1; 
        for(i=1;i<p;i++){t = t.next;}
        node nn = new node(d);
        nn.next = t.next; 
        t.next = nn;
    }
    public void deleteAfter(int p){
        int i; 
        node t = n1; 
        for(i=1;i<p;i++){t = t.next;}
        node temp = t.next;
        t.next = temp.next;
        temp = null;
    }
    public void show(){
        node t; int i=1;
        for(t = n1; t!=null;t=t.next){
            System.out.println(i+" : "+t.getData());
            ++i;
        }
    }
}
class Linked_List_Demo{
    public static void main(String[] owl){
        Linked_LIST l1 = new Linked_LIST();
        l1.show();
        l1.insertAfter(2, 200);
        l1.show();
        l1.deleteAfter(2);
        l1.show();
    }
}

Circular list

In circular List the insertion is possible even the end of the list is reached and empty positions are left in the beginning of the list.

class cq{
    int rear;
    int counter;
    int front;
    String[] data;
    public cq(){
        counter = 0;
        front = 0;
        rear = -1;
        data = new String[5];
    }
    public void insert(String o){
        if(rear < counter){
            rear = (rear+1)%5;
            data[rear] = o; 
            ++counter;
        }
    }
    public void remove(){
        if(counter !=0){
            System.out.println("Removed Item: "+data[front]);
            front = (front+1)%5;
            --counter;
        }
    }
    public void show(){
        int i=front;
        do{
            System.out.println("Data at "+i
            +" is:  "+data[i]);
            i=(i+1)%5;
        }while(i!=rear);
    }
    public static void main(String[] aargs){
        cq c = new cq();
        c.insert("chair");
        c.insert("bench");
        c.insert("desk");
        c.show();
        c.insert("sofa");
        c.insert("Dinosaur");
        c.insert("tea table");
        c.show();
    }
}
Output:
Data at 0 is:  chair
Data at 1 is:  bench
Data at 0 is:  tea table
Data at 1 is:  bench
Data at 2 is:  desk
Data at 3 is:  sofa
Data at 4 is:  Dinosaur

MenuDriven Example

 

import java.util.*;
class menuDri{
    public static void main(String [] aaaaaaaaaaa){
        int op;
        String str1="Tiger";
        Scanner sc = new Scanner(System.in);
        while(true){
            System.out.println("\n1. Enter String ");
            System.out.println("2. Display Entered String in Reverse ");
            System.out.println("3. Display Length of Entered String ");
            System.out.println("4. Exit ");
            System.out.println("Enter Your Choice: ");
            op = sc.nextInt();
            switch(op){
                case 1: System.out.println("Enter String: ");
                str1 = sc.next();
                break;
                case 2: System.out.println("Reverse of "+str1);
                    for(int i=str1.length()-1;i>=0;i--)
                        System.out.print(str1.charAt(i));
                break;
                case 3:System.out.println("Length of "+str1+" is "+str1.length());
                break; 
                default: 
                sc.close();
                System.exit(0);
                break;
            }
        }
    }
}

MenuDriven Circular Queue

 

import java.util.*;
class cp_menu{
    int rear;
    int counter;
    int front;
    String[] data;
    public cp_menu(){
        counter = 0;
        front = 0;
        rear = -1;
        data = new String[5];
    }
    public void insert(String o){
        if(rear < counter){
            rear = (rear+1)%5;
            data[rear] = o; 
            ++counter;
        }
    }
    public void remove(){
        if(counter !=0){
            System.out.println("Removed Item: "+data[front]);
            front = (front+1)%5;
            --counter;
        }
    }
    public void show(){
        int i=front;
        do{
            System.out.println("Data at "+i+" is:  "+data[i]);
            i=(i+1)%5;
        }while(i!=rear);
    }
    public static void main(String[] aargs){
        cp_menu c = new cp_menu();
        int op=4;
        Scanner ss = new Scanner(System.in);
        while(true){
            System.out.println("1.Insert");
            System.out.println("2.Remove");
            System.out.println("3.Display");
            System.out.println("4.Exit");
            System.out.println("Choice:");
            op = ss.nextInt();
            if(op == 1){
                System.out.println("Enter Word:");
                String s = ss.next();
                c.insert(s);
            }else if(op == 2){
                c.remove();
            }else if(op == 3){
                c.show();
            }else{
                ss.close();
                System.exit(1);
            }
        }
    }
}

Binary Search Tree (BST)

Binary Search Tree is a tree in which each node can have only 0, 1, or 2 children. Nodes in the left of root is less than root node and nodes in the right of the root is greater than root node. This rule is same for the sub trees also.
BST can be traversal in following ways:

  • Preorder: First visit root node, then left child, then right child
  • Inorder: First visit left child, then root node, then right child. This traversal displays node in ascending order.
  • Post Order: First visit left child, then right child, the root.

 

If the left subtree or right subtree of the BST is lengthy compared to each other, then searching in the lengthy subtree will take more time than shorter subtree. The height of left and right subtrees are not balanced in the BST. This creates long search time for the lengthy subtree.

import java.util.*;
class node{
    int data;
    node left,right;
    public node(int d){
        data = d;
        left = right = null;
    }
}
class binary_tree{
    node root=null;
    node temp;
    public void insertNode(node n){
        if(root ==null){
            root = n;
        }else{
            temp = root;
            while(temp!=null){
                if(temp.data>n.data){
                    if(temp.left == null){
                        temp.left = n;
                        break;
                    }else
                    temp = temp.left;
                }
                else if(temp.data <=n.data){
                    if(temp.right == null){
                        temp.right = n;
                        break;
                    }else
                    temp = temp.right;
                }
            }
        }
    }
    public void inorder(node r){
        if(r!=null){
            inorder(r.left);
            System.out.println(" "+r.data);
            inorder(r.right);
        }
    }
    public node getRoot(){
        return root;
    }
}
class binary_tree_demo{
    public static void main(String[] args){
        node temp;
        Scanner sc = new Scanner(System.in);
        int option,value;
        binary_tree bt = new binary_tree();
        while(true){
            System.out.println("\n1.InsertNode\n2.DisplayTree\n8.Exit");
            option = sc.nextInt();
            switch(option){
                case 1:System.out.println("Enter a value:");
                    value = sc.nextInt();
                    temp = new node(value);
                    bt.insertNode(temp);
                break;
                case 2: System.out.println("Display Tree:");
                    bt.inorder(bt.getRoot());
                break;
                case 8:System.exit(0);
            }
        }
    }
}

AVL Tree

AVL tree is a height balance tree. If height of left and right sub trees of a binary search tree (BST) differs highly, then searching in that BST will be slow. Searching in lengthy tree takes more time than short tree.

To, remove this ineffiency of BST, AVL tree, a height balanced tree is developed. In AVL tree height of sub trees never differs more than 1, it can be -1, 0, or 1. Height of the AVL tree is adjusted at the time of inserting new node, if the insertion of new node voilates height factor (-1, 0 or 1) of the tree, then rotation of nodes is done to adjust the height factor of the tree.

  • Left Rotation
  • Right Rotation
  • Double Rotation
class AVLNode {
	int key, ht;
	AVLNode left, right;
	AVLNode(int d) {
		key = d;
		ht = 1;
	}
}

class AVLTree {
	AVLNode root;
	// A utility function to get the ht of the tree
	int getheight(AVLNode N) {
		if (N == null)
			return 0;
		return N.ht;
	}
	int getMaxHeight(int x, int y) {
		return (x > y) ? x : y;
	}
	AVLNode rightRotate(AVLNode b) {
		AVLNode a = b.left;
		AVLNode T2 = b.right;

		// Perform rotation
		a.right = b;
		b.left = T2;

		// Update hts
		b.ht = getMaxHeight(getheight(b.left), getheight(b.right)) + 1;
		a.ht = getMaxHeight(getheight(a.left), getheight(a.right)) + 1;
		return a;
	}
	AVLNode leftRotate(AVLNode a) {
		AVLNode b = a.right;
		AVLNode T2 = b.left;
		b.left = a;
		a.right = T2;
		a.ht = getMaxHeight(getheight(a.left), getheight(a.right)) + 1;
		b.ht = getMaxHeight(getheight(b.left), getheight(b.right)) + 1;
		return b;
	}
	int getBalance(AVLNode N) {
		if (N == null)
			return 0;

		return getheight(N.left) - getheight(N.right);
	}

	AVLNode insert(AVLNode AVLNode, int key) {
		if (AVLNode == null)
			return (new AVLNode(key));
		if (key < AVLNode.key)
			AVLNode.left = insert(AVLNode.left, key);
		else if (key > AVLNode.key)
			AVLNode.right = insert(AVLNode.right, key);
		else 
			return AVLNode;
		AVLNode.ht = 1 + getMaxHeight(getheight(AVLNode.left),
		getheight(AVLNode.right));
		int bal = getBalance(AVLNode);
		if (bal > 1 && key < AVLNode.left.key)
			return rightRotate(AVLNode);
		if (bal < -1 && key > AVLNode.right.key)
			return leftRotate(AVLNode);
		if (bal > 1 && key > AVLNode.left.key) {
			AVLNode.left = leftRotate(AVLNode.left);
			return rightRotate(AVLNode);
		}
		if (bal < -1 && key < AVLNode.right.key) {
			AVLNode.right = rightRotate(AVLNode.right);
			return leftRotate(AVLNode);
		}
		return AVLNode;
	}
	void preOrder(AVLNode AVLNode) {
		if (AVLNode != null) {
			System.out.print(AVLNode.key + " ");
			preOrder(AVLNode.left);
			preOrder(AVLNode.right);
		}
	}
    void inOrder(AVLNode r){
        if(r!=null){
            inOrder(r.left);
            System.out.println(r.key+ " ");
            inOrder(r.right);
        }
    }

	public static void main(String[] args) {
		AVLTree tree = new AVLTree();
		tree.root = tree.insert(tree.root, 10);
		tree.root = tree.insert(tree.root, 20);
		tree.root = tree.insert(tree.root, 30);
		tree.root = tree.insert(tree.root, 40);
		tree.root = tree.insert(tree.root, 50);
		tree.root = tree.insert(tree.root, 25);
		System.out.println("Preorder traversal" +
						" of constructed tree is : ");
		tree.preOrder(tree.root);
        tree.inOrder(tree.root);
	}
}

Graph

Graph is a non-linear data structure containing finite number of nodes and vertices. Graphs are used to represent real-world problems like telephone network, social networks, network of roads, etc. Graph can aslo be used to represent locations, places connected by roads. The connection between nodes or vertices is called edge. Weights (numerical values) can be assigned to the edges of the graph.

Directed Graph

In a directed graph direction is shown in the edge, that is, it is known if can we reach to node ‘b’ from node ‘a’ or not and back to node ‘a’ from node ‘b’ or not.

Undirected Graph

In undirected graph, edges don’t have direction.

Cycle in the Graph

If it is possible to reach to a node ‘a’ from where traversal is started or ‘a’ is intermediate node and come back to the same node ‘a’ after visiting intermediate nodes inbetween then the graph is said to contain a Cycle.

Minimum Spanning Tree

A tree containing all the nodes of the graph with minimum weight and with no loops or cycle is called a Minimum Spanning Tree. Minimum spanning tree can be used in telephone network design, computer network design, electric circuit design and many more. In case of computer network or electric circuit, all the componets of the network or circuit can be connected with minimum wire using the concept of minimum spanning tree.
Kruskal’s algorithm, Prim’s algorithm can be used to find a minimum spanning tree in a graph.

Shortest Path

In a weighted graph (a graph in which weigth is given to the edges) we can find a shorted path (path in minium cost) from one node (vertex) to another node. Dijkstra’s Algorithm can be used to find a shortest path in a graph.

Topological sort

Topological sorting shows the vertice/s which come before a given vertex ‘v’ of the directed acyclic graph (DAG). To perform some tasks it becomes necessary to perform some other tasks before that. For example, for a student to study master’s level of education it is necessary to complete bachelor’s level of education. The dependencies between the tasks can be represented by a graph without a cycle. Topological sort labels all the vertices with number 1 to V (V is the number of vertices in the graph) such that numbers i is < j if and only if there is a path from vi and v j. Topological sorting for a digraph with cycle is impossible.

Connectivity in a graph

An undirected graph having a path between any two vertices is called a Connected Graph. A graph can be more or less connected as connectivity has a degree. If a graph contains atleast n-different paths between any two verticess then it called n-connected graph. If a vertex ‘w’ in a path between vertices ‘u’ and ‘v’ is removed and there is no other path to reach from vertex ‘u’ to vertex ‘v’ then that vertex ‘w’ is called articulation point or cut vertex. The removal of the cut vertex or articulation point causes a graph to split into two or more graphs. If removal of a edge causes a graph to split into two subgraphs then the edge is called bridge or cut-edge. from a graph

Connectivity in Directed Graph

A directed graph is weakly connected if a undirected graph equivalent to the directed graph is connected. A directed graph is strongly connected if each and every pair of vertices have bi-directional paths. A graph may not be strongly connected but may be formed with strongly connected components (SCC).
Vertices x, y are k-edge connected if they remain connected even after removing fewer than k edges. A graph is k-edge connected if and only if every two vertices are k-edge connected. Connectivity is helpful in measuring fault tolerance of a computer network or (network only). The network will continue serving even after how many connections have been cut off.
k-vertex connected graph is that one in which removal of k vertices does not result in split of the graph. k-vertext connected implies k-edge connected but not conversely.

Network

network is directed graph with a vertex without any incoming edges called source, and one vertex with no outgoing eges called sink. Each edge is associated with a number called the capacity of the edge. A flow is a real number f:E –> $ that assigns a number to each edge of the network and meets two conditions:

  • Flow through an edge e can’t be greater than its capacity
  • The total flow coming to a vertex v is equal to the total flow coming from it.

The problem is to maximize the flow f so that the sum of total of output is maximum value for any possible function f. This is called a maximum-flow or max-flow problem.

Graph Implementation as Adjacency List

import java.util.*;

class Graph_as_adjacencyList {
	private int V; // Number of vertices
	private ArrayList[] adj;
	Graph_as_adjacencyList(int v)
	{
		V = v;
        adj = new ArrayList[v];
		for (int i = 0; i < v; ++i)
		    adj[i] = new ArrayList();
	}
	void addEdge(int v, int w)
	{
		adj[v].add(w); //Creating an edge.
	}
    void showGraph(){
        for(int i=0;i<v;i++) for(int="" j="0;j<adj[i].size();j++){" system.out.println("edges:="" "+i+"<--="">"+adj[i].get(j));
            }
    }
}
class Graph_as_adjacencyList_Demo{
    public static void main(String[] args){
        Graph_as_adjacencyList g = new Graph_as_adjacencyList(4);
        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(0, 3);
        g.addEdge(1, 2);
        g.addEdge(2, 0);
        g.addEdge(2, 3);
        g.addEdge(3, 3);
        g.addEdge(3, 1);
        g.showGraph();
    }
}

Sortings

QuickSort

        QuickSort(list[]){
            if(length of list > 1){
                pivot = select an first item of the list;
                while(length of list > 0){
                    if( element of list < pivot){
                        place element in left of pivot (sublistleft);
                    }
                    if (element of list > pivot){
                        place element in right of pivot (sublistright);
                    }
                } 
                QuickSort(sublistleft);
                QuickSort(sublistright);
            }
        }

MergeSort

        MergeSort(list){
            if (size of list >= 2){
                MergeSort(left half of list);
                MergeSort(right half of list);
                merge(left half of list and right half of list);
            }
        }
        merge(list1,list2,list3){
            initialize i1,i2,i3 properly;
            while( both list1 and list2 have elements){
                if(list2[i2] < list3[i3]){
                    list1[i1++] = list2[i2++];
                    list1[i1++] = list3[i3++];
                }
            store the remaining elements of either list2 or list3 to list1;
            }
        }

Heap Sort

Heap Sort was invented by John Williams. Heap sort uses approach similar to Selection Sort.

Heap sort uses a heap tree. There are two types of heap: max heap and min heap. A min heap tree is a binary tree having given properties:

  • value stored in children is greater than value stored in its parent node.
  • tree is perfectly balanced, and the leaves are in the last level are all in the leftmost positions.
        heapsort(list a){
            transform a to heap tree;
            for(int i = a.length; i > 1;i--){
                swap the root with the element in position i of the heap tree; 
                restore the heap property for the tree with element a[0] to a[i-1];
            }
        }

Quick Sort, Merge Sort and Heap sort’s running time is O(n lgn). Bubble sort, insertion sort and selection sort take O(n2) time. Algorithms with O(n2) take longer time to complete their operations than algorithms with O(n lgn) running time.

Radix Sort Algorithm

            Consider a list of number
            make all numbers of list of same digits by appending zero's in beginning of each numbers if required
            for(int j=length of number;j>=0;j--){
                for(int i = 1 ;i< list.size;i++){
                    compare element[i].digit[j] with element[i-1].digit[j];
                    order elements
                }
            }
Note:
  • compare the last digit of each number of the list and order the numbers accordingly to the last digit.
  • compare the second last digit of each number of the ordered list and order the numbers accordingly to the second last digit

Selection Sort

        SelectionSort(list){
            for(i=0;i<list.length;i++){
                find largest element of the list of size: size(list)-i;
                swap the found largest element with the last element of the list of size: size(list)-i
            }
        }

Insertion sort

InsertionSort(list){
            for(i=1;i<list.size();i++){
                temp = list[i];           
                j = i-1;      
                shift all elements before list[j] greater than temp by one position;
                place temp in its proper position; 
            }
        }

B Tree

A B Tree is multiway search tree having order m, m indicates how many children a node will have. B tree has following properties:

  • If root is not leaf, it has at least two subtrees.
  • Each intermediate node hold k – 1 keys and k references to subtrees where ceiling(m/2) <= k <=m.
  • Each leaf node has k-1 keys where ceiling(m/2) <= k <=m
  • All the leaves are in same level.

 

B Tree Node

        class BTreeNode{
            int m, int numberofkeys;
            boolean leaf = true;
            int keys[];
            BTreeNode references[];
            BTreeNode(int m, int n, int key){
                this.m = m;
                this.numberofkeys = n;
                keys = new int[m-1];
                references = new BTreeNode[m];
                keys[0] = key;
                for(int i=0;i<m;i++)
                    references[i] = null;
            }
        }

Algorithm to insert keys in B-trees:

BTreeInsert(key){
            find a leaf node to insert key;
            while(true){
                find a proper position in found leaf node for key;
                if node is have empty space{
                    insert key and increment numberofkeys;
                    return;
                }else{
                    split node into two nodes: n1 and n2, n1 = node and n2 is new one; 
                    distribute keys and references between n1 and n2 without violating definition of B Tree, initialize numberofkeys correctly;
                    key = the last key of n1; 
                    if node is root{
                        create a new root node as parent of n1 and n2;
                        put key and references to n1 and n2 in the root, set it numberofkeys to 1;
                        return; 
                    }else{
                        node = its parent; 
                    }
                }

            }
        }

Graph _ II

Cycle Detection using Depth First Search (DFS)in Graph Algorithm

        int i = 0;
        edges is array of edges;
        //method num(vertex) assign number of the vertex pass to it.
        cycleDetectionDFS(v){
            num(v) = i++;
            for all vertices u adjacent to v
                if(num(v) == 0){
                    add edge uv to edges
                    cycleDetection DFS(u);
                }else{
                    return cycle Detected;
                }
        }

Spanning Trees: Kruskal’s Algorithm

Minimum spanning tree is a tree in which the sum of the weight of its edges is minimal
Kruskal’s Algorithm

        Graph must be connected undirected graph
        E is number of edges;
        V is number of vertices; 
        KruskalAlgorithm(Grapgh G){
            tree = null;
            edges = all the edges of graph sorted by weight;
            for(i=1;i<=|E| and |tree| < |V|-1;i++){
                if(e

i

 from edges does not form a cycle with edges in tree){
                    add e

i

 to tree;
                }
            }
        }

Topological Sort

In many situations, tasks have to be performed in sequence as the order of tasks matters, it matters which task should be performed first. The dependencies between tasks can be show using directed graph (digraph) without cycle.

        int i = 0;
        V is number of vertices;
        TopologicalSort(digraph){
            for i=1 to |V|
                find a minimal vertex v, vertex with minimum indegree or indegree = 0;
                num(v) = i++;
                perform depth first search for vertex v until vertex without any out going edge is reached, store 
                vertices in stack;
                pop that vertex from stack, check if other edges can be traversed from elements of stack, if not
                pop them out. 

        }

Connectivity

An undirected graph is called connected if there is a path between any two vertices of the graph. A vertex removal of which splits a graph into subgraphs is called articulation point or cut vertex. A graph is called n-connected if there are at least n different paths any two vertices without any vertex in common between those paths

Network

A network can be explained as a network of pipelines used to deliver water to one destination from a source. Many pipes of different diameters with may pumping stations will be used to deliver water from source to destination, pumping power of stations will be different.

Dynamic Stack

Dynamic stack is FIFO data structure in which any number of data can be inserted. It is implemented using Linked List, in which only one end is defined to insert (push) or remove (pop) elements named top.

import java.util.*;
class dynamicStack{
	public static void main(String args[]){
		node temp, top=null;
		System.out.print("Creating Dynamic Stack!!!");
		int choice;
		String str; 
		Scanner sc = new Scanner(System.in);
		
		while(true){
			System.out.print("\n1.Push\n2.Pop\n3.Show\nChoice:");
			choice = sc.nextInt();
			switch(choice){
				case 1:
				System.out.println("Enter Data:");
						str = sc.nextLine();
					    str = sc.nextLine();
						temp = new node();
						temp.data = str;
						temp.address = null; 
						if(top == null){
							top = temp;
						}else{
							temp.address = top;
							top = temp;
						}
				break;
				case 2: System.out.println("Popping Stack!!!");
						System.out.println("Top of Stack : "+top.data);
							temp = top.address;
							top = temp;
							temp = null; 
				break;
				case 3: System.out.println("Show contents of Stack: \n");
						if(top != null){
						for(temp=top;temp.address!=null;temp=temp.address){
							System.out.print(temp.data+"  ");
						}
							System.out.print(temp.data+"  ");
						}
				break;
				default: System.exit(0);
				break; 
			}
		}
	}
}

Output:
Creating Dynamic Stack!!!
1.Push
2.Pop
3.Show
Choice:1
Enter Data:
apple

1.Push
2.Pop
3.Show
Choice:1
Enter Data:
mango

1.Push
2.Pop
3.Show
Choice:3
Show contents of Stack:

mango  apple
1.Push
2.Pop
3.Show
Choice:2
Popping Stack!!!
Top of Stack : mango

1.Push
2.Pop
3.Show
Choice:

Dynamic Queue

Queue is a data structure in which elements are added or inserted from end called rear and elements are removed from another end called front. In queue First element inserted is the first element to be removed. So, Queue is also known as First In First Out (FIFO) Data structure. Queue can be static or dynamic. If queue is implemented in array then it will be static queue. If queue is implemented using concept of linked list then it will be dynamic queue.

Here, is a code to implement queue dynamically. A node contained data field (here, string), and address field is defined. Three objects of node class is created: objects are temp, front, and rear. Both rear and front are assigned null. Object of Scanner is created to take data for node and for provided value action to perform. This is a menu driven program. Users can insert, remove and view contents of queue. Menu is written inside while loop so, user can run loop as s/he likes.

case 1 is for adding or inserting elements to the queue. if rear is null then queue is empty.
case 2 is for removing element from the queue.
case 3 is for displaying content of queue
*/

import java.util.*; 
class dynamicQueue{
	public static void main(String args[]){
		node temp, front=null,rear=null;
		System.out.println("Creating Dynamic Queue!!!");
		int choice;
		String str; 
		Scanner sc = new Scanner(System.in);
		
		while(true){
			System.out.println("\n1.Insert\n2.Remove\n3.Show\nChoice:");
			choice = sc.nextInt();
			switch(choice){
				case 1: System.out.println("Enter Data:");
						str = sc.nextLine();
					    str = sc.nextLine();
						temp = new node();
						temp.data = str;
						temp.address = null; 
						if(rear == null){
							rear = temp;
							front = temp;
						}else{
							rear.address = temp;
							rear = temp;
						}
				break;
				case 2: System.out.println("Removing Element From Queue!!!");
						System.out.println("Element Removed : "+front.data);
						if(front == rear)
							System.out.println("Queue is Empty");
						else{
							temp = front;
							front = front.address;
							temp = null; 
						}
							
				break;
				case 3: System.out.println("Show contents of Queue: \n");
						for(temp=front;temp!=rear;temp=temp.address){
							System.out.print(temp.data+"  ");
						}
							System.out.print(temp.data+"  ");
				break;
				case 4: System.exit(0);
				break; 
			}
		}
	}
}
//Output:
Creating Dynamic Queue!!!

1.Insert
2.Remove
3.Show
Choice:
1
Enter Data:
movies

1.Insert
2.Remove
3.Show
Choice:
1
Enter Data:
books

1.Insert
2.Remove
3.Show
Choice:
3
Show contents of Queue:

movies  books
1.Insert
2.Remove
3.Show
Choice:
2
Removing Element From Queue!!!
Element Removed : movies

1.Insert
2.Remove
3.Show
Choice:
3
Show contents of Queue:

books
1.Insert
2.Remove
3.Show
Choice: 5

Doubly Linked List

import java.util.*;
class dnode{
	int data;
	dnode left,right;
}

class doublelinkedlistDemo{
	public static void main(String[] args){
		dnode first=null, temp, dummy;
		dummy = new dnode();
		System.out.println("Creating Doubly Linked List!!!");
		int choice;
		int data; 
		Scanner sc = new Scanner(System.in);
		while(true){
			System.out.println("\n1.Insert\n2.Show\n3.Back Track\n4.Remove First Node\n5.Insert Before Firs node");
			choice = sc.nextInt();
			switch(choice){
				case 1: System.out.println("Enter Integer Data:");
						data = sc.nextInt();
						temp = new dnode();
						temp.data = data;
						temp.left = temp.right = null; 
						if(first == null){
							first = temp;
							dummy = temp;
						}else{
							dummy.right = temp;
							temp.left = dummy;
							dummy = temp;
						}
				break;
				case 2: System.out.println("Show contents of List: \n");
						for(temp=first;temp.right!=null;temp=temp.right){
							System.out.print(temp.data+"  ");
						}System.out.print(temp.data+"  ");
				break;
				case 3: System.out.println("Back Tracking: \n");
						for(temp=dummy;temp.left!=null;temp=temp.left){
							System.out.print(temp.data+"  ");
						}System.out.print(temp.data+"  ");
				break;
				case 4: System.out.println("Removing First Node of List");
						temp = first.right;
						first = temp;
						first.left = null; 
				break;
				case 5: System.out.println("Insert Before First Node");
						data = sc.nextInt();
						temp = new dnode();
						temp.data = data;
						temp.left = temp.right = null; 
						temp.right = first; 
						first.left = temp;
						first = temp; 
				break;
				default:System.exit(0);
				break;
			}
		}
	}
}
Output
Creating Doubly Linked List!!!

1.Insert
2.Show
3.Back Track
4.Remove First Node
5.Insert Before Firs node
1
Enter Integer Data:
33

1.Insert
2.Show
3.Back Track
4.Remove First Node
5.Insert Before Firs node
1
Enter Integer Data:
44

1.Insert
2.Show
3.Back Track
4.Remove First Node
5.Insert Before Firs node
1
Enter Integer Data:
5

1.Insert
2.Show
3.Back Track
4.Remove First Node
5.Insert Before Firs node
2
Show contents of List:

33  44  5
1.Insert
2.Show
3.Back Track
4.Remove First Node
5.Insert Before Firs node
3
Back Tracking:

5  44  33
1.Insert
2.Show
3.Back Track
4.Remove First Node
5.Insert Before Firs node
4
Removing First Node of List

1.Insert
2.Show
3.Back Track
4.Remove First Node
5.Insert Before Firs node
2
Show contents of List:

44  5
1.Insert
2.Show
3.Back Track
4.Remove First Node
5.Insert Before Firs node

Graph BSF Shortest Cycle

import java.util.*;
class AdjacencyGraph{
  
    int  matrix[][] = new int[10][10];
    public void createEdge(int s, int e, int w){
        matrix[s][e] = w;
    }

    public void showGraph(){
        System.out.println("Size of Graph: "+matrix.length)   ;
        for(int i=0;i<=5;i++){
            for(int j=0;j<=5;j++){
                System.out.print(matrix[i][j]+" ");
            }
            System.out.println();
        }
    }
    public void BSF(int start){
        int queue[] = new int[10];
        boolean visited[] = new boolean[10];
        visited[start] = true;
        int rear = -1,front=0,i;
        queue[++rear] = start;
        for(front=0;front <=rear;front++){
            for(i=0;i<matrix.length;i++){
                if(matrix[queue[front]][i]!=0){
                    if(visited[i]!=true){
                        queue[++rear] = i;
                        visited[i] = true;
                    }else if(visited[i]== true){
                        for(int j=0;j<queue.length;j++){
                            if(queue[j]== i)
                                System.out.println("Cycle Found!!!");
                        }
                    }
                }
            }
        }
        for(i=0;i<=rear;i++){
            System.out.println(" "+queue[i]);
        }
    }
    public void dijkstra(){
        int v = matrix.length;
        boolean visited[] = new boolean[v];
        int distance[] = new int[v];
        distance[0] = 0;
        for(int i=1;i<v;i++){
            distance[i] = Integer.MAX_VALUE;
        }
        for(int i=0;i<v-1;i++){
            int minVertex = minVertex(distance,visited);
            System.out.println("Min Vertext: "+minVertex);
            visited[minVertex] = true;
            //explore neighbors
            for(int j=0;j<v;j++){
                if(matrix[minVertex][j]!=0 && !visited[j] && (distance[minVertex]!=Integer.MAX_VALUE)){
                    int newDist = distance[minVertex]+matrix[minVertex][j];
                    if(newDist < distance[j]){
                        distance[j] = newDist;
                    }
                }
            }
        }
        for(int i=0;i<v-1;i++){
            System.out.println(i+" "+distance[i]);
        }
    }
    public int minVertex(int[] distance,boolean[] visited){
        int minVertex = -1;
        for(int i=0;i<distance.length;i++){
            if(!visited[i] &&(minVertex == -1 || distance[i] < distance[minVertex])){
                minVertex = i;
            }
        }
        return minVertex; 
    }
    public void showAdjacent(int vertex){
        for(int i=0;i<5;i++){
            if(matrix[vertex][i]!=0)
                System.out.println("Adjacents: "+i);
        }
    }
    public void showInDegree(int vertex){
        int count = 0;
        for(int i=1;i<matrix.length;i++){
            if(matrix[i][vertex]!=0){
                ++count;
            }
        }
        System.out.println("In Degree of "+vertex+" is "+count);
    }
}

class AdjacencyGraphDemo{
    public static void main(String[] args){
        AdjacencyGraph gg = new AdjacencyGraph();
        gg.createEdge(0,1,3);
        gg.createEdge(0,2,4);
        gg.createEdge(0,3,5);
        gg.createEdge(3,4,4);
        gg.BSF(0);

        AdjacencyGraph g = new AdjacencyGraph();
        g.createEdge(0,1,4);
        g.createEdge(1,0,4);
        g.createEdge(0,2,8);
        g.createEdge(2,0,8);
        g.createEdge(1,3,5);
        g.createEdge(3,1,5);
        g.createEdge(1,2,2);
        g.createEdge(2,1,2);
        g.createEdge(2,4,9);
        g.createEdge(4,2,9);
        g.createEdge(2,3,5);
        g.createEdge(3,2,5);
        g.createEdge(4,3,4);
        g.createEdge(3,4,4);
        //System.out.println("Shortest path");
        g.showGraph();
        g.dijkstra();
        g.showAdjacent(3);
        //g.detectCycle(0);
        System.out.println("BSF Traversal");
        g.BSF(0);
        AdjacencyGraph dg = new AdjacencyGraph();
        dg.createEdge(1,2,5);
        dg.createEdge(3,2,4);
        dg.createEdge(3,4,3);
        dg.createEdge(4,1,2);
        dg.createEdge(5,2,2);
        dg.createEdge(5,1,2);
        dg.createEdge(4,1,2);
        dg.showGraph();
        dg.showInDegree(2);
        AdjacencyGraph d1 = new AdjacencyGraph();
        d1.createEdge(1,2,3);
        d1.createEdge(1,3,3);
        d1.createEdge(1,4,3);
        d1.createEdge(4,5,3);
        d1.createEdge(2,6,3);
        d1.createEdge(3,6,3);
        d1.BSF(1);
    }
}

Graph Implementation

Graph is a collection of nodes and edges between the nodes. In the program given below, class nodes is created to store name of nodes and class edges is created to store information about the edges. Class nodes simply stores name of nodes in the array of characters with the help of setNodes methods.
Class edges has src and dest variables to store name of nodes and wt variable to store weight of the edge. Method setEdges takes three parameters: source node, destination node, and weight of the edge.
Method showEdge displays information of the edges.

class nodes{
    char[] nodes;  
    public nodes(){
        nodes = new char[10];
    }
    public void setNodes(char[] nodes){
        this.nodes = nodes;
    }
    public  void showNodes(){
        for(int i=0;i<nodes.length;i++){
            System.out.println(nodes[i]);
        }
    }
}
class edges{
    char src,dest; 
    int wt;
    public edges(){}
    public void setEdges(char s,char d,int w){
        src = s;
        dest = d;
        wt = w; 
    }
    public void showEdge(){
        System.out.println("Edge: "+src+"---"+wt+"---"+dest);
    }
}

class graph_2{
	public static void main(String[] arr){
		char n[] = {'a','b','c','d','e','f'};
		nodes g_n = new nodes(); 
        g_n.setNodes(n);
		g_n.showNodes();
		edges [] ee = new edges[7];
		int i;
		for(i=0;i<7;i++){
			ee[i] = new edges();
		}
		ee[0].setEdges(n[0],n[1],9);
		ee[1].setEdges(n[0],n[2],3);
		ee[2].setEdges(n[2],n[3],7);
		ee[3].setEdges(n[2],n[4],8);
		ee[4].setEdges(n[0],n[5],5);
		ee[5].setEdges(n[4],n[5],6);
		ee[6].setEdges(n[2],n[5],5);
		for(i=0;i<7;i++){
			ee[i].showEdge();
		}
	}
}

Hashing Implementation

Hashing is a technique of storing data in a list or table such that stored data can be found in single comparison or in very few comparisons. Several methods are defined to store data in a list: division by prime number, folding individual digits of the given data, etc.
It is very possible that two or more data hash to same position, that is, hash method produce same hash values for different elements, this situation is known as Hash Collision.
Hash collision can be reduced by considering big prime number to division given data; probing methods can be used to address hash collisions.
Following program uses division by prime number to hash given elements, and quadratic probing to resolve collision.
List of numbers are stored in array named keys, those keys are stored or hash to list name table of size 100. Prime number 97 is used to divide given elements.

import java.util.*;

class hashing_Demo
{
	public static void main(String[] aa){
		int keys [] = {111,14,222,333,423,4556,6777,8889,3232,4345,46787};
		int table[] = new int[100];
		int i,prime=97,hashvalue=0;
		for(i=0;i<keys.length;i++){
			hashvalue = keys[i] % prime;
			if(table[hashvalue]==0)
				table[hashvalue] = keys[i];
			else{
				for(int j=1;j<100;j=j*j){
					if(table[hashvalue+j]==0){
						table[hashvalue+j] = keys[i];
						break;
					}
				}
			}
		}
		for(i=0;i<table.length;i++){
			System.out.print(" "+table[i]);
		}
		Scanner sc = new Scanner(System.in);
		System.out.println("Enter value to search: ");
		int search = sc.nextInt();
		hashvalue = search % prime;
		if(table[hashvalue] == search)
			System.out.println("Found at"+hashvalue);
		else{
			for(int j=1;j<100;j=j*j){
				if(table[hashvalue+j]==search){
					System.out.println("Found at"+(hashvalue+j));
					break;
				}
			}
		}
	}
}

Copy Linked List to array

A simple linked list is creating in the following program. Node class with data field and address field is defined, constructor is defined to set value for data field (second constructor), show method returns content of a node.

In the driver class (class with main method): while loop is used to create a linked list, numbers from 100 to 109 is stored in the list.

A third loop (for loop) is created to loop through the list, as the fourth position is reached loop is stopped. temp1 iterates through the list and stops at the fourth node (i != 3); A new node temp2 is created; in next field of temp2 reference of 5th node (temp1.next) is stored, then in next field of 4th node (temp1.next), temp2 is stored. A node is inserted in the list.

The list traversed in the fifth loop (for loop), and data of list is stored in the array arr.

class node{
    int data;
    node next;
    public node(){
        next = null;
    }
    public node(int d){
        data = d;
        next = null;
    }
    public int show(){
        //System.out.println(" "+data);
        return data;
    }
}

class linkedlist_demo{
    public static void main(String[] ar){
        node head = null, temp1,temp2=null;
        int i=100;
        int aar[] = new int [20],j=0;
        //creating linked list wiht 10 elements;
        while(i<110){
            temp1 = new node(i);
            if(head == null){
                head = temp1;
                temp2 = temp1;
                //head.show();
            }else{
                temp2.next = temp1;
                temp2 = temp1; 
                //temp2.show();
            }
            ++i;
        }
        //display list
        System.out.println("\nBefore inserting new node:--->");
        for(temp1 = head;temp1!=null;temp1=temp1.next){
            System.out.print(" "+ temp1.show());
        }

        //inserting new node after given position, 
        //here new node will be inserted after 4th node
        i=0;
        for(temp1 = head;i!=3;temp1=temp1.next){
            i++;
        }
        temp2 = new node(9999);
        temp2.next = temp1.next;
        temp1.next = temp2;
        

        System.out.println("\nAfter inserting new node:--->");
        for(temp1 = head;temp1!=null;temp1=temp1.next){
            System.out.print(" "+ temp1.show());
        }

        //coping contents of linked list to array
        j=0;
        for(temp1 = head;temp1!=null;temp1=temp1.next){
            aar[j++] = temp1.show();
        }
        //Displaying content of array
        System.out.println("\nPrinting content of array--> ");
        for(i=0;i<j;i++)
        System.out.print(" "+aar[i]);
    }
}
Output:
Before inserting new node:--->
 100 101 102 103 104 105 106 107 108 109
After inserting new node:--->
 100 101 102 103 9999 104 105 106 107 108 109
Printing content of array-->
 100 101 102 103 9999 104 105 106 107 108 109

Didn't Find Any Subjects/Contents?

Click on the contribute button to contribute subjects materials on Study Notes Nepal.

Contribute

1 thought on “Data Structure and Algorithm | Reference Notes

Leave a Reply

Your email address will not be published. Required fields are marked *


Join Our Facebook Community Group

Study Notes Nepal