Linked List(Insert Delete Reverse search display) in Java

//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();

}

}

Advertisements

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;

}

 

}