COMPLETE DATA STRUCTURES LAB JAVA PROGRAMS (1 -

16)

1. Student Attendance Record using Array

import [Link];

public class AttendanceArray {

public static void main(String[] args) {

Scanner sc = new Scanner([Link]);

int[] attendance = new int[10];

int n = 0, choice, pos, value;

do {

[Link]("\[Link] [Link] [Link] [Link]");

choice = [Link]();

switch(choice) {

case 1:
[Link]("Enter attendance value: ");
value = [Link]();

attendance[n] = value;
n++;
break;

case 2:
[Link]("Enter position to delete: ");
pos = [Link]();

for(int i = pos; i < n - 1; i++) {

attendance[i] = attendance[i + 1];
}

n--;
break;

case 3:
[Link]("Attendance Records:");

for(int i = 0; i < n; i++) {

[Link](attendance[i] + " ");
}

[Link]();
break;
}

} while(choice != 4);

[Link]();
}
}

2. Supermarket Sales using Array

import [Link];

public class SalesArray {

public static void main(String[] args) {

Scanner sc = new Scanner([Link]);

int[] sales = new int[20];

int n = 0, choice, pos, value;

do {

[Link]("\[Link] Sale [Link] Sale [Link] [Link]");

choice = [Link]();
switch(choice) {
 case 1:
[Link]("Enter sales amount: ");
value = [Link]();

sales[n++] = value;
break;

case 2:
[Link]("Enter position to remove: ");
pos = [Link]();

for(int i = pos; i < n - 1; i++) {

sales[i] = sales[i + 1];
}

n--;
break;

case 3:
[Link]("Sales Records:");

for(int i = 0; i < n; i++) {

[Link](sales[i] + " ");
}

[Link]();
break;
}

} while(choice != 4);

[Link]();
}
}

3. Railway Reservation using Singly Linked List

class Node {
int data;
Node next;

Node(int data) {
[Link] = data;
next = null;
}
}

public class RailwayLinkedList {

Node head;

void insert(int data) {

Node newNode = new Node(data);

if(head == null) {
head = newNode;
} else {

Node temp = head;

while([Link] != null) {
temp = [Link];
}

[Link] = newNode;
}
}

void delete(int key) {

Node temp = head;

Node prev = null;

if(temp != null && [Link] == key) {

head = [Link];
return;
}

while(temp != null && [Link] != key) {

prev = temp;
temp = [Link];
}
if(temp != null) {
 [Link] = [Link];
}
}

void display() {

Node temp = head;

while(temp != null) {
[Link]([Link] + " ");
temp = [Link];
}

[Link]();
}

public static void main(String[] args) {

RailwayLinkedList list = new RailwayLinkedList();

[Link](101);
[Link](102);
[Link](103);

[Link]();

[Link](102);

[Link]();
}
}

4. Music Playlist using Doubly Linked List

class DNode {

int data;
DNode prev, next;

DNode(int data) {
[Link] = data;
}
}

public class DoublyPlaylist {

DNode head;

void insert(int data) {

DNode newNode = new DNode(data);

if(head == null) {
head = newNode;
} else {

DNode temp = head;

while([Link] != null) {
temp = [Link];
}

[Link] = newNode;
[Link] = temp;
}
}

void delete(int key) {

DNode temp = head;

while(temp != null && [Link] != key) {

temp = [Link];
}

if(temp == null)
return;

if([Link] != null)
[Link] = [Link];
else
head = [Link];

if([Link] != null)
 [Link] = [Link];
}

void forwardDisplay() {

DNode temp = head;

while(temp != null) {
[Link]([Link] + " ");

if([Link] == null)
break;

temp = [Link];
}

[Link]();
}

void backwardDisplay() {

DNode temp = head;

while([Link] != null) {
temp = [Link];
}

while(temp != null) {
[Link]([Link] + " ");
temp = [Link];
}

[Link]();
}

public static void main(String[] args) {

DoublyPlaylist d = new DoublyPlaylist();

[Link](1);
[Link](2);
[Link](3);

[Link]();
[Link]();

[Link](2);

[Link]();
}
}

5. Browser History using Stack

import [Link];

public class BrowserStack {

public static void main(String[] args) {

Stack<String> stack = new Stack<>();

[Link]("Google");
[Link]("YouTube");
[Link]("Wikipedia");

[Link]("Browser History:");
[Link](stack);

[Link]();

[Link]("After Back Navigation:");

[Link](stack);
}
}

