//This is the class that I use to make the node. Here I use a constructor to add the element in a node.
//next gets automatically initialized as null.
public class link { int i; link next; public link(int j) { i = j; } } ********************************************** //This is the main class where all the methods and work is taking place. public class list { link first; public list() { first = null; } public void insertatstart(int d) { link newlink = new link(d); newlink.next = first; first = newlink; } public link delfirst() { link temp = first; first = first.next; return temp; } public void displaylist() { link curr = first; System.out.println(“Printing the linked list”); while(curr != null) { System.out.println(curr.i); curr = curr.next; } } public void insertlast(int s) { link curr = first; while(curr.next != null) { curr = curr.next; } link newlink = new link(s); newlink.next = curr.next; curr.next = newlink; } public void insspeclinks(int t, int j) { link curr = first; while(curr.i != t) { curr = curr.next; } link newlink = new link(j); newlink.next = curr.next; curr.next = newlink; } public void delspeclink(int key) { link curr = first; link prev = first; while(curr.i != key) { prev = curr; curr = curr.next; } prev.next = curr.next; curr = null; } public void reverse() { link temp = null; link curr = first; link next = curr.next; while(next != null) { curr.next = temp; temp = curr; curr = next; next = next.next; } first = curr; first.next = temp; } } ********************************************** //Tester class to test the program public class linktest { public static void main(String [] args) { list l = new list(); l.insertatstart(3); l.insertatstart(6); l.insertatstart(7); l.insertatstart(8); l.displaylist(); l.insertlast(111); l.insertlast(222); l.insertlast(333); l.displaylist(); l.delfirst(); l.delfirst(); l.displaylist(); l.insspeclinks(111, 112); l.displaylist(); l.delspeclink(222); l.displaylist(); l.reverse(); System.out.println(“rev”); l.displaylist(); } } |
Category Archives: Java
Implementing Stack and queues in Java
//Implementing a queue (FIFO) first in first out
public class queue {
Object[] array; int start, end;
public queue(int c) { array = new Object[c]; start = end =0;
}
public void add(Object a) { array[start = (++start % array.length)] = a; System.out.println(“Added to queue: “+array[start]); } public void remove() { System.out.println(“Removed: “+array[end = (++end % array.length)] ); array[end = (++end % array.length)] = null;
} }
********************************************** //Implementing a stack
public class stack {
Object[] array; int pointer = -1; //Constructor to initiaize the array i.e. stack
public stack(int c) { int capacity = c; array = new Object[capacity]; }
//Adding a object to array public void add ( Object a){
pointer++; array[pointer] = a; System.out.println(“Pushed: “+a); }
//As it is LIFO you do not need to ask which object to remove public void remove() { System.out.println(“Removed: ” +array[pointer]); array[pointer] = null; pointer–;
} }
************************************ //Tester class to test the program
public class stacktest {
public static void main(String [] args) { System.out.println(“Starting stack implementation LIFO”); stack s = new stack(10); s.add(1); s.add(2); s.add(3); s.add(4); s.remove(); s.add(5);
System.out.println(“Starting queue implementation FIFO”); queue q = new queue(10); q.add(1); q.add(2); q.add(3); q.add(4); q.remove(); q.add(5); } } |
Count number of binary ones in an Integer using Java
//To count the number of ones in a Integer we can either use brute force O(n) or //we can ‘AND’ the number with number-1 until num becomes zero //keep a count for how many times the loop runs whic is the ans public class bit {
public static void main(String [] args) { int a = 5; int b = 6; int count = 0; int c; for(c = a ^ b; c != 0; c = c >> 1) { count += c & 1; } System.out.println(count); } } |
Check if two Strings are anagrams or not in Java
//Here the main concept is to add the ascii values and if they are same then the strings are anagrams else not
import java.util.*;
public class anagrams {
public static void main(String [] args){
String a = “madam”;
String b = “damma”;
int sum1 =0;
int sum2=0;
char[] c = a.toCharArray();
char[] d = b.toCharArray();
if(c.length == d.length)
{
for (int i =0; i < c.length ; i++)
{
sum1 += c[i];
sum2 += d[i];
}
if(sum1 == sum2){
System.out.println(“They are anagrams”);
}
else{
System.out.println(“They are not”);
}
}
else{
System.out.println(“They are not”);
}
Arrays.sort(c);
Arrays.sort(d);
if(Arrays.equals(c, d) )
{
System.out.println(“They are anagrams”);
}
else{
System.out.println(“They are not “);
}
}
}
Checking for unique charecters in a String using Java
import java.util.HashMap;
//If no addition data structures can be used then we need to comapare each and every charecter with
//all the charectersi in a string
//We can also use the boolean array to check for duplicate charesters in the string
public class uniquestr {
public static void main(String [] args){
String s = “Ishan”;
char[] c = s.toCharArray();
HashMap< Character, Integer> map = new HashMap<Character, Integer>();
for(char i : c){
if(map.containsKey(i))
{
map.put(i, map.get(i) +1);
System.out.println(“The string contains duplicate charecter ” + i);
}
else
map.put(i, 1);
}
}
}
Binary Search program in Java
//Here you basically take three pointers one at the start of the array one at the end and one at the mid. //Then compare with the element to be found if greater then increment the start to mid+1 and less then //decrement the end to mid -1. Keep going on until start not equal to end. public class arrayserach {
int[] array = {1,2,3,4,5,6,7,8,9,12,34,345,462,545,777,778,999,1001,1002,1111,1112,1113}; int start, end , mid, count;
public arrayserach(){
start = 0; end = array.length – 1; mid = (array.length/2) – 1; count = 0; }
public int search(int i) {
while(start != end) { count++; if(i ==array[start]) { System.out.println(“Found num: “+i+ “at index: “+start); System.out.println(count); return 1; }
if(i == array[end]){ System.out.println(“Found num: “+i+”at index: “+end); System.out.println(count); return 1;
}
if(i == array[mid]){ System.out.println(“Found num”+i+”at index: “+mid); System.out.println(count); return 1; }
if(array[mid] > i) { end = mid -1; mid = (start + end) / 2; continue; } if(array[mid] < i) { start = mid +1; mid = (start + end) /2; continue; } } if(array[end] == i){ System.out.println(“Found”); System.out.println(count); return 1; } return count; }
} |