LinkedList
singlelinkedlist
package com.demo.linkedlist;
public class SinglyLinkedList {
class Node{
int data;
Node next;
public Node(int data) {
super();
this.data = data;
this.next=null;
}
}
Node head;
public SinglyLinkedList() {
head=null;
}
//add newnode at the end
public void addNode(int val){
//to create a new node
Node newnode=new Node(val);
//if list is empty, then add at the begining
if(head==null) {
head=newnode;
}else {
Node temp=head;
while(temp.next!=null) {
temp=temp.next;
}
temp.next=newnode;
}
}
public int searchbyvalue(int val) {
if(head==null) {
System.out.println("List is empty");
}else {
Node temp=head;
int pos=0;
while(temp!=null && temp.data!=val) {
temp=temp.next;
pos++;
}
if(temp!=null) {
return pos;
}
}
return -1;
}
public void addByPosition(int val,int pos) {
if(head==null && pos>1) {
System.out.println("list is empty");
}else {
Node newnode=new Node(val);
//add before current head
if(pos==1) {
newnode.next=head;
head=newnode;
}else {
Node temp=head;
//place the temp at the node, after which we want to add data
for(int i=1;temp!=null && i<=pos-2;i++) {
temp=temp.next;
}
if(temp!=null) {
newnode.next=temp.next;
temp.next=newnode;
}else {
System.out.println("The given position beyond the limit of list");
}
}
}
}
public void addByValue(int val) {
}
//delete the node by value
public void deleteByValue(int val) {
//check whether list is empty
if(head==null) {
System.out.println("the list is empty");
}else {
Node temp=head, prev=null;
//check whetehr to delete thefirst node
if(head.data==val) {
head=temp.next;
temp.next=null;
temp=null;
}else {
//delete in between or last node
while(temp!=null && temp.data!=val) {
prev=temp;
temp=temp.next;
}
if(temp!=null) {
prev.next=temp.next;
temp.next=null;
temp=null;
}else {
System.out.println("data not found");
}
}
}
}
public void deleteByPosition(int pos) {
if(head==null) {
System.out.println("list is empty");
}else {
Node temp=head,prev=null;
if(pos==1) {
head=temp.next;
temp.next=null;
temp=null;
}else {
for(int i=1;temp!=null && i<=pos-1;i++) {
prev=temp;
temp=temp.next;
}
if(temp!=null) {
prev.next=temp.next;
temp.next=null;
temp=null;
}else {
System.out.println("position is beyond the length of the list");
}
}
}
}
//to display values of all nodes
public void displaydata() {
if(head==null) {
System.out.println("list is empty");
}else {
Node temp=head;
while(temp!=null) {
System.out.println(temp.data+" ");
temp=temp.next;
}
System.out.println("------------------------------------------");
}
}
}
//test
package com.demo.test;
import com.demo.linkedlist.SinglyLinkedList;
public class TestSinglyLinkedList {
public static void main(String[] args) {
SinglyLinkedList lst=new SinglyLinkedList();
lst.addNode(3);
lst.addNode(5);
lst.addNode(7);
lst.addNode(8);
lst.displaydata();
lst.addByPosition(100, 2);
lst.displaydata();
/*lst.addByPosition(500, 1);
lst.displaydata();
lst.addByPosition(600, 7);
lst.displaydata();
lst.addByPosition(700, 10);
lst.displaydata();*/
// lst.deleteByValue(300);
lst.deleteByPosition(12); //test for 1, 3, 5
lst.displaydata();
}
}
--------------------------------------------------------------------------------------------------------------------------------------
//sorted linked list
package com.demo.linkedlist;
import com.demo.linkedlist.SinglyLinkedList.Node;
public class SinglySortedList {
class Node{
int data;
Node next;
public Node(int data) {
super();
this.data = data;
this.next=null;
}
}
Node head;
public SinglySortedList() {
head=null;
}
public void addInSortedOrder(int val) {
Node newnode=new Node(val);
if(head==null) {
head=newnode;
}else {
Node temp=head,prev=null;
if(head.data>val) {
newnode.next=head;
head=newnode;
}else {
while(temp!=null && temp.data<val) {
prev=temp;
temp=temp.next;
}
newnode.next=prev.next;
prev.next=newnode;
}
}
}
//to display values of all nodes
public void displaydata() {
if(head==null) {
System.out.println("list is empty");
}else {
Node temp=head;
while(temp!=null) {
System.out.println(temp.data+" ");
temp=temp.next;
}
System.out.println("------------------------------------------");
}
}
}
// testfile
package com.demo.test;
import com.demo.linkedlist.SinglySortedList;
public class TestSortedLinkedList {
public static void main(String[] args) {
SinglySortedList lst=new SinglySortedList();
lst.addInSortedOrder(5);
lst.addInSortedOrder(9);
lst.addInSortedOrder(7);
lst.addInSortedOrder(3);
lst.displaydata();
}
}
----------------------------------------------------------------------------------------------------------------------------------------
//circular linked list
package com.demo.linkedlist;
public class CircularLinkedList {
Node head,tail;
class Node{
int data;
Node next;
public Node(int data) {
super();
this.data = data;
this.next=null;
}
}
public CircularLinkedList() {
head=null;
tail=null;
}
//add at the end of the list
public void addNode(int val) {
Node newnode=new Node(val);
if(head==null) {
head=newnode;
tail=newnode;
}else {
tail.next=newnode;
tail=newnode;
}
tail.next=head;
}
public void addByPosition(int val, int pos) {
if(head==null) {
System.out.println("the list is empty");
}else {
Node newnode=new Node(val);
if(pos==1) {
newnode.next=head;
head=newnode;
tail.next=newnode;
}else {
Node temp=head;
int i=1;
for(;temp.next!=head && i<=pos-2;i++) {
temp=temp.next;
}
//whether we reached to required position
if(i>pos-2) {
if(temp.next==head) {
//add at the end
tail=newnode;
}
newnode.next=temp.next;
temp.next=newnode;
}else {
System.out.println("position is beyond the limit");
}
}
}
}
public void displaydata() {
if(head==null)
System.out.println("list is empty");
else {
Node temp=head;
while(temp.next!=head) {
System.out.println(temp.data);
temp=temp.next;
}
System.out.println(temp.data);
System.out.println("--------------");
}
}
}
---------------------------------------------------------------------------------------------------------------------------------------
//doubly linkedlist
package com.demo.linkedlist;
public class DoublyLinkedList {
Node head;
class Node{
int data;
Node prev,next;
public Node(int data) {
super();
this.data = data;
prev=null;
next=null;
}
}
public DoublyLinkedList() {
head=null;
}
//add at the ned
public void addNode(int val) {
Node newnode=new Node(val);
if(head==null) {
head=newnode;
}else {
Node temp=head;
while(temp.next!=null) {
temp=temp.next;
}
temp.next=newnode;
newnode.prev=temp;
}
}
public void addBeforeKey(int val,int key) {
if(head==null) {
System.out.println("List is empty");
}else {
//adding before head
Node newnode=new Node(val);
if(head.data==key) {
newnode.next=head;
head.prev=newnode;
head=newnode;
}else {
Node temp=head;
while(temp!=null && temp.data!=key) {
temp=temp.next;
}
if(temp!=null) {
newnode.next=temp;
newnode.prev=temp.prev;
temp.prev.next=newnode;
temp.prev=newnode;
}else {
System.out.println("key not found");
}
}
}
}
public void addAfterKey(int val,int key) {
if(head==null) {
System.out.println("List is empty");
}else {
Node newnode=new Node(val);
Node temp=head;
while(temp!=null && temp.data!=key) {
temp=temp.next;
}
if(temp!=null) {
newnode.next=temp.next;
newnode.prev=temp;
if(temp.next!=null) {
temp.next.prev=newnode;
}
temp.next=newnode;
}
}
}
public void deleteByPosition(int pos) {
Node temp=head;
if(pos==1) {
if(head!=null) {
head=head.next;
if(temp.next!=null)
temp.next.prev=null;
temp.next=null;
temp=null;
}else {
System.out.println("position beyond the limit");
}
}else {
for(int i=1;temp!=null && i<=pos-1;i++) {
temp=temp.next;
}
if(temp!=null) {
temp.prev.next=temp.next;
if(temp.next!=null) {
temp.next.prev=temp.prev;
}
temp.next=null;
temp.prev=null;
temp=null;
}
}
}
public void addByPosition(int val,int pos) {
Node newnode=new Node(val);
//add node in th begining
if(pos==1) {
if(head==null)
head=newnode;
else {
newnode.next=head;
head.prev=newnode;
head=newnode;
}
}else {
Node temp=head;
for(int i=0;temp!=null && i<pos-2;i++) {
temp=temp.next;
}
if(temp==null) {
System.out.println("Given position is beyond the limit");
}else {
newnode.next=temp.next;
//adding in between
if(temp.next!=null)
temp.next.prev=newnode;
newnode.prev=temp;
temp.next=newnode;
}
}
}
public void displayData() {
Node temp=head;
if(head!=null) {
while(temp!=null) {
System.out.print(temp.data+" , ");
temp=temp.next;
}
System.out.println("-----------------------");
}
}
public void displayDatainReverseOrder() {
Node temp=head;
while(temp.next!=null) {
temp=temp.next;
}
while(temp!=null) {
System.out.print(temp.data+" , ");
temp=temp.prev;
}
System.out.println("-----------------------");
}
}
//test
package com.demo.test;
import com.demo.linkedlist.DoublyLinkedList;
public class TestDoublyLinkedList {
public static void main(String[] args) {
DoublyLinkedList dlist=new DoublyLinkedList();
dlist.addNode(2);
dlist.addNode(3);
dlist.addNode(5);
dlist.addNode(1);
dlist.addNode(10);
dlist.displayData();
dlist.displayDatainReverseOrder();
dlist.addBeforeKey(11,1);
dlist.displayData();
dlist.addBeforeKey(100,2);
dlist.displayData();
dlist.addAfterKey(33,10);
dlist.displayData();
dlist.deleteByPosition(2);
}
}
--------------------------------------------------------------------------------------------------------------------------------
//stack
package com.demo.stacks;
import java.util.Arrays;
public class MyArrayStack {
private int[] arr;
private int top;
public MyArrayStack() {
top=-1;
arr=new int[10];
}
public MyArrayStack(int size) {
top=-1;
arr=new int[size];
}
public boolean isEmpty() {
return top==-1;
}
public boolean isFull() {
return top==arr.length-1;
}
public void push(int val) {
if(isFull()) {
System.out.println("Stack is full");
}else {
top++;
arr[top]=val;
}
}
public int pop() {
if(isEmpty()) {
System.out.println("stack is empty");
}else {
int n=arr[top];
top--;
return n;
}
return -1;
}
}
--------------------------------------------------------------------------------------------------------------------------------
//stack using linked list
package com.demo.stacks;
public class MyListStack {
private Node top;
class Node{
int data;
Node next;
public Node(int val) {
data=val;
next=null;
}
}
public MyListStack() {
top=null;
}
public boolean isEmpty() {
return top==null;
}
public void push(int n) {
Node newnode=new Node(n);
if(top==null) {
top=newnode;
}else {
newnode.next=top;
top=newnode;
}
}
public int pop() {
if(isEmpty()) {
System.out.println("stack is empty");
}else {
Node temp=top;
top=temp.next;
temp.next=null;
return temp.data;
}
return -1;
}
}
----------------------------------------------------------------------------------------------------------------------------------------
// test parenthesis
package com.demo.test;
import com.demo.stacks.MyStack;
public class TestBalnceParenthesis {
public static void main(String[] args) {
//String str="{{{[](){}}}}";
String str="{{{[](){}}}]}";
MyStack st=new MyStack(20);
boolean flag=isBalanced(st,str);
if(flag) {
System.out.println("The string has balanced parenthesis");
}else {
System.out.println("The string has not balanced parenthesis");
}
}
private static boolean isBalanced(MyStack st, String str) {
for(int i=0;i<str.length();i++) {
char ch=str.charAt(i);
if(ch=='(' || ch=='[' || ch=='{') {
st.push(ch);
}else {
if(!st.isEmpty()) {
char ch1=st.pop();
// if we could not find matching opening bracket in stack
if((ch=='}' && ch1!='{') || (ch==')' && ch1!='(') || (ch==']' && ch1!='[')){
return false;
}
}else { // string is not yet finished but stack is empty
return false;
}
}
}
if(st.isEmpty()) {
return true;
}else { //stack is not empty, but string is finished
return false;
}
}
}
----------------------------------------------------------------------------------------------------------------------------------------
//myarrayqueue
package com.demo.queue;
public class MyArrayQueue {
int[] arr;
int front;
int rear;
public MyArrayQueue() {
front=0;
rear=0;
arr=new int[10];
}
public MyArrayQueue(int size) {
front=0;
rear=0;
arr=new int[size];
}
public void enqueue(int val) {
if(isFull()) {
System.out.println("Queue is full");
}
else {
arr[rear]=val;
rear++;
}
}
public int dequeue() {
if(isEmpty()) {
System.out.println("Queue is empty");
}else {
int n=arr[front];
front++;
return n;
}
return -1;
}
public boolean isEmpty() {
return front==rear;
}
public boolean isFull() {
return rear==arr.length;
}
}
------------------------------------------------------------------------------------------------------------------------------------
//circular queue
package com.demo.queue;
import java.util.Arrays;
public class MyCircularQueue {
int[] arr;
int front;
int rear;
public MyCircularQueue() {
front=-1;
rear=-1;
arr=new int[10];
}
public MyCircularQueue(int size) {
front=-1;
rear=-1;
arr=new int[size];
}
public boolean isFull() {
if(front==0 && rear==arr.length-1)
return true;
if(front==rear+1)
return true;
return false;
}
public boolean isEmpty() {
return front==-1;
}
public void enqueue(int val) {
if(isFull()) {
System.out.println("Queue is full");
}
//it will place front to 0, when only one element in the queue at oth position
if(front==-1)
front=0;
rear=(rear+1) % arr.length;
arr[rear]=val;
System.out.println(Arrays.toString(arr));
}
public int dequeue() {
if(isEmpty()) {
System.out.println("Queue is empty");
}else {
int n=arr[front];
//this checks whether all the values have been read, so queue should be restarted from 0
if(front==rear){
front=-1;
rear=-1;
}else {
front=(front+1)%arr.length;
}
System.out.println(Arrays.toString(arr));
return n;
}
System.out.println(Arrays.toString(arr));
return -1;
}
}
-----------------------------------------------------------------------------------------------------------------------------------------
// hashinglinked list
package com.demo.hashing;
public class MyHashingLinkedList {
Node head;
class Node{
int data;
Node next;
public Node(int data) {
super();
this.data = data;
this.next = null;
}
}
public MyHashingLinkedList() {
this.head = null;
}
public void addValue(int val) {
Node newnode=new Node(val);
if(head==null) {
head=newnode;
}else {
newnode.next=head;
head=newnode;
}
}
public boolean search(int val) {
if(head==null) {
return false;
}else {
Node temp=head;
while(temp!=null && temp.data!=val ) {
temp=temp.next;
}
if(temp!=null && temp.data==val)
return true;
else
return false;
}
}
public boolean deletedata(int val) {
if(head==null) {
return false;
}else {
Node temp=head;
if(head.data==val) {
head=head.next;
}else {
Node prev=null;
while(temp!=null && temp.data!=val ) {
prev=temp;
temp=temp.next;
}
if(temp.data==val) {
prev.next=temp.next;
}else {
return false;
}
}
temp.next=null;
temp=null;
return true;
}
}
public void displayList() {
if(head==null) {
System.out.print("empty");
}else {
Node temp=head;
while(temp!=null) {
System.out.print(temp.data+"--->");
temp=temp.next;
}
System.out.print("null");
}
}
}
///test
package com.demo.test;
import java.util.Scanner;
import com.demo.hashing.MyHashingLinkedList;
public class MyHashingDemo {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int num=7;
MyHashingLinkedList[] hashtable=new MyHashingLinkedList[num];
for(int i=0;i<hashtable.length;i++) {
hashtable[i]=new MyHashingLinkedList();
}
displayhashTable(hashtable);
int choice=0;
do {
System.out.println("1. Add data \n 2. Search data\n 3. delete data\n 4. exit\n choioce: ");
choice=sc.nextInt();
switch(choice) {
case 1->{
System.out.println("enetr number");
int val=sc.nextInt();
adddataInHashTable(hashtable, val);
displayhashTable(hashtable);
}
case 2->{
System.out.println("enetr number");
int val=sc.nextInt();
boolean status=searchdata(hashtable, val);
if(status) {
System.out.println("number found");
}else {
System.out.println("number not found");
}
}
case 3->{
System.out.println("enetr number");
int val=sc.nextInt();
boolean status=deleteFromHashTable(hashtable, val);
if(status) {
System.out.println("number deleted");
}else {
System.out.println("number not deleted");
}
displayhashTable(hashtable);
}
case 4->{
System.out.println("Thank you for hashing....");
sc.close();
}
default->System.out.println("Wrong choice....");
}
}while(choice!=4);
}
private static void adddataInHashTable(MyHashingLinkedList[] hashtable, int data) {
int bucket=data%hashtable.length;
hashtable[bucket].addValue(data);
}
private static boolean deleteFromHashTable(MyHashingLinkedList[] hashtable, int data) {
int bucket=data%hashtable.length;
return hashtable[bucket].deletedata(data);
}
private static boolean searchdata(MyHashingLinkedList[] hashtable, int data) {
int bucket=data%hashtable.length;
return hashtable[bucket].search(data);
}
private static void displayhashTable(MyHashingLinkedList[] hashtable) {
for(int i=0;i<hashtable.length;i++) {
System.out.print(i+"--->");
hashtable[i].displayList();
System.out.println();
}
System.out.println("--------------------------------------");
}
}
-------------------------------------------------------------------------------------------------------------------------------------------
Comments
Post a Comment