6. Stack using Linked List

class StackNode {
int data;
 StackNode next;

StackNode(int data) {
[Link] = data;
}
}

public class StackLinkedList {

StackNode top;

void push(int data) {

StackNode newNode = new StackNode(data);

[Link] = top;
top = newNode;
}

void pop() {

if(top == null) {
[Link]("Stack Empty");
} else {
[Link]("Deleted: " + [Link]);
top = [Link];
}
}

void display() {

StackNode temp = top;

while(temp != null) {
[Link]([Link] + " ");
temp = [Link];
}

[Link]();
}

public static void main(String[] args) {

StackLinkedList s = new StackLinkedList();

[Link](10);
[Link](20);
[Link](30);

[Link]();

[Link]();

[Link]();
}
}

7. Queue using Array

public class QueueArray {

int[] queue = new int[5];

int front = -1;
int rear = -1;

void enqueue(int data) {

if(rear == 4) {
[Link]("Queue Full");
} else {

if(front == -1)
front = 0;

queue[++rear] = data;
}
}

void dequeue() {

if(front == -1 || front > rear) {

[Link]("Queue Empty");
} else {
[Link]("Removed: " + queue[front++]);
 }
}

void display() {

for(int i = front; i <= rear; i++) {

[Link](queue[i] + " ");
}

[Link]();
}

public static void main(String[] args) {

QueueArray q = new QueueArray();

[Link](1);
[Link](2);
[Link](3);

[Link]();

[Link]();

[Link]();
}
}

8. Queue using Linked List

class QNode {

int data;
QNode next;

QNode(int data) {
[Link] = data;
}
}

public class QueueLinkedList {

QNode front, rear;

void enqueue(int data) {

QNode newNode = new QNode(data);

if(rear == null) {
front = rear = newNode;
return;
}

[Link] = newNode;
rear = newNode;
}

void dequeue() {

if(front == null) {
[Link]("Queue Empty");
return;
}

[Link]("Removed: " + [Link]);

front = [Link];

if(front == null)
rear = null;
}

void display() {

QNode temp = front;

while(temp != null) {
[Link]([Link] + " ");
temp = [Link];
}

[Link]();
}

public static void main(String[] args) {

 QueueLinkedList q = new QueueLinkedList();

[Link](11);
[Link](22);
[Link](33);

[Link]();

[Link]();

[Link]();
}
}

9. BST Program
class TreeNode {

int data;
TreeNode left, right;

TreeNode(int data) {
[Link] = data;
}
}

public class BSTExample {

TreeNode root;

TreeNode insert(TreeNode root, int data) {

if(root == null)
return new TreeNode(data);

if(data < [Link])

[Link] = insert([Link], data);
else
[Link] = insert([Link], data);

return root;
}

boolean search(TreeNode root, int key) {

if(root == null)
return false;

if([Link] == key)
return true;

if(key < [Link])

return search([Link], key);

return search([Link], key);

}

void inorder(TreeNode root) {

if(root != null) {
inorder([Link]);
[Link]([Link] + " ");
inorder([Link]);
}
}

public static void main(String[] args) {

BSTExample tree = new BSTExample();

[Link] = [Link]([Link], 50);

[Link]([Link], 30);
[Link]([Link], 70);

[Link]([Link]);

[Link]("\nSearch 30: " + [Link]([Link], 30));

}
}

10. AVL Tree

 class AVLNode {

int key, height;

AVLNode left, right;

AVLNode(int d) {
key = d;
height = 1;
}
}

public class AVLTree {

AVLNode root;

int height(AVLNode n) {
return (n == null) ? 0 : [Link];
}

int getBalance(AVLNode n) {
return (n == null) ? 0 : height([Link]) - height([Link]);
}

AVLNode rightRotate(AVLNode y) {

AVLNode x = [Link];
AVLNode t2 = [Link];

[Link] = y;
[Link] = t2;

[Link] = [Link](height([Link]), height([Link])) + 1;

[Link] = [Link](height([Link]), height([Link])) + 1;

return x;
}

AVLNode insert(AVLNode node, int key) {

if(node == null)
return new AVLNode(key);

if(key < [Link])

[Link] = insert([Link], key);
else if(key > [Link])
[Link] = insert([Link], key);
else
return node;

[Link] = 1 + [Link](height([Link]), height([Link]));

int balance = getBalance(node);

if(balance > 1 && key < [Link])

return rightRotate(node);

return node;
}
}

