Linked List is a linear data structure where elements are not stored in contiguous memory location. The elements of linked list contains a object and the address part.Each element in linked list is called node. It has some advantage over array: Size of the list doesn't need to be mentioned at the beginning of the program, certainly dynamic memory allocation and deallocation. As the linked list doesn't have a size limit, we can go on adding new nodes (elements) and increasing the size of the list to any extent. It has some disadvantage over array: Wastage of Memory – Pointer Requires extra memory for storage. The main disadvantage of linked list over array is access time to individual elements.Array is random-access,which means it takes O(1) to access any element in the array.Linked list takes O(n) for access to an element in the list in the worst case. In linked list ,Random access is not allowed. We have to access elements sequentially starting from the first node. So we cannot do binary search with linked lists. Code: Create a class called Node for representing each element i linked list. class Node { int data; Node next; public Node(int data) { this.data = data; this.next = null; } } data represent the integer value of element and next is the pointer to next element. Create a class called LinkedList class LinkedList { Node head; public LinkedList() { head = null; } } head points to the first element of the linked list. Add addLast ,addFirst and addAtPos methods that add the elements to the linked list at last ,first and given position respectively. public void addLast(int data) { Node current = this.head; if(current == null) { head = new Node(data); return; } while(current.next != null) { current = current.next; } current.next = new Node(data); } public void addFirst(int data) { Node current = this.head; if(current == null) { head = new Node(data); return; } head = new Node(data); head.next = current; } public void addAtPos(int data,int pos) { Node current = this.head; if(current == null&&pos == 0) { head = new Node(data); return; } int index = 0; while(current != null) { if(index == pos-1) { Node temp = current.next; current.next = new Node(data); current = current.next; current.next = temp; return; } else { index++; current = current.next; } } System.out.println("Index is not found !!"); } Add removeLast,removeFirst and removeAtPos methods to remove elements from linked list at last ,first nd given position respectively. public void removeLast() { Node current = this.head; if(current == null) { System.out.println("There is no last element !!"); return; } if(current.next == null) { head = null; return; } while(current.next.next != null) { current = current.next; } current.next = null; } public void removeFirst() { Node current = this.head; if(current == null) { System.out.println("There is no first element !!"); return; } if(current.next == null) { head = null; return; } Node temp = current.next; this.head = temp; } public void removeAtPos(int pos) { Node current = this.head; if(current == null) { System.out.println("There is no index found !!"); return; } if(current.next == null&&pos == 0) { head = null; return; } int index = 0; while(current != null) { if(index == pos-1) { Node temp = current.next; current.next = temp.next; return; } else { index++; current = current.next; } } System.out.println("Index is not found !!"); } Add print method to print the elements in linked list. public void print() { Node current = this.head; while(current !=null) { System.out.print(current.data+" "); current = current.next; } System.out.println(); } Add length method to find the number of elements in linked list. public int length() { Node current = this.head; int length = 0; while(current != null) { length++; current = current.next; } return length; } Main method: public static void main(String[] args) { LinkedList list = new LinkedList(); System.out.println("Linked List******************************************"); list.addFirst(5); list.addLast(6); list.print(); System.out.println("*******************************************************"); list.addAtPos(10,3); list.print(); System.out.println("*******************************************************"); list.addLast(3); list.addLast(5); list.addLast(2); list.addLast(8); list.print(); System.out.println("*******************************************************"); //System.out.println("**********************************************************"); list.removeLast(); list.print(); System.out.println("************************************************************"); list.removeFirst(); list.print(); System.out.println("*******************************************************"); list.removeAtPos(2); list.print(); System.out.println("*******************************************************"); list.removeAtPos(5); list.print(); System.out.println("*******************************************************"); list.addAtPos(10,2); list.print(); System.out.println("*******************************************************"); System.out.println("Length :"+list.length()); System.out.println("*******************************************************"); } Output:

A password is validate if: It contains at least 8 characters and at most 15 characters. It contains at least one lower case alphabet. It contains at least one upper case alphabet. It contains at least one digit. It contains at least one special character i.e. !@#$%&*()-+=^. It does not contain space. Code: Import library: import java.util.regex.Matcher; import java.util.regex.Pattern; Create a Password class class Password { } Create a regular expression to check a password is valid or not. public static final Pattern PASSWORD_REGEX = Pattern.compile("^(?=.*[0-9])" + "(?=.*[a-z])(?=.*[A-Z])" + "(?=.*[@#$%^&+=])" + "(?=\\S+$).{8,15}$"); Add a validatePassword method public static String validatePassword(String str) { // System.out.println(str); Matcher matcher = PASSWORD_REGEX.matcher(str); return matcher.find()?"":" not"; } Main method public static void main(String[] args) { String[] str = new String[]{"pollard@123A","Tesl@112","Park","Fest@4","TSHIRT","Ramesh123"}; for(int i=0;i<str.length;i++) { System.out.println("The password "+str[i]+" is"+validatePassword(str[i])+" validate"); } } Output:

Binary search is used to search an key element from array of elements. Binary search is faster than linear search. It can be used when the elements are in a sorted sequence and all the key elements are unique. It takes O(logn) time where as the linear search takes O(n) time in worst case. Algorithm: Compare the middle element with key If the middle element matches with the key, then return index of middle element Else if middle elements is greater than key, then key can only be lie on half sub array before the mid so we recursively find the key in half sub array Else key can be found in half sub array after the mid Code: Import library import java.util.*; Create a class called BinarySearch class BinarySearch { } Add methods searchHelper and search. public static int searchHelper(int[] arr,int low,int high,int key) { if(low<=high) { int mid = (low+high)/2; if(arr[mid] == key) { return mid; } else if(arr[mid]>key) { return searchHelper(arr,low,mid-1,key); } else { return searchHelper(arr,mid+1,high,key); } } // if key is not found return -1; } public static void search(int[] arr,int key) { int value = searchHelper(arr,0,arr.length-1,key); System.out.println("The key "+key+ " is found at index "+value); } searchHelper method is used to search the key element from an array recursively. Main method: public static void main(String[] args) { int[] arr = new int[]{3,5,7,8,9,1,15,13,78,4,34,89,23,12}; Arrays.sort(arr); search(arr,7); search(arr,13); search(arr,89); search(arr,12); } Output:

Binary search tree is a node based binary tree data structure which has following property: The left subtree of a node contains key that is less than the node's key. The right subtree of a node contains key that is greater than the node's key. The left and right subtree must also be binary search tree. Create a node to store the key class Node { int data; Node left; Node right; public Node(int data) { this.data = data; this.left = null; this.right = null; } } Create a class BST class BST { Node root; static int count = 0; public BST() { root = null; } } Add method is used to add the key in binary search tree. void add(int key) { root = addHelper(root, key); } Node addHelper(Node root, int key) { if (root == null) { root = new Node(key); return root; } if (key < root.data) root.left = addHelper(root.left, key); else if (key > root.data) root.right = addHelper(root.right, key); return root; } Delete a particular key in a binary search tree. public Node deleteNode(Node root, int key) { Node parent = null; Node curr = root; while (curr != null && curr.data != key) { parent = curr; if (key < curr.data) { curr = curr.left; } else { curr = curr.right; } } // return if key is not found in the tree if (curr == null) { return root; } // node to be deleted has no children i.e. it is a leaf node if (curr.left == null && curr.right == null) { // if node to be deleted is not a root node, then set its // parent left/right child to null if (curr != root) { if (parent.left == curr) { parent.left = null; } else { parent.right = null; } } // if tree has only root node, delete it and set root to null else { root = null; } } // node to be deleted has two children else if (curr.left != null && curr.right != null) { // find its in-order successor node Node successor = minimumKey(curr.right); int val = successor.data; deleteNode(root, successor.data); curr.data = val; } // node to be deleted has only one child else { // find child node Node child = (curr.left != null)? curr.left: curr.right; // if node to be deleted is not a root node, then set its parent // to its child if (curr != root) { if (curr == parent.left) { parent.left = child; } else { parent.right = child; } } // if node to be deleted is root node, then set the root to child else { root = child; } } return root; } Finding the minimum value from binary search tree. public Node minimumKey(Node curr) { while (curr.left != null) { curr = curr.left; } return curr; } Searching a node of given key in binary search tree. public Node search(Node root,int key) { if(root == null) { return null; } if(root.data == key) { return root; } else if(key<root.data) { return search(root.left,key); } else { return search(root.right,key); } } Kth Smallest in binary search tree. public static Node kthSmallest(Node root, int k) { if (root == null) return null; Node left = kthSmallest(root.left, k); if (left != null) return left; count++; if (count == k) return root; return kthSmallest(root.right, k); } public static void printKthSmallest(Node root, int k) { count = 0; Node curr = kthSmallest(root, k); if (curr == null) System.out.print("There are less " + "than k nodes in the BST"); else System.out.print(curr.data); } Inorder in binary search tree. public void inOrder(Node root) { if(root == null) { return; } inOrder(root.left); System.out.print(root.data+" "); inOrder(root.right); } Preorder in binary search tree. public void preOrder(Node root) { if(root == null) { return; } System.out.print(root.data+" "); preOrder(root.left); preOrder(root.right); } Postorder in binary search tree. public void postOrder(Node root) { if(root == null) { return; } postOrder(root.left); postOrder(root.right); System.out.print(root.data+" "); } Driver method. public static void main(String[] args) { BST tree = new BST(); tree.add(5); tree.add(3); tree.add(2); tree.add(4); tree.add(7); tree.add(6); tree.add(8); System.out.println("Inorder of BST *********************************"); tree.inOrder(tree.root); System.out.println(); System.out.println("Preorder of BST *********************************"); tree.preOrder(tree.root); System.out.println(); System.out.println("Postorder of BST *********************************"); tree.postOrder(tree.root); System.out.println(); System.out.println("Delete 4 from BST*********************************"); int key = 4; tree.root = tree.deleteNode(tree.root,key); System.out.println("Inorder of BST *********************************"); tree.inOrder(tree.root); System.out.println(); System.out.println("Delete 7 from BST*********************************"); key = 7; tree.root = tree.deleteNode(tree.root,key); System.out.println("Inorder of BST *********************************"); tree.inOrder(tree.root); System.out.println(); System.out.println("Minimum key from BST ****************************"); Node curr = tree.minimumKey(tree.root); System.out.print(curr.data); System.out.println(); System.out.println("Search a node from BST ****************************"); key = 2; curr = tree.search(tree.root,key); System.out.print(curr.data+" "); System.out.println(); System.out.println("Kth smallest in BST ****************************"); int k = 3; tree.printKthSmallest(tree.root,k); System.out.println(); } Output