Category: dsa Using Java

DSA using Java – Heap ”; Previous Next Overview Heap represents a special tree based data structure used to represent priority queue or for heap sort. We”ll going to discuss binary heap tree specifically. Binary heap tree can be classified as a binary tree with two constraints − Completeness − Binary heap tree is a complete binary tree except the last level which may not have all elements but elements from left to right should be filled in. Heapness − All parent nodes should be greater or smaller to their children. If parent node is to be greater than its child then it is called Max heap otherwise it is called Min heap. Max heap is used for heap sort and Min heap is used for priority queue. We”re considering Min Heap and will use array implementation for the same. Basic Operations Following are basic primary operations of a Min heap which are following. Insert − insert an element in a heap. Get Minimum − get minimum element from the heap. Remove Minimum − remove the minimum element from the heap Insert Operation Whenever an element is to be inserted. Insert element at the end of the array. Increase the size of heap by 1. Heap up the element while heap property is broken. Compare element with parent”s value and swap them if required. public void insert(int value) { size++; intArray[size – 1] = value; heapUp(size – 1); } private void heapUp(int nodeIndex){ int parentIndex, tmp; if (nodeIndex != 0) { parentIndex = getParentIndex(nodeIndex); if (intArray[parentIndex] > intArray[nodeIndex]) { tmp = intArray[parentIndex]; intArray[parentIndex] = intArray[nodeIndex]; intArray[nodeIndex] = tmp; heapUp(parentIndex); } } } Get Minimum Get the first element of the array implementing the heap being root. public int getMinimum(){ return intArray[0]; } Remove Minimum Whenever an element is to be removed. Get the last element of the array and reduce size of heap by 1. Heap down the element while heap property is broken. Compare element with children”s value and swap them if required. public void removeMin() { intArray[0] = intArray[size – 1]; size–; if (size > 0) heapDown(0); } private void heapDown(int nodeIndex){ int leftChildIndex, rightChildIndex, minIndex, tmp; leftChildIndex = getLeftChildIndex(nodeIndex); rightChildIndex = getRightChildIndex(nodeIndex); if (rightChildIndex >= size) { if (leftChildIndex >= size) return; else minIndex = leftChildIndex; } else { if (intArray[leftChildIndex] <= intArray[rightChildIndex]) minIndex = leftChildIndex; else minIndex = rightChildIndex; } if (intArray[nodeIndex] > intArray[minIndex]) { tmp = intArray[minIndex]; intArray[minIndex] = intArray[nodeIndex]; intArray[nodeIndex] = tmp; heapDown(minIndex); } } Heap Implementation Heap.java package com.tutorialspoint.datastructure; public class Heap { private int[] intArray; private int size; public Heap(int size){ intArray = new int[size]; } public boolean isEmpty(){ return size == 0; } public int getMinimum(){ return intArray[0]; } public int getLeftChildIndex(int nodeIndex){ return 2*nodeIndex +1; } public int getRightChildIndex(int nodeIndex){ return 2*nodeIndex +2; } public int getParentIndex(int nodeIndex){ return (nodeIndex -1)/2; } public boolean isFull(){ return size == intArray.length; } public void insert(int value) { size++; intArray[size – 1] = value; heapUp(size – 1); } public void removeMin() { intArray[0] = intArray[size – 1]; size–; if (size > 0) heapDown(0); } /** * Heap up the new element,until heap property is broken. * Steps: * 1. Compare node”s value with parent”s value. * 2. Swap them, If they are in wrong order. * */ private void heapUp(int nodeIndex){ int parentIndex, tmp; if (nodeIndex != 0) { parentIndex = getParentIndex(nodeIndex); if (intArray[parentIndex] > intArray[nodeIndex]) { tmp = intArray[parentIndex]; intArray[parentIndex] = intArray[nodeIndex]; intArray[nodeIndex] = tmp; heapUp(parentIndex); } } } /** * Heap down the root element being least in value,until heap property is broken. * Steps: * 1.If current node has no children, done. * 2.If current node has one children and heap property is broken, * 3.Swap the current node and child node and heap down. * 4.If current node has one children and heap property is broken, find smaller one * 5.Swap the current node and child node and heap down. * */ private void heapDown(int nodeIndex){ int leftChildIndex, rightChildIndex, minIndex, tmp; leftChildIndex = getLeftChildIndex(nodeIndex); rightChildIndex = getRightChildIndex(nodeIndex); if (rightChildIndex >= size) { if (leftChildIndex >= size) return; else minIndex = leftChildIndex; } else { if (intArray[leftChildIndex] <= intArray[rightChildIndex]) minIndex = leftChildIndex; else minIndex = rightChildIndex; } if (intArray[nodeIndex] > intArray[minIndex]) { tmp = intArray[minIndex]; intArray[minIndex] = intArray[nodeIndex]; intArray[nodeIndex] = tmp; heapDown(minIndex); } } } Demo Program HeapDemo.java package com.tutorialspoint.datastructure; public class HeapDemo { public static void main(String[] args){ Heap heap = new Heap(10); /* 5 //Level 0 * */ heap.insert(5); /* 1 //Level 0 * | * 5—| //Level 1 */ heap.insert(1); /* 1 //Level 0 * | * 5—|—3 //Level 1 */ heap.insert(3); /* 1 //Level 0 * | * 5—|—3 //Level 1 * | * 8–| //Level 2 */ heap.insert(8); /* 1 //Level 0 * | * 5—|—3 //Level 1 * | * 8–|–9 //Level 2 */ heap.insert(9); /* 1 //Level 0 * | * 5—|—3 //Level 1 * | | * 8–|–9 6–| //Level 2 */ heap.insert(6); /* 1 //Level 0 * | * 5—|—2 //Level 1 * | | * 8–|–9 6–|–3 //Level 2 */ heap.insert(2); System.out.println(heap.getMinimum()); heap.removeMin(); /* 2 //Level 0 * | * 5—|—3 //Level 1 * | | * 8–|–9 6–| //Level 2 */ System.out.println(heap.getMinimum()); } } If we compile and run the above program then it would produce following result − 1 2 Print Page Previous Next Advertisements ”;

