1) List Interface Implementation
public interface List<T extends Comparable<T>> {
public Node<T> getMiddleNode();
public void insert(T data);
public void remove(T data);
public void traverse();
public int size();
public void reverse();
}
2) Linked List's Node Implementation
public class Node<T extends Comparable<T>> {
private Node<T> nextNode;
T data;
public Node(T data){
this.data = data;
}
public Node<T> getNextNode() {
return nextNode;
}
public void setNextNode(Node<T> nextNode) {
this.nextNode = nextNode;
}
public T getData() {
return data;
}
public void setData(T data) {
this.data = data;
}
@Override
public String toString() {
return data+"-> ";
}
}
3) Linked List Implementation
public class LinkedList<T extends Comparable<T>> implements List<T> {
private Node<T> head;
int sizeCounter=0;
@Override
public Node<T> getMiddleNode() { ==> Example to find middle node of LinkedList
Node<T> slow = head;
Node<T> fast = head;
while(fast.getNextNode() != null &&
fast.getNextNode().getNextNode() != null) {
slow = slow.getNextNode();
fast = fast.getNextNode().getNextNode();
}
return slow;
}
@Override
public void insert(T data) {
sizeCounter++;
if(head==null) {
head = new Node<T>(data);
}else {
insertBiginning(data);
}
}
private void insertBiginning(T data) {
Node<T> node = new Node<T>(data);
node.setNextNode(head);
head = node;
}
@Override
public void remove(T data) {
if(head == null) return;
if(head.getData().compareTo(data) == 0) {
head = head.getNextNode();
}else {
remove(data,head, head.getNextNode());
}
}
private void remove(T data, Node<T> previousNode, Node<T> actualNode) {
while(actualNode != null) {
if(actualNode.getData().compareTo(data)==0) { ==> This is the reason we use generic type which extends Comparable
sizeCounter--;
previousNode.setNextNode(actualNode.getNextNode());
actualNode=null;
return;
}
previousNode = actualNode;
actualNode = actualNode.getNextNode();
}
}
@Override
public void traverse() { ==> Example to traverse linked list
r
if(head==null) return;
Node<T> actualNode = head;
while(actualNode != null) {
System.out.print(actualNode);
actualNode = actualNode.getNextNode();
}
}
@Override
public int size() {
return sizeCounter;
}
@Override
public void reverse() { ==> Example to reverse LinkedList
Node<T> prev = null;
Node<T> next = null;
Node<T> current = head;
while(current != null) {
next = current.getNextNode();
current.setNextNode(prev);
prev = current;
current = next;
}
head = prev;
}
}
4) Linked List uses example
public class AppRunner {
public static void main(String[] args) {
LinkedList<String> names = new LinkedList<>();
names.insert("narayan");
names.insert("Pawan");
names.insert("Karan");
names.insert("Sonu");
names.insert("Ram");
names.traverse(); ==> Traversing Linked List
System.out.println("");
System.out.println("Middle node is :- "+names.getMiddleNode());==> Finding middle element without using extra loop
names.reverse(); ==> Reversing linkedList without inbuilt function
System.out.println("");
names.traverse();
}
}
5) Output:-
Before Reverse:- Tarun-> Nishant-> Gajendra-> Sonpal-> Ravi-> Anurag-> Narayan->
After ReversingNarayan-> Anurag-> Ravi-> Sonpal-> Gajendra-> Nishant-> Tarun->
Middle node is :- Sonpal->
Monday, February 8, 2021
How to find middle element of LinkedList without using inbuilt method or extra loop
Friday, February 5, 2021
What will be the output of given example
public class StringConcating {
public static void main(String[] args) {
String str ="Hello";
String str2 = "Narayan";
String str3 = "HelloNarayan";
String str4 = str+str2;
if(str3 == str4) {
System.out.println("Match");
}else {
System.out.println("Not Match");
}
}
}
Output:-
Not Match
Now you may wordering bcoz both object have same value still not match
so reason behind of this is when we do any operation over string it
return new object that will store in heap memory so we can say that str4 store
in heap while str3 will store in string constant pool and can't change value
of it since string is immutable
Thursday, February 4, 2021
How to reverse an Array without using extra memory
public class ReverseArrayWithoutExtraMemory {
public static void main(String[] args) {
int arr[] = {1,2,3,4,5,6};
int swapArray[] = new ReverseArrayWithoutExtraMemory().swapArray(arr);
for (int i : swapArray) {
System.out.print(i+" ");
}
}
public int[] swapArray(int[] arr) {
int startIndex=0;
int lastIndex= arr.length-1;
while(lastIndex > startIndex) {
swapItem(arr, startIndex, lastIndex);
lastIndex--;
startIndex++;
}
return arr;
}
public void swapItem(int[] arr, int startIndex, int lastIndex) {
int temp = arr[startIndex];
arr[startIndex] = arr[lastIndex];
arr[lastIndex] = temp;
}
}
Output:-
6 5 4 3 2 1
How to find biggest item in the array within constant time complexity
public class BiggestnumberInArray {
public static void main(String[] args) {
// TODO Auto-generated method stub
int arr[] = {1,8,10,40,30,60,50,0,-2};
System.out.println("The biggest Item is : "+
new BiggestnumberInArray().findBiggestItem(arr));
}
public int findBiggestItem(int arr[]) {
int biggest=0;
for (int i : arr) {
if(biggest==0) {
biggest=i;
}
if(biggest < i) {
biggest = i;
}
}
return biggest;
}
}
Output:-
The biggest Item is : 60
How to find smallest item in the array within constant time complexity
public class SmallestItemIntoArray {
public static void main(String[] args) {
// TODO Auto-generated method stub
int arr[] = {1,8,10,40,30,60,50,0,-2};
System.out.println("The smallest Item is : "+
new SmallestItemIntoArray().smallestItem(arr));
}
public int smallestItem(int arr[]) {
int smallest=0;
for (int i : arr) {
if(smallest==0) {
smallest=i;
}
if(smallest > i) {
smallest = i;
}
}
return smallest;
}
}
Output:-
The smallest Item is : -2
Stack Implementation using Array Data structure
Stack Implementation
import java.util.Arrays;
public class Stack {
private int count=0;
private T[] data;
Stack(){
data = (T[]) new Object[1];
}
public int size() {
return count;
}
public boolean isEmpty() {
return count==0;
}
public void push(T newItem) {
if(count==data.length) {
resize(2*data.length);
}
data[count++] = newItem;
}
public T pop() {
T item = data[--count];
if(count>0 && count == (data.length/4)){
resize(data.length/2);
}
return item;
}
public void resize(int newCapacity){
T stackCopy[] = Arrays.copyOf(data, newCapacity);
data = stackCopy;
}
}
App Runner:-
public class StackApp {
public static void main(String[] args) {
// TODO Auto-generated method stub
Stack stack = new Stack();
stack.push(10);
stack.push(30);
stack.push(4);
stack.push(7);
stack.push(14);
while(!stack.isEmpty())
System.out.println(stack.pop());
}
}
Output:-
14
7
4
30
10
How to find pair of two numbers whose difference equivalent to given key less than N square time complexity
public class DifferencePair {
public static void main(String[] args) {
int arr[] = {1,8,10,40,30,60,50};
int n = 10;
findPair(arr,n);
}
private static void findPair(int[] arr, int n) {
ArrayList<Integer> numbers = new ArrayList<>();
boolean status = false;
for(int num : arr) {
if(numbers.contains((num-n))){
status=true;
System.out.println("Pair Found: "+"( "+(num-n)+", "+ num+" )");
}
if (numbers.contains((num+n))) {
status=true;
System.out.println("Pair Found: "+"( "+(num+n)+", "+ num+" )");
}
numbers.add(num);
}
if(!status)
System.out.print("No such pair");
}
}
Output:-
Pair Found: ( 40, 30 )
Pair Found: ( 40, 50 )
Pair Found: ( 60, 50 )
How to find Pair of two sum element equivalent to given key less than N square time complexity
public class SumPair {
public static void main(String[] args) {
int arr[] = {5,7,8,3,1,4,6,9,2};
int n = 12;
findPair(arr,n);
}
private static void findPair(int[] arr, int n) {
ArrayList<Integer> numbers = new ArrayList<>();
boolean status = false;
for(int num : arr) {
int anotherNumber = (n-num);
if(numbers.contains(anotherNumber) && (anotherNumber+num) == n) {
status=true;
System.out.println("Pair Found: "+"( "+anotherNumber+", "+ num+" )");
}
numbers.add(num);
}
if(!status)
System.out.print("No such pair");
}
}
Output:-
Pair Found: ( 5, 7 )
Pair Found: ( 8, 4 )
Pair Found: ( 3, 9 )
Subscribe to:
Posts (Atom)
How to sort an HashMap based on value
import java.util.Collections; import java.util.Comparator; import java.util.HashMap; import java.util.LinkedHashMap; import java....
-
http://www.roseindia.net/apachevelocity/velocity-tutorials.shtml
-
http://download.oracle.com/javase/tutorial/uiswing/start/index.html
-
function data_change(field) { var check = true; var value = field.value; //get characters //check that all ch...