Scribd
Upload
3 views11 pages

DS Using Java Lab (University Program)

Data Structure using Java lab

Uploaded by

dead wish
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
3 views11 pages

DS Using Java Lab (University Program)

Data Structure using Java lab

Uploaded by

dead wish
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
LIST OF EXERCISES: 1. Write @ Java programs to implement the List ADT using arrays and linked lists. [Link] ¢ Java programs to implement the following using a singly linked list. Stack ADT (b) Queue ADT 3. Write @ java program that reads an infix expression, converts the expression to postfix form and then evaluates the postfix expression (use stack ADT). 4, Write @ Java program to implement priority queue ADT. [Link] a Java program to perform the following operations: (a) _ Insert an element into a binary search tree. (b) Delete an element from a binary search tree. (©) Search for a key element in a binary search tree. 6. Write 2 Java program to pe-form the following operations (a) _ Insertion into an AVL-tree (b) Deletion from an AVL-tree [Link] e Java programs for the implementation of BFS for a given graph. 8. Write a Java programs for the implementation of DFS for a given graph 9. Write a Java programs for implementing the following searching methods: (a) Linear search (b) Binary search. 10. Write a Java programs for implementing the following sorting methods (a) Bubble sort (b) Selection sort (c) _ Insertion sort (d) Radix sort. [Link] a Java programs to implement the List ADT using arrays and linked lists. a) ADT using arrays leave two page space b) Linked List public class singlyLinkedList { //Represent a node of the singly linked list class Node{ int data; Node next; public Node(int data) { [Link] = data; [Link] = null; } } //Represent the head and tail of the singly linked list, public Node head = null; public Node tail = null; /faddNode() will add a new nodeto thelist public void addNode(int data) { 1/Create anew node Node newNode = new Node(data); 1/Checks if the list is empty if(head == null) { /{Mf list is empty, both head end tail will point to new node head = newNode; tail = newNode; } else { //newNode will be added after tail such that tail’s next will point to newNode [Link] = newNode; //newNode will become new tail of the list tail = newNode; } } //display() will display all the nodes present in thelist public void display) { //Node current will point to head Node current = head; if(head == null) { System out printin(’List is empty"); return; } [Link](’Nodes of singly linked list: "); while(current != null) { /|Prints each node by incrementing pointer System out print([Link] +"); current = [Link], } System. out printinO; } public static void main(Stingl] args) { singlyLinkedList sList = new singlyLinkedList0; //sListaddNode(; Add nodes to the list [Link](1); [Link](2); [Link](3), [Link](4); //Displays the nodes present in the list [Link](); } } [Link] a Java programs to implement the following using a singly linked list. Stack ADT (b) Queue ADT a)Stack ADT import [Link].*; import [Link]; class StkList { StackNode root; static class StackNode { int data; StackNode next; StackNode(int data) {[Link] = data; } } public void push(int data) { StackNode newNode = new StackNode(data); if (root == null) { root = newNode; } else { StackNode temp = root; root = newNode; [Link] = temp; } System out printin(data +" pushed to stack’); } public void pop() { int popped = Integer. MIN_VALUE; if (Foot == null) { [Link]('Stack is Empty"); } else { popped = [Link]; root = root next; } System out printin("\n the element popped fram stack\n"+popped); } void display() { if (root == null) ‘ystem out printin(‘Stack is empty’); } StackNode tmp1=root; while(tmpt!= null) { [Link] print([Link]+'\n’); imp1=[Link]; } } class stklinked public static void main(String[] args)throws IOException BufferedReader br=new BufferedReader{new [Link])); StkList s = new StkList(); int ch ; do { [Link](‘\n1 push’); System. out printin('[Link]"); System. out printin('[Link]’); [Link] printin(‘enter your choice\n’); ch =[Link]([Link]()); switch(ch) { casel int x=Integer parselnt(brreadLine(); spush(x); break; case 2: s.pop0); break case 3: [Link](; break default: [Link](‘invalid choice’); break; } Jwhile(ch>=1&&ch<=3); } } b)Queue ADT class QNode { int key; QNode next; // constructor to create a new linked list node public QNode(int key) { [Link] = key; [Link] = null; } } class Queue { QNode front, rear; public Queue() { [Link] = [Link] = null; } // Method to add an key to the queue. void enqueue(int key) { // Create a new LL node QNode temp = new QNode(key); // |i queue is empty, then new node is front and rear both if ([Link] == null) { thisfront = [Link] = temp; return; } // Add the new node at the end of queue and change rear [Link] = temp; [Link] = temp; } // Method to remove an key from queue. void dequeue() { //|f queue is empty, return NULL. if (this front == null) return; // Store previous front and move front one node ahead QNode temp = [Link] [Link] = [Link], // Kf front becomes NULL, then change rear also as NULL if (this front == null) [Link]= null; /! Driver class public class queuelinked{ public static void main(Stringl] args) { Queue q = new Queue(); [Link](10); [Link](20); [Link](); [Link](); [Link](30); [Link](40); [Link](50); [Link](); System. out printin("Queue Front :' + [Link] key); System. out printin("‘Queue Rear : "+ [Link] key); [Link] a java program that reads an infix expression, converts the expression to postfix form and then evaluates the postfix expression (use stack ADT). import [Link]. Stack, import [Link]*; class Test { // utility function to return // precedence of a given operator // Higher returned value means // higher precedence static int Preo(char ch) { switch (ch) { case '+': case“! return 1; case* case'/' return 2; case" return 3; } return -1; } // The main method that converts // given infix expression // 10 postfix expression String infixToPostfix(String exp) { // initializing empty String for result String result = new Strin // initializing empty stack Stack stack = new Stacko(); for (inti = 0; i<[Link](; ++i) { char = [Link](i); // If the scanned character is an /f operand, add it to output. if (CharacterisLetterOrDigit(c)) result += c; 7 \f the scanned character is an'(, 1 push it to the stack elseif (c == '() stack push(c); // \fthe scanned character is an’), J! pop and output from the stack // until an '( is encountered. elseif (¢ ==')) { while ([Link]() &&[Link]() = '() result += [Link](); stack. pop); } else // an operator is encountered while (‘[Link]() &8 Preo(c) rec([Link]())){ result += [Link](); } stack push(c); } } // pop all the operators from the stack while (‘stack isEmpty()) { if(stack peek() = return “Invalid Expression’; result += stack pop(); } return result; } d/ Driver method static int evalpostfix(String exp1) Stack stack=new Stack<>(); for(int i=O;i

You might also like