11. DFS Traversal

public class DFSGraph {

int vertices = 5;

int[][] graph = {
{0,1,1,0,0},
{1,0,0,1,1},
{1,0,0,0,0},
{0,1,0,0,0},
{0,1,0,0,0}
};

boolean[] visited = new boolean[5];

void dfs(int v) {

visited[v] = true;

[Link](v + " ");

for(int i = 0; i < vertices; i++) {

if(graph[v][i] == 1 && !visited[i]) {
 dfs(i);
}
}
}

public static void main(String[] args) {

DFSGraph g = new DFSGraph();

[Link](0);
}
}

12. BFS Traversal

import [Link];
import [Link];

public class BFSGraph {

int vertices = 5;

int[][] graph = {
{0,1,1,0,0},
{1,0,0,1,1},
{1,0,0,0,0},
{0,1,0,0,0},
{0,1,0,0,0}
};

void bfs(int start) {

boolean[] visited = new boolean[vertices];

Queue<Integer> q = new LinkedList<>();

visited[start] = true;
[Link](start);

while(![Link]()) {

int v = [Link]();

[Link](v + " ");

for(int i = 0; i < vertices; i++) {

if(graph[v][i] == 1 && !visited[i]) {

visited[i] = true;
[Link](i);
}
}
}
}

public static void main(String[] args) {

BFSGraph g = new BFSGraph();

[Link](0);
}
}

13. Hashing with Linear Probing

public class LinearProbing {

int size = 10;

int[] hashTable = new int[size];

LinearProbing() {

for(int i = 0; i < size; i++) {

hashTable[i] = -1;
}
}

void insert(int key) {

int index = key % size;
 while(hashTable[index] != -1) {
index = (index + 1) % size;
}

hashTable[index] = key;
}

void search(int key) {

int index = key % size;

while(hashTable[index] != -1) {

if(hashTable[index] == key) {
[Link]("Key Found");
return;
}

index = (index + 1) % size;

}

[Link]("Key Not Found");

}

public static void main(String[] args) {

LinearProbing h = new LinearProbing();

[Link](10);
[Link](20);
[Link](30);

[Link](20);
}
}

14. Hashing with Chaining

import [Link];

public class HashChaining {

int size = 10;

LinkedList<Integer>[] table = new LinkedList[size];

HashChaining() {

for(int i = 0; i < size; i++) {

table[i] = new LinkedList<>();
}
}

void insert(int key) {

int index = key % size;

table[index].add(key);
}

void search(int key) {

int index = key % size;

if(table[index].contains(key))
[Link]("Key Found");
else
[Link]("Key Not Found");
}

public static void main(String[] args) {

HashChaining h = new HashChaining();

[Link](15);
[Link](25);
[Link](35);

[Link](25);
}
}
15. Bubble Sort
public class BubbleSort {

public static void main(String[] args) {

int[] marks = {78, 45, 90, 32, 67};

int n = [Link];

for(int i = 0; i < n - 1; i++) {

for(int j = 0; j < n - i - 1; j++) {

if(marks[j] > marks[j + 1]) {

int temp = marks[j];

marks[j] = marks[j + 1];
marks[j + 1] = temp;
}
}
}

[Link]("Sorted Array:");

for(int mark : marks) {

[Link](mark + " ");
}
}
}

16. Merge Sort

public class MergeSort {

void merge(int arr[], int left, int mid, int right) {

int n1 = mid - left + 1;

int n2 = right - mid;

int L[] = new int[n1];

int R[] = new int[n2];

for(int i = 0; i < n1; i++)

L[i] = arr[left + i];

for(int j = 0; j < n2; j++)

R[j] = arr[mid + 1 + j];

int i = 0, j = 0;
int k = left;

while(i < n1 && j < n2) {

if(L[i] <= R[j]) {

arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}

k++;
}

while(i < n1) {

arr[k] = L[i];
i++;
k++;
}

while(j < n2) {

arr[k] = R[j];
j++;
k++;
}
}

void sort(int arr[], int left, int right) {

if(left < right) {

int mid = (left + right) / 2;

 sort(arr, left, mid);
sort(arr, mid + 1, right);

merge(arr, left, mid, right);

}
}

public static void main(String[] args) {

int arr[] = {55, 23, 87, 12, 45, 90};

MergeSort m = new MergeSort();

[Link](arr, 0, [Link] - 1);

for(int i : arr) {
[Link](i + " ");
}
}
}