DSA using Java – Parsing Expressions ”; Previous Next Ordinary airthmetic expressions like 2*(3*4) are easier for human mind to parse but for an algorithm it would be pretty difficult to parse such an expression. To ease this difficulty, an airthmetic expression can be parsed by an algorithm using a two step approach. Transform the provided arithmetic expression to postfix notation. Evaluate the postfix notation. Infix Notation Normal airthmetic expression follows Infix Notation in which operator is in between the operands. For example A+B here A is first operand, B is second operand and + is the operator acting on the two operands. Postfix Notation Postfix notation varies from normal arithmetic expression or infix notation in a way that the operator follows the operands. For example, consider the following examples Sr.No Infix Notation Postfix Notation 1 A+B AB+ 2 (A+B)*C AB+C* 3 A*(B+C) ABC+* 4 A/B+C/D AB/CD/+ 5 (A+B)*(C+D) AB+CD+* 6 ((A+B)*C)-D AB+C*D- Infix to PostFix Conversion Before looking into the way to translate Infix to postfix notation, we need to consider following basics of infix expression evaluation. Evaluation of the infix expression starts from left to right. Keep precedence in mind, for example * has higher precedence over +. For example 2+3*4 = 2+12. 2+3*4 = 14. Override precedence using brackets, For example (2+3)*4 = 5*4. (2+3)*4= 20. Now let us transform a simple infix expression A+B*C into a postfix expression manually. Step Character read Infix Expressed parsed so far Postfix expression developed so far Remarks 1 A A A 2 + A+ A 3 B A+B AB 4 * A+B* AB + can not be copied as * has higher precedence. 5 C A+B*C ABC 6 A+B*C ABC* copy * as two operands are there B and C 7 A+B*C ABC*+ copy + as two operands are there BC and A Now let us transform the above infix expression A+B*C into a postfix expression using stack. Step Character read Infix Expressed parsed so far Postfix expression developed so far Stack Contents Remarks 1 A A A 2 + A+ A + push + operator in a stack. 3 B A+B AB + 4 * A+B* AB +* Precedence of operator * is higher than +. push * operator in the stack. Otherwise, + would pop up. 5 C A+B*C ABC +* 6 A+B*C ABC* + No more operand, pop the * operator. 7 A+B*C ABC*+ Pop the + operator. Now let us see another example, by transforming infix expression A*(B+C) into a postfix expression using stack. Step Character read Infix Expressed parsed so far Postfix expression developed so far Stack Contents Remarks 1 A A A 2 * A* A * push * operator in a stack. 3 ( A*( A *( push ( in the stack. 4 B A*(B AB *( 5 + A*(B+ AB *(+ push + in the stack. 6 C A*(B+C ABC *(+ 7 ) A*(B+C) ABC+ *( Pop the + operator. 8 A*(B+C) ABC+ * Pop the ( operator. 9 A*(B+C) ABC+* Pop the rest of the operator(s). Demo program Now we”ll demonstrate the use of stack to convert infix expression to postfix expression and then evaluate the postfix expression. Stack.java package com.tutorialspoint.expression; public class Stack { private int size; private int[] intArray; private int top; //Constructor public Stack(int size){ this.size = size; intArray = new int[size]; top = -1; } //push item on the top of the stack public void push(int data) { if(!isFull()){ //increment top by 1 and insert data intArray[++top] = data; }else{ System.out.println(“Cannot add data. Stack is full.”); } } //pop item from the top of the stack public int pop() { //retrieve data and decrement the top by 1 return intArray[top–]; } //view the data at top of the stack public int peek() { //retrieve data from the top return intArray[top]; } //return true if stack is full public boolean isFull(){ return (top == size-1); } //return true if stack is empty public boolean isEmpty(){ return (top == -1); } } InfixToPostFix.java package com.tutorialspoint.expression; public class InfixToPostfix { private Stack stack; private String input = “”; private String output = “”; public InfixToPostfix(String input){ this.input = input; stack = new Stack(input.length()); } public String translate(){ for(int i=0;i<input.length();i++){ char ch = input.charAt(i); switch(ch){ case ”+”: case ”-”: gotOperator(ch, 1); break; case ”*”: case ”/”: gotOperator(ch, 2); break; case ”(”: stack.push(ch); break; case ”)”: gotParenthesis(ch); break; default: output = output+ch; break; } } while(!stack.isEmpty()){ output = output + (char)stack.pop(); } return output; } //got operator from input public void gotOperator(char operator, int precedence){ while(!stack.isEmpty()){ char prevOperator = (char)stack.pop(); if(prevOperator == ”(”){ stack.push(prevOperator); break; }else{ int precedence1; if(prevOperator == ”+” || prevOperator == ”-”){ precedence1 = 1; }else{ precedence1 = 2; } if(precedence1 < precedence){ stack.push(Character.getNumericValue(prevOperator)); break; }else{ output = output + prevOperator; } } } stack.push(operator); } //got operator from input public void gotParenthesis(char parenthesis){ while(!stack.isEmpty()){ char ch = (char)stack.pop(); if(ch == ”(”){ break; }else{ output = output + ch; } } } } PostFixParser.java package com.tutorialspoint.expression; public class PostFixParser { private Stack stack; private String input; public PostFixParser(String postfixExpression){ input = postfixExpression; stack = new Stack(input.length()); } public int evaluate(){ char ch; int firstOperand; int secondOperand; int tempResult; for(int i=0;i<input.length();i++){ ch =

DSA using Java – Stack ”; Previous Next Overview Stack is kind of data structure which allows operations on data only at one end. It allows access to the last inserted data only. Stack is also called LIFO (Last In First Out) data structure and Push and Pop operations are related in such a way that only last item pushed (added to stack) can be popped (removed from the stack). Stack Representation We”re going to implement Stack using array in this article. Basic Operations Following are two primary operations of a stack which are following. Push − push an element at the top of the stack. Pop − pop an element from the top of the stack. There is few more operations supported by stack which are following. Peek − get the top element of the stack. isFull − check if stack is full. isEmpty − check if stack is empty. Push Operation Whenever an element is pushed into stack, stack stores that element at the top of the storage and increments the top index for later use. If storage is full then an error message is usually shown. // push item on the top of the stack public void push(int data) { if(!isFull()){ // increment top by 1 and insert data intArray[++top] = data; }else{ System.out.println(“Cannot add data. Stack is full.”); } } Pop Operation Whenever an element is to be popped from stack, stack retrives the element from the top of the storage and decrements the top index for later use. // pop item from the top of the stack public int pop() { // retrieve data and decrement the top by 1 return intArray[top–]; } Stack Implementation Stack.java package com.tutorialspoint.datastructure; public class Stack { private int size; // size of the stack private int[] intArray; // stack storage private int top; // top of the stack // Constructor public Stack(int size){ this.size = size; intArray = new int[size]; //initialize array top = -1; //stack is initially empty } // Operation : Push // push item on the top of the stack public void push(int data) { if(!isFull()){ // increment top by 1 and insert data intArray[++top] = data; }else{ System.out.println(“Cannot add data. Stack is full.”); } } // Operation : Pop // pop item from the top of the stack public int pop() { //retrieve data and decrement the top by 1 return intArray[top–]; } // Operation : Peek // view the data at top of the stack public int peek() { //retrieve data from the top return intArray[top]; } // Operation : isFull // return true if stack is full public boolean isFull(){ return (top == size-1); } // Operation : isEmpty // return true if stack is empty public boolean isEmpty(){ return (top == -1); } } Demo Program StackDemo.java package com.tutorialspoint.datastructure; public class StackDemo { public static void main (String[] args){ // make a new stack Stack stack = new Stack(10); // push items on to the stack stack.push(3); stack.push(5); stack.push(9); stack.push(1); stack.push(12); stack.push(15); System.out.println(“Element at top of the stack: ” + stack.peek()); System.out.println(“Elements: “); // print stack data while(!stack.isEmpty()){ int data = stack.pop(); System.out.println(data); } System.out.println(“Stack full: ” + stack.isFull()); System.out.println(“Stack empty: ” + stack.isEmpty()); } } If we compile and run the above program then it would produce following result − Element at top of the stack: 15 Elements: 15 12 1 9 5 3 Stack full: false Stack empty: true Print Page Previous Next Advertisements ”;

DSA using Java – Graph ”; Previous Next Overview Graph is a datastructure to model the mathematical graphs. It consists of a set of connected pairs called edges of vertices. We can represent a graph using an array of vertices and a two dimentional array of edges. Important terms Vertex − Each node of the graph is represented as a vertex. In example given below, labeled circle represents vertices. So A to G are vertices. We can represent them using an array as shown in image below. Here A can be identified by index 0. B can be identified using index 1 and so on. Edge − Edge represents a path between two vertices or a line between two vertices. In example given below, lines from A to B, B to C and so on represents edges. We can use a two dimentional array to represent array as shown in image below. Here AB can be represented as 1 at row 0, column 1, BC as 1 at row 1, column 2 and so on, keeping other combinations as 0. Adjacency − Two node or vertices are adjacent if they are connected to each other through an edge. In example given below, B is adjacent to A, C is adjacent to B and so on. Path − Path represents a sequence of edges betweeen two vertices. In example given below, ABCD represents a path from A to D. Basic Operations Following are basic primary operations of a Graph which are following. Add Vertex − add a vertex to a graph. Add Edge − add an edge between two vertices of a graph. Display Vertex − display a vertex of a graph. Add Vertex Operation //add vertex to the array of vertex public void addVertex(char label){ lstVertices[vertexCount++] = new Vertex(label); } Add Edge Operation //add edge to edge array public void addEdge(int start,int end){ adjMatrix[start][end] = 1; adjMatrix[end][start] = 1; } Display Edge Operation //display the vertex public void displayVertex(int vertexIndex){ System.out.print(lstVertices[vertexIndex].label+” “); } Traversal Algorithms Following are important traversal algorithms on a Graph. Depth First Search − traverses a graph in depthwards motion. Breadth First Search − traverses a graph in breadthwards motion. Depth First Search Algorithm Depth First Search algorithm(DFS) traverses a graph in a depthward motion and uses a stack to remember to get the next vertex to start a search when a dead end occurs in any iteration. As in example given above, DFS algorithm traverses from A to B to C to D first then to E, then to F and lastly to G. It employs following rules. Rule 1 − Visit adjacent unvisited vertex. Mark it visited. Display it. Push it in a stack. Rule 2 − If no adjacent vertex found, pop up a vertex from stack. (It will pop up all the vertices from the stack which do not have adjacent vertices.) Rule 3 − Repeat Rule 1 and Rule 2 until stack is empty. public void depthFirstSearch(){ //mark first node as visited lstVertices[0].visited = true; //display the vertex displayVertex(0); //push vertex index in stack stack.push(0); while(!stack.isEmpty()){ //get the unvisited vertex of vertex which is at top of the stack int unvisitedVertex = getAdjUnvisitedVertex(stack.peek()); //no adjacent vertex found if(unvisitedVertex == -1){ stack.pop(); }else{ lstVertices[unvisitedVertex].visited = true; displayVertex(unvisitedVertex); stack.push(unvisitedVertex); } } //stack is empty, search is complete, reset the visited flag for(int i=0;i<vertexCount;i++){ lstVertices[i].visited = false; } } Breadth First Search Algorithm Breadth First Search algorithm(BFS) traverses a graph in a breadthwards motion and uses a queue to remember to get the next vertex to start a search when a dead end occurs in any iteration. As in example given above, BFS algorithm traverses from A to B to E to F first then to C and G lastly to D. It employs following rules. Rule 1 − Visit adjacent unvisited vertex. Mark it visited. Display it. Insert it in a queue. Rule 2 − If no adjacent vertex found, remove the first vertex from queue. Rule 3 − Repeat Rule 1 and Rule 2 until queue is empty. public void breadthFirstSearch(){ //mark first node as visited lstVertices[0].visited = true; //display the vertex displayVertex(0); //insert vertex index in queue queue.insert(0); int unvisitedVertex; while(!queue.isEmpty()){ //get the unvisited vertex of vertex which is at front of the queue int tempVertex = queue.remove(); //no adjacent vertex found while((unvisitedVertex=getAdjUnvisitedVertex(tempVertex)) != -1){ lstVertices[unvisitedVertex].visited = true; displayVertex(unvisitedVertex); queue.insert(unvisitedVertex); } } //queue is empty, search is complete, reset the visited flag for(int i=0;i<vertexCount;i++){ lstVertices[i].visited = false; } } Graph Implementation Stack.java package com.tutorialspoint.datastructure; public class Stack { private int size; // size of the stack private int[] intArray; // stack storage private int top; // top of the stack // Constructor public Stack(int size){ this.size = size; intArray = new int[size]; //initialize array top = -1; //stack is initially empty } // Operation : Push // push item on the top of the stack public void push(int data) { if(!isFull()){ // increment top by 1 and insert data intArray[++top] = data; }else{ System.out.println(“Cannot add data. Stack is full.”); } } // Operation : Pop // pop item from the top of the stack public int pop() { //retrieve data and decrement the top by 1 return intArray[top–]; } // Operation : Peek // view the data at top of the stack public int peek() { //retrieve data from the top return intArray[top]; } // Operation : isFull // return true if stack is full

DSA using Java – Algorithms ”; Previous Next Algorithm concept Algorithm is a step by step procedure, which defines a set of instructions to be executed in certain order to get the desired output. In term of data structures, following are the categories of algorithms. Search − Algorithms to search an item in a datastrucure. Sort − Algorithms to sort items in certain order Insert − Algorithm to insert item in a datastructure Update − Algorithm to update an existing item in a data structure Delete − Algorithm to delete an existing item from a data structure Algorithm analysis Algorithm analysis deals with the execution time or running time of various operations of a data structure. Running time of an operation can be defined as no. of computer instructions executed per operation. As exact running time of any operation varies from one computer to another computer, we usually analyze the running time of any operation as some function of n, where n is the no. of items processed in that operation in a datastructure. Asymptotic analysis Asymptotic analysis refers to computing the running time of any operation in mathematical units of computation. For example, running time of one operation is computed as f(n) and of another operation as g(n2). Which means first operation running time will increase linearly with the increase in n and running time of second operation will increase exponentially when n increases. Similarly the running time of both operations will be nearly same if n is significantly small. Asymptotic Notations Following are commonly used asymptotic notations used in calculating running time complexity of an algorithm. Ο Notation Ω Notation θ Notation Big Oh Notation, Ο The Ο(n) is the formal way to express the upper bound of an algorithm”s running time. It measures the worst case time complexity or longest amount of time an algorithm can possibly take to complete. For example, for a function f(n) Ο(f(n)) = { g(n) : there exists c > 0 and n0 such that g(n) ≤ c.f(n) for all n > n0. } Big Oh notation is used to simplify functions. For example, we can replace a specific functional equation 7nlogn + n – 1 with Ο(f(nlogn)). Consider the scenario as follows: 7nlogn +n – 1 ≤ 7nlogn + n 7nlogn +n – 1 ≤ 7nlogn + nlogn for n ≥ 2 so that logn ≥ 1 7nlogn +n – 1 ≤ 8nlogn It demonstrates that f(n) = 7nlogn + n – 1 is within the range of outout of O(nlogn) using constants c = 8 and n0 = 2. Omega Notation, Ω The Ω(n) is the formal way to express the lower bound of an algorithm”s running time. It measures the best case time complexity or best amount of time an algorithm can possibly take to complete. For example, for a function f(n) Ω(f(n)) ≥ { g(n) : there exists c > 0 and n0 such that g(n) ≤ c.f(n) for all n > n0. } Theta Notation, θ The θ(n) is the formal way to express both the lower bound and upper bound of an algorithm”s running time. It is represented as following. θ(f(n)) = { g(n) if and only if g(n) = Ο(f(n)) and g(n) = Ω(f(n)) for all n > n0. } Print Page Previous Next Advertisements ”;

DSA using Java – Search techniques ”; Previous Next Search refers to locating a desired element of specified properties in a collection of items. We are going to start our discussion using following commonly used and simple search algorithms. Sr.No Technique & Description 1 Linear Search Linear search searches all items and its worst execution time is n where n is the number of items. 2 Binary Search Binary search requires items to be in sorted order but its worst execution time is constant and is much faster than linear search. 3 Interpolation Search Interpolation search requires items to be in sorted order but its worst execution time is O(n) where n is the number of items and it is much faster than linear search. Print Page Previous Next Advertisements ”;

DSA using Java – Arrays ”; Previous Next Array Basics Array is a container which can hold fix number of items and these items should be of same type. Most of the datastructure make use of array to implement their algorithms. Following are important terms to understand the concepts of Array Element − Each item stored in an array is called an element. Index − Each location of an element in an array has a numerical index which is used to identify the element. Array Representation As per above shown illustration, following are the important points to be considered. Index starts with 0. Array length is 8 which means it can store 8 elements. Each element can be accessed via its index. For example, we can fetch element at index 6 as 9. Basic Operations Following are the basic operations supported by an array. Insertion − add an element at given index. Deletion − delete an element at given index. Search − search an element using given index or by value. Update − update an element at given index. In java, when an array is initialized with size, then it assigns defaults values to its elements in following order. Data Type Default Value byte 0 short 0 int 0 long 0L float 0.0f double 0.0d char ”u0000” boolean false Object null Demo package com.tutorialspoint.array; public class ArrayDemo { public static void main(String[] args){ // Declare an array int intArray[]; // Initialize an array of 8 int // set aside memory of 8 int intArray = new int[8]; System.out.println(“Array before adding data.”); // Display elements of an array. display(intArray); // Operation : Insertion // Add elements in the array for(int i = 0; i< intArray.length; i++) { // place value of i at index i. System.out.println(“Adding “+i+” at index “+i); intArray[i] = i; } System.out.println(); System.out.println(“Array after adding data.”); display(intArray); // Operation : Insertion // Element at any location can be updated directly int index = 5; intArray[index] = 10; System.out.println(“Array after updating element at index ” + index); display(intArray); // Operation : Search using index // Search an element using index. System.out.println(“Data at index ” + index + “: “+ intArray[index]); // Operation : Search using value // Search an element using value. int value = 4; for(int i = 0; i< intArray.length; i++) { if(intArray[i] == value ){ System.out.println(value + ” Found at index “+i); break; } } System.out.println(“Data at index ” + index + “: “+ intArray[index]); } private static void display(int[] intArray){ System.out.print(“Array : [“); for(int i = 0; i< intArray.length; i++) { // display value of element at index i. System.out.print(” “+intArray[i]); } System.out.println(” ]”); System.out.println(); } } If we compile and run the above program then it would produce following result − Array before adding data. Array : [ 0 0 0 0 0 0 0 0 ] Adding 0 at index 0 Adding 1 at index 1 Adding 2 at index 2 Adding 3 at index 3 Adding 4 at index 4 Adding 5 at index 5 Adding 6 at index 6 Adding 7 at index 7 Array after adding data. Array : [ 0 1 2 3 4 5 6 7 ] Array after updating element at index 5 Array : [ 0 1 2 3 4 10 6 7 ] Data at index 5: 10 4 Found at index: 4 Print Page Previous Next Advertisements ”;

DSA using Java – Linked List ”; Previous Next Linked List Basics Linked List is a sequence of links which contains items. Each link contains a connection to another link. Linked list the second most used data structure after array. Following are important terms to understand the concepts of Linked List. Link − Each Link of a linked list can store a data called an element. Next − Each Link of a linked list contain a link to next link called Next. LinkedList − A LinkedList contains the connection link to the first Link called First. Linked List Representation As per above shown illustration, following are the important points to be considered. LinkedList contains an link element called first. Each Link carries a data field(s) and a Link Field called next. Each Link is linked with its next link using its next link. Last Link carries a Link as null to mark the end of the list. Types of Linked List Following are the various flavours of linked list. Simple Linked List − Item Navigation is forward only. Doubly Linked List − Items can be navigated forward and backward way. Circular Linked List − Last item contains link of the first element as next and and first element has link to last element as prev. Basic Operations Following are the basic operations supported by a list. Insertion − add an element at the beginning of the list. Deletion − delete an element at the beginning of the list. Display − displaying complete list. Search − search an element using given key. Delete − delete an element using given key. Insertion Operation Insertion is a three step process: Create a new Link with provided data. Point New Link to old First Link. Point First Link to this New Link. //insert link at the first location public void insertFirst(int key, int data){ //create a link Link link = new Link(key,data); //point it to old first node link.next = first; //point first to new first node first = link; } Deletion Operation Deletion is a two step process: Get the Link pointed by First Link as Temp Link. Point First Link to Temp Link”s Next Link. //delete first item public Link deleteFirst(){ //save reference to first link Link tempLink = first; //mark next to first link as first first = first.next; //return the deleted link return tempLink; } Navigation Operation Navigation is a recursive step process and is basis of many operations like search, delete etc.: Get the Link pointed by First Link as Current Link. Check if Current Link is not null and display it. Point Current Link to Next Link of Current Link and move to above step. Note //display the list public void display(){ //start from the beginning Link current = first; //navigate till the end of the list System.out.print(“[ “); while(current != null){ //print data current.display(); //move to next item current = current.next; System.out.print(” “); } System.out.print(” ]”); } Advanced Operations Following are the advanced operations specified for a list. Sort − sorting a list based on a particular order. Reverse − reversing a linked list. Concatenate − concatenate two lists. Sort Operation We”ve used bubble sort to sort a list. public void sort(){ int i, j, k, tempKey, tempData ; Link current,next; int size = length(); k = size ; for ( i = 0 ; i < size – 1 ; i++, k– ) { current = first ; next = first.next ; for ( j = 1 ; j < k ; j++ ) { if ( current.data > next.data ) { tempData = current.data ; current.data = next.data; next.data = tempData ; tempKey = current.key; current.key = next.key; next.key = tempKey; } current = current.next; next = next.next; } } } Reverse Operation Following code demonstrate reversing a single linked list. public LinkedList reverse() { LinkedList reversedlist = new LinkedList(); Link nextLink = null; reversedlist.insertFirst(first.key, first.data); Link currentLink = first; // Until no more data in list, // insert current link before first and move ahead. while(currentLink.next != null){ nextLink = currentLink.next; // Insert at start of new list. reversedlist.insertFirst(nextLink.key, nextLink.data); //advance to next node currentLink = currentLink.next; } return reversedlist; } Concatenate Operation Following code demonstrate reversing a single linked list. public void concatenate(LinkedList list){ if(first == null){ first = list.first; } if(list.first == null){ return; } Link temp = first; while(temp.next !=null) { temp = temp.next; } temp.next = list.first; } Demo Link.java package com.tutorialspoint.list; public class Link { public int key; public int data; public Link next; public Link(int key, int data){ this.key = key; this.data = data; } public void display(){ System.out.print(“{“+key+”,”+data+”}”); } } LinkedList.java package com.tutorialspoint.list; public class LinkedList { //this link always point to first Link //in the Linked List private Link first; // create an empty linked list public LinkedList(){ first = null; } //insert link at the first location public void insertFirst(int key, int data){ //create a link Link link = new Link(key,data); //point it to old first node link.next = first; //point first to new first node first = link; } //delete first item public Link deleteFirst(){ //save reference to first link Link tempLink = first; //mark next to first link as first first = first.next; //return the deleted link return tempLink; } //display the list public

Discuss DSA using Java ”; Previous Next Data Structures are the programmetic way of storing data so that data can be used efficiently. Almost every enterprise applicaton uses various types of data structures in one or other way. This tutorial will give you great understanding on Data Structures concepts needed to understand the complexity of enterprise level applications and need of algorithms, data structures. Print Page Previous Next Advertisements ”;

DSA using Java – Queue ”; Previous Next Overview Queue is kind of data structure similar to stack with primary difference that the first item inserted is the first item to be removed (FIFO – First In First Out) where stack is based on LIFO, Last In First Out principal. Queue Representation Basic Operations insert / enqueue − add an item to the rear of the queue. remove / dequeue − remove an item from the front of the queue. We”re going to implement Queue using array in this article. There is few more operations supported by queue which are following. Peek − get the element at front of the queue. isFull − check if queue is full. isEmpty − check if queue is empty. Insert / Enqueue Operation Whenever an element is inserted into queue, queue increments the rear index for later use and stores that element at the rear end of the storage. If rear end reaches to the last index and it is wrapped to the bottom location. Such an arrangement is called wrap around and such queue is circular queue. This method is also termed as enqueue operation. public void insert(int data){ if(!isFull()){ if(rear == MAX-1){ rear = -1; } intArray[++rear] = data; itemCount++; } } Remove / Dequeue Operation Whenever an element is to be removed from queue, queue get the element using front index and increments the front index. As a wrap around arrangement, if front index is more than array”s max index, it is set to 0. public int remove(){ int data = intArray[front++]; if(front == MAX){ front = 0; } itemCount–; return data; } Queue Implementation Queue.java package com.tutorialspoint.datastructure; public class Queue { private final int MAX; private int[] intArray; private int front; private int rear; private int itemCount; public Queue(int size){ MAX = size; intArray = new int[MAX]; front = 0; rear = -1; itemCount = 0; } public void insert(int data){ if(!isFull()){ if(rear == MAX-1){ rear = -1; } intArray[++rear] = data; itemCount++; } } public int remove(){ int data = intArray[front++]; if(front == MAX){ front = 0; } itemCount–; return data; } public int peek(){ return intArray[front]; } public boolean isEmpty(){ return itemCount == 0; } public boolean isFull(){ return itemCount == MAX; } public int size(){ return itemCount; } } Demo Program QueueDemo.java package com.tutorialspoint.datastructure; public class QueueDemo { public static void main(String[] args){ Queue queue = new Queue(6); //insert 5 items queue.insert(3); queue.insert(5); queue.insert(9); queue.insert(1); queue.insert(12); // front : 0 // rear : 4 // —————— // index : 0 1 2 3 4 // —————— // queue : 3 5 9 1 12 queue.insert(15); // front : 0 // rear : 5 // ——————— // index : 0 1 2 3 4 5 // ——————— // queue : 3 5 9 1 12 15 if(queue.isFull()){ System.out.println(“Queue is full!”); } //remove one item int num = queue.remove(); System.out.println(“Element removed: “+num); // front : 1 // rear : 5 // ——————- // index : 1 2 3 4 5 // ——————- // queue : 5 9 1 12 15 //insert more items queue.insert(16); // front : 1 // rear : -1 // ———————- // index : 0 1 2 3 4 5 // ———————- // queue : 16 5 9 1 12 15 //As queue is full, elements will not be inserted. queue.insert(17); queue.insert(18); // ———————- // index : 0 1 2 3 4 5 // ———————- // queue : 16 5 9 1 12 15 System.out.println(“Element at front: “+queue.peek()); System.out.println(“———————-“); System.out.println(“index : 5 4 3 2 1 0”); System.out.println(“———————-“); System.out.print(“Queue: “); while(!queue.isEmpty()){ int n = queue.remove(); System.out.print(n +” “); } } } If we compile and run the above program then it would produce following result − Queue is full! Element removed: 3 Element at front: 5 ———————- index : 5 4 3 2 1 0 ———————- Queue: 5 9 1 12 15 16 Print Page Previous Next Advertisements ”;