In this post, we will see about various data structures in java.
Data structure is a way of storing and organizing data. Data structure provide a way to process and store data efficiently.
For example:
Imagine you have pile of books on the table and you are going to read these books one by one from the top. Can you think of any data structure which can simulate with this?
Yes, you can simply use stack to store the books, so it can be accessed in Last in first out fashion.
[toc]
In this post, I am going to cover list of all important data structures in java which you can easily implement.
Array
Array is linear data structure which stores fixed number of similar elements. Array can store primitive data types as well as object but it should be of same kind. This is one of most used data structures in java.
Declare and initialize array in java
You can declare a String array as below:
String[] strArr=new String[10];
Here,
String is data type
strArr is variable name
10 is size of the array
You can also initialize array as below:
String[] strArr={"One","Two","Three"};
Advantages of array
- You can randomly access array elements using index
- It can represent multiple elements of same type with single name
- You can implement various data strucures such as LinkedList, Stack and Queue using Array
Disadvantages of array
- You need to know number of elements in advance.
- You can not modify array once its size is defined
- Insertion and deletion are quite costly operation in array as you need to shift elements.
Example
Here is an example program of an array.
package org.arpit.java2blog;
import java.util.Arrays;
public class StringArrayMain {
public static void main(String[] args) {
String[] strArr = {"One","Two","Three"};
System.out.println("Array elements are:");
// Iterate over array
for (int i=0;i
Output:
Array elements are:
One
Two
Three
====================
Printing array elements using Arrays.toString():
====================
[One, Two, Three]
Array practice programs
There are many java tricky interview programs that can be asked in interview.
You should practice these java interview programs on array.
- Find smallest and largest element in array
- Find second largest number in array
- Find missing number in an array
- Separate 0's and 1's in array
- Separate odd even numbers in java
- Sort array of 0's, 1's and 2's in java
- Find number occurring odd number of times in array
- Minimum numbers of platforms required for railway station in java
- Find pair whose sum is closest to zero in array in java
- Find pair whose sum is closest to X in array in java
- Find all pairs of elements whose sum is equal to given number
- Search element in row wise and column wise sorted matrix
- Stock buy and sell to maximize profit.
- Find local minima in array
- Find leader in array
- Find subarray with given sum
- Sliding window maximum
- Find peak element in array
- Permutations of array in java
- Subsets of set
- Rotate array by K positions
- Largest sum contiguous subarray
- search an element in a sorted and rotated arraybinary in java
- Minimum element in a sorted and ratated array in java
- Minimum jumps required to reach end of array
Stack
Stack is abstract data type which depicts Last in first out (LIFO) behavior.
Stack implementation using Array
package org.arpit.java2blog.datastructures;
/**
* @author Arpit Mandliya
*/
public class MyStack {
int size;
int arr[];
int top;
MyStack(int size) {
this.size = size;
this.arr = new int[size];
this.top = -1;
}
public void push(int element) {
if (!isFull()) {
top++;
arr[top] = element;
System.out.println("Pushed element:" + element);
} else {
System.out.println("Stack is full !");
}
}
public int pop() {
if (!isEmpty()) {
int topElement = top;
top--;
System.out.println("Popped element :" + arr[topElement]);
return arr[topElement];
} else {
System.out.println("Stack is empty !");
return -1;
}
}
public int peek() {
if(!this.isEmpty())
return arr[top];
else
{
System.out.println("Stack is Empty");
return -1;
}
}
public boolean isEmpty() {
return (top == -1);
}
public boolean isFull() {
return (size - 1 == top);
}
public static void main(String[] args) {
MyStack myStack = new MyStack(5);
myStack.pop();
System.out.println("=================");
myStack.push(100);
myStack.push(90);
myStack.push(10);
myStack.push(50);
System.out.println("=================");
myStack.pop();
myStack.pop();
myStack.pop();
System.out.println("=================");
}
}
Output:
Stack is empty !
=================
Pushed element:100
Pushed element:90
Pushed element:10
Pushed element:50
=================
Popped element :50
Popped element :10
Popped element :90
=================
Stack implementation using LinkedList
package org.arpit.java2blog.datastructures;
public class StackUsingLinkedList {
private Node head; // the first node
// nest class to define linkedlist node
private class Node {
int value;
Node next;
}
public StackUsingLinkedList() {
head = null;
}
// Remove value from the beginning of the list to simulate stack
public int pop() throws LinkedListEmptyException {
if (head == null) {
throw new LinkedListEmptyException();
}
int value = head.value;
head = head.next;
return value;
}
// Add value to the beginning of the list to simulate stack
public void push(int value) {
Node prevHead = head;
head = new Node();
head.value = value;
head.next = prevHead;
}
public static void main(String args[])
{
StackUsingLinkedList sll=new StackUsingLinkedList();
sll.push(200);
sll.push(150);
sll.push(80);
sll.push(90);
sll.push(600);
sll.push(175);
System.out.println("Removed element from LinkedList: "+sll.pop());
System.out.println("Removed element from LinkedList: "+sll.pop());
sll.push(100);
System.out.println("Removed element from LinkedList: "+sll.pop());
printList(sll.head);
}
public static void printList(Node head) {
Node temp = head;
while (temp != null) {
System.out.format("%d ", temp.value);
temp = temp.next;
}
System.out.println();
}
}
/**
*
* Throw LinkedListEmptyException if LinkedList is empty
*/
class LinkedListEmptyException extends RuntimeException {
private static final long serialVersionUID = 1L;
public LinkedListEmptyException() {
super();
}
public LinkedListEmptyException(String message) {
super(message);
}
}
Output:
Removed element from LinkedList: 175
Removed element from LinkedList: 600
Removed element from LinkedList: 100
90 80 150 200
Implementation
- Java Program to implement stack using array.
- Java Program to implement stack using Linked List
- Java Program to implement stack using two queues
Practice Programs
Sort a stack using another stack.
Queue
Queue is abstract data type which depicts First in first out (FIFO) behavior.
Queue implementation using array
package org.arpit.java2blog.datastructures;
public class MyQueue {
private int capacity;
int queueArr[];
int front;
int rear;
int currentSize = 0;
public MyQueue(int size) {
this.capacity = size;
front = 0;
rear = -1;
queueArr = new int[this.capacity];
}
/**
* Method for adding element in the queue
*
* @param data
*/
public void enqueue(int data) {
if (isFull()) {
System.out.println("Queue is full!! Can not add more elements");
} else {
rear++;
if (rear == capacity - 1) {
rear = 0;
}
queueArr[rear] = data;
currentSize++;
System.out.println(data + " added to the queue");
}
}
/**
* This method removes an element from the front of the queue
*/
public void dequeue() {
if (isEmpty()) {
System.out.println("Queue is empty!! Can not dequeue element");
} else {
front++;
if (front == capacity - 1) {
System.out.println(queueArr[front - 1] + " removed from the queue");
front = 0;
} else {
System.out.println(queueArr[front - 1] + " removed from the queue");
}
currentSize--;
}
}
/**
* Method for checking if Queue is full
*
* @return
*/
public boolean isFull() {
if (currentSize == capacity) {
return true;
}
return false;
}
/**
* Method for checking if Queue is empty
*
* @return
*/
public boolean isEmpty() {
if (currentSize == 0) {
return true;
}
return false;
}
public static void main(String a[]) {
MyQueue myQueue = new MyQueue(6);
myQueue.enqueue(1);
myQueue.dequeue();
myQueue.enqueue(30);
myQueue.enqueue(44);
myQueue.enqueue(32);
myQueue.dequeue();
myQueue.enqueue(98);
myQueue.dequeue();
myQueue.enqueue(70);
myQueue.enqueue(22);
myQueue.dequeue();
myQueue.enqueue(67);
myQueue.enqueue(23);
}
}
Output:
1 added to the queue
1 removed from the queue
30 added to the queue
44 added to the queue
32 added to the queue
30 removed from the queue
98 added to the queue
44 removed from the queue
70 added to the queue
22 added to the queue
32 removed from the queue
67 added to the queue
23 added to the queue
Queue implementation using LinkedList
package org.arpit.java2blog.datastructures;
public class QueueUsingLinkedList
{
private Node front, rear;
private int currentSize; // size
//Node data structure
private class Node
{
int data;
Node next;
}
//constructor
public QueueUsingLinkedList()
{
front = null;
rear = null;
currentSize = 0;
}
public boolean isEmpty()
{
return (currentSize == 0);
}
//Remove item from the beginning of the list to simulate Queue
public int dequeue()
{
int data = front.data;
front = front.next;
if (isEmpty())
{
rear = null;
}
currentSize--;
System.out.println(data+ " removed from the queue");
return data;
}
//Add data to the end of the list to simulate Queue
public void enqueue(int data)
{
Node oldRear = rear;
rear = new Node();
rear.data = data;
rear.next = null;
if (isEmpty())
{
front = rear;
}
else
{
oldRear.next = rear;
}
currentSize++;
System.out.println(data+ " added to the queue");
}
public static void main(String a[]){
QueueUsingLinkedList queueUsingLinkedList = new QueueUsingLinkedList();
queueUsingLinkedList.enqueue(60);
queueUsingLinkedList.dequeue();
queueUsingLinkedList.enqueue(10);
queueUsingLinkedList.enqueue(20);
queueUsingLinkedList.enqueue(40);
queueUsingLinkedList.dequeue();
queueUsingLinkedList.enqueue(70);
queueUsingLinkedList.dequeue();
queueUsingLinkedList.enqueue(80);
queueUsingLinkedList.enqueue(100);
queueUsingLinkedList.dequeue();
queueUsingLinkedList.enqueue(150);
queueUsingLinkedList.enqueue(50);
}
}
Output:
60 added to the queue
60 removed from the queue
10 added to the queue
20 added to the queue
40 added to the queue
10 removed from the queue
70 added to the queue
20 removed from the queue
80 added to the queue
100 added to the queue
40 removed from the queue
150 added to the queue
50 added to the queue
Implementation
LinkedList
Singly LinkedList
In singly linked list, Node has data and pointer to next node. It does not have pointer to the previous node. Last node ‘s next points to null, so you can iterate over linked list by using this condition.
package org.arpit.java2blog.datastructures;
class Node {
public int data;
public Node next;
public void displayNodeData() {
System.out.println("{ " + data + " } ");
}
}
public class MyLinkedList {
private Node head;
public boolean isEmpty() {
return (head == null);
}
// Method for inserting node at the start of linked list
public void insertFirst(int data) {
Node newHead = new Node();
newHead.data = data;
newHead.next = head;
head = newHead;
}
// Method for deleting node from start of linked list
public Node deleteFirst() {
Node temp = head;
head = head.next;
return temp;
}
// Method used to delete node after provided node
public void deleteAfter(Node after) {
Node temp = head;
while (temp.next != null && temp.data != after.data) {
temp = temp.next;
}
if (temp.next != null)
temp.next = temp.next.next;
}
// Method used to insert at end of LinkedList
public void insertLast(int data) {
Node current = head;
while (current.next != null) {
current = current.next; // we'll loop until current.next is null
}
Node newNode = new Node();
newNode.data = data;
current.next = newNode;
}
// Method for printing Linked List
public void printLinkedList() {
System.out.println("Printing LinkedList (head --> last) ");
Node current = head;
while (current != null) {
current.displayNodeData();
current = current.next;
}
System.out.println();
}
public static void main(String args[])
{
MyLinkedList myLinkedlist = new MyLinkedList();
myLinkedlist.insertFirst(50);
myLinkedlist.insertFirst(60);
myLinkedlist.insertFirst(70);
myLinkedlist.insertFirst(10);
myLinkedlist.insertLast(20);
myLinkedlist.printLinkedList();
// Linked list will be
// 10 -> 70 -> 60 -> 50 -> 20
System.out.println("=========================");
System.out.println("Delete node after Node 60");
Node node=new Node();
node.data=60;
myLinkedlist.deleteAfter(node);
// After deleting node after 1,Linked list will be
// 10 -> 70 -> 60 -> 20
System.out.println("=========================");
myLinkedlist.printLinkedList();
}
}
Output:
Printing LinkedList (head --> last)
{ 10 }
{ 70 }
{ 60 }
{ 50 }
{ 20 }
=========================
Delete node after Node 60
=========================
Printing LinkedList (head --> last)
{ 10 }
{ 70 }
{ 60 }
{ 20 }
Doubly LinkedList
In doubly linked list, Node has data and pointers to next node and previous node.You can iterate over linkedlist either in forward or backward direction as it has pointers to prev node and next node. This is one of most used data structures in java.
package org.arpit.java2blog.datastructures;
class Node {
public int data;
public Node next;
public Node prev;
public void displayNodeData() {
System.out.println("{ " + data + " } ");
}
}
public class MyDoublyLinkedList {
private Node head;
private Node tail;
int size;
public boolean isEmpty() {
return (head == null);
}
// Method to insert a node at the start of linked list
public void insertFirst(int data) {
Node newNode = new Node();
newNode.data = data;
newNode.next = head;
newNode.prev=null;
if(head!=null)
head.prev=newNode;
head = newNode;
if(tail==null)
tail=newNode;
size++;
}
// Method to insert a node at the start of linked list
public void insertLast(int data) {
Node newNode = new Node();
newNode.data = data;
newNode.next = null;
newNode.prev=tail;
if(tail!=null)
tail.next=newNode;
tail = newNode;
if(head==null)
head=newNode;
size++;
}
// used to delete node from start of Doubly linked list
public Node deleteFirst() {
if (size == 0)
throw new RuntimeException("Doubly linked list is already empty");
Node temp = head;
head = head.next;
head.prev = null;
size--;
return temp;
}
// Method to delete node from last of Doubly linked list
public Node deleteLast() {
Node temp = tail;
tail = tail.prev;
tail.next=null;
size--;
return temp;
}
// Method to delete node after particular node
public void deleteAfter(Node after) {
Node temp = head;
while (temp.next != null && temp.data != after.data) {
temp = temp.next;
}
if (temp.next != null)
temp.next.next.prev=temp;
temp.next = temp.next.next;
}
// Method to print Doubly Linked List forward
public void printLinkedListForward() {
System.out.println("Printing Doubly LinkedList (head --> tail) ");
Node current = head;
while (current != null) {
current.displayNodeData();
current = current.next;
}
System.out.println();
}
// Method to print Doubly Linked List forward
public void printLinkedListBackward() {
System.out.println("Printing Doubly LinkedList (tail --> head) ");
Node current = tail;
while (current != null) {
current.displayNodeData();
current = current.prev;
}
System.out.println();
}
public static void main(String args[])
{
MyDoublyLinkedList mdll = new MyDoublyLinkedList();
mdll.insertFirst(50);
mdll.insertFirst(60);
mdll.insertFirst(70);
mdll.insertFirst(10);
mdll.insertLast(20);
mdll.printLinkedListForward();
mdll.printLinkedListBackward();
System.out.println("================");
// Doubly Linked list will be
// 10 -> 70 -> 60 -> 50 -> 20
Node node=new Node();
node.data=10;
mdll.deleteAfter(node);
mdll.printLinkedListForward();
mdll.printLinkedListBackward();
// After deleting node after 1,doubly Linked list will be
// 20 -> 10 -> 60-> 50
System.out.println("================");
mdll.deleteFirst();
mdll.deleteLast();
// After performing above operation, doubly Linked list will be
// 60 -> 50
mdll.printLinkedListForward();
mdll.printLinkedListBackward();
}
}
Output:
Printing Doubly LinkedList (head --> tail)
{ 10 }
{ 70 }
{ 60 }
{ 50 }
{ 20 }
Printing Doubly LinkedList (tail --> head)
{ 20 }
{ 50 }
{ 60 }
{ 70 }
{ 10 }
================
Printing Doubly LinkedList (head --> tail)
{ 10 }
{ 60 }
{ 50 }
{ 20 }
Printing Doubly LinkedList (tail --> head)
{ 20 }
{ 50 }
{ 60 }
{ 10 }
================
Printing Doubly LinkedList (head --> tail)
{ 60 }
{ 50 }
Printing Doubly LinkedList (tail --> head)
{ 50 }
{ 60 }
Implementation
LinkedList Practice Programs
- How to reverse a linked list in java
- How to reverse a linked list in pairs
- How to find middle element of linked list in java
- How to detect a loop in linked list in java
- Find start node of loop in linkedlist
- How to find nth element from end of linked list
- How to check if linked list is palindrome in java
- Add two numbers represented by linked list in java
- Find intersection of two Linked Lists
Binary tree
A binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child
Example of binary tree:
package org.arpit.java2blog.datastructures;
import java.util.Stack;
public class BinaryTree {
public static class Node
{
int data;
Node left;
Node right;
Node(int data)
{
this.data=data;
}
}
// Recursive Solution
public void preorder(Node root) {
if(root != null) {
//Pre order traversal
System.out.printf("%d ",root.data);
preorder(root.left);
preorder(root.right);
}
}
// Iterative solution
public void preorderIter(Node root) {
if(root == null)
return;
Stack s = new Stack();
s.push(root);
while(!s.empty()){
Node n = s.pop();
System.out.printf("%s ",n.data);
if(n.right != null){
s.push(n.right);
}
if(n.left != null){
s.push(n.left);
}
}
}
public static void main(String[] args)
{
BinaryTree bi=new BinaryTree();
// Creating a binary tree
Node rootNode=createBinaryTree();
System.out.println("Using Recursive solution:");
bi.preorder(rootNode);
System.out.println();
System.out.println("-------------------------");
System.out.println("Using Iterative solution:");
bi.preorderIter(rootNode);
}
public static Node createBinaryTree()
{
Node rootNode =new Node(30);
Node node20=new Node(50);
Node node10=new Node(60);
Node node30=new Node(80);
Node node60=new Node(90);
Node node50=new Node(100);
Node node70=new Node(110);
rootNode.left=node20;
rootNode.right=node60;
node20.left=node10;
node20.right=node30;
node60.left=node50;
node60.right=node70;
return rootNode;
}
}
Output:
Using Recursive solution:
30 50 60 80 90 100 110
-------------------------
Using Iterative solution:
30 50 60 80 90 100 110
Implementation
Binary tree practice programs
- Binary tree in java
- Binary tree preorder traversal
- Binary tree postorder traversal
- Binary tree inorder traversal
- Binary tree level order traversal
- Binary tree spiral order traversal
- Binary tree reverse level order traversal
- Binary tree boundary traversal
- Print leaf nodes of binary tree
- Count leaf nodes in binary tree
- get maximum element in binary tree
- Print all paths from root to leaf in binary tree
- Print vertical sum of binary tree in java
- Get level of node in binary tree in java
- Lowest common ancestor(LCA) in binary tree in java
Binary Search tree
Binary search tree is a special type of binary tree which have following properties.
- Nodes which are smaller than root will be in left subtree.
- Nodes which are greater than root will be right subtree.
- It should not have duplicate nodes
- Both left and right subtree also should be binary search tree.
package org.arpit.java2blog.datastructures;
public class MyBinarySearchTree {
public static class Node
{
int data;
Node left;
Node right;
Node(int data)
{
this.data=data;
}
}
public static boolean search(Node root, Node nodeToBeSearched)
{
if(root==null)
return false;
if(root.data== nodeToBeSearched.data)
{
return true;
}
boolean result=false;
if(root.data > nodeToBeSearched.data)
result=search(root.left,nodeToBeSearched);
else if(root.data < nodeToBeSearched.data)
result= search(root.right,nodeToBeSearched);
return result;
}
public static Node insert(Node root, Node nodeToBeInserted)
{ if(root==null) {
root=nodeToBeInserted; return root;
} if(root.data > nodeToBeInserted.data)
{
if(root.left==null)
root.left=nodeToBeInserted;
else
insert(root.left,nodeToBeInserted);
}
else if(root.data < nodeToBeInserted.data)
if(root.right==null)
root.right=nodeToBeInserted;
else
insert(root.right,nodeToBeInserted);
return root;
}
public static void inOrder(Node root)
{
if(root==null)
return;
inOrder(root.left);
System.out.print(root.data+" ");
inOrder(root.right);
}
public static void main(String[] args)
{
// Create binary search tree
Node rootNode=createBinarySearchTree();
Node node55=new Node(55);
boolean result=search(rootNode,node55);
System.out.println("Searching for node 55 : "+result);
System.out.println("---------------------------");
Node node13=new Node(13);
Node root=insert(rootNode,node13);
System.out.println("Inorder traversal of binary tree after adding 13:");
inOrder(root);
}
public static Node createBinarySearchTree()
{
Node rNode =new Node(40);
Node node20=new Node(20);
Node node10=new Node(10);
Node node30=new Node(30);
Node node60=new Node(60);
Node node50=new Node(50);
Node node70=new Node(70);
Node node5=new Node(5);
Node node55=new Node(55);
insert(null,rNode);
insert(rNode,node20);
insert(rNode,node10);
insert(rNode,node30);
insert(rNode,node60);
insert(rNode,node50);
insert(rNode,node70);
insert(rNode,node5);
insert(rNode,node55);
return rNode;
}
}
Output:
Searching for node 55 : true
---------------------------
Inorder traversal of binary tree after adding 13:
5 10 13 20 30 40 50 55 60 70
Implementation
Binary search tree Practice programs
- Binary search tree in java
- Delete node from binary search tree
- Minimum and maximum elements in binary search tree
- LCA of binary search tree
- inorder successor in binary search tre
- Conver sorted array to balanced BST
- Convert sorted Linked List to balanced BST
- Convert sorted Linked List to balanced BST
- Check if a binary tree is binary search tree or not in java
Trie
Trie is data structure which is used to store in such a way that data can be retrieved faster.
Some real time examples:
Trie can be used to implement Dictionary.
We can put words in Trie and its children linkedlist will have its child nodes.
Let's say you want to insert do, deal , dear , he , hen , heat etc.
Here is the trie representation of the data:
package org.arpit.java2blog.datastructures;
/*
* Java Program to Implement Trie
*/
import java.util.*;
class TrieNode
{
char data;
boolean isEnd;
int count;
LinkedList childList;
/* Constructor */
public TrieNode(char c)
{
childList = new LinkedList();
isEnd = false;
data = c;
count = 0;
}
public TrieNode getChild(char c)
{
if (childList != null)
for (TrieNode eachChild : childList)
if (eachChild.data == c)
return eachChild;
return null;
}
}
public class Trie
{
private TrieNode root;
/* Constructor */
public Trie()
{
root = new TrieNode(' ');
}
/* Method for inserting words from trie*/
public void insert(String word)
{
if (search(word) == true)
return;
TrieNode tempCurr = root;
for (char ch : word.toCharArray() )
{
TrieNode child = tempCurr.getChild(ch);
if (child != null)
tempCurr = child;
else
{
// If child not present, adding it io the list
tempCurr.childList.add(new TrieNode(ch));
tempCurr = tempCurr.getChild(ch);
}
tempCurr.count++;
}
tempCurr.isEnd = true;
}
/* Method for searching words in Trie*/
public boolean search(String word)
{
TrieNode tempCurr = root;
for (char ch : word.toCharArray() )
{
if (tempCurr.getChild(ch) == null)
return false;
else
tempCurr = tempCurr.getChild(ch);
}
if (tempCurr.isEnd == true)
return true;
return false;
}
/* Method for removing words from trie*/
public void remove(String word)
{
if (search(word) == false)
{
System.out.println(word +" does not present in trien");
return;
}
TrieNode tempCurr = root;
for (char ch : word.toCharArray())
{
TrieNode child = tempCurr.getChild(ch);
if (child.count == 1)
{
tempCurr.childList.remove(child);
return;
}
else
{
child.count--;
tempCurr = child;
}
}
tempCurr.isEnd = false;
}
public static void displayWordsInTrie(TrieNode root, String str)
{
TrieNode tempCurr = root;
if(root.childList==null || root.childList.size()==0)
return;
Iterator iter=tempCurr.childList.iterator();
while(iter.hasNext())
{
TrieNode trieNode= (TrieNode) iter.next();
str+=trieNode.data;
displayWordsInTrie(trieNode,str);
if(trieNode.isEnd==true)
{
System.out.print(" "+str);
str=str.substring(0,str.length()-1);
}
else
{
str=str.substring(0,str.length()-1);
}
}
}
public static void main(String[] args)
{
Trie t = new Trie();
t.insert("apple");
t.insert("ape");
t.insert("goat");
t.insert("goa");
t.insert("apt");
System.out.println("go present in trie : "+t.search("go"));
System.out.println("goa present in trie : "+t.search("goa"));
System.out.println("appl present in trie : "+t.search("ape"));
System.out.println("========================");
System.out.println("Displaying all word present in trie : ");
displayWordsInTrie(t.root,"");
}
}
Output:
go present in trie : false
goa present in trie : true
appl present in trie : true
========================
Displaying all word present in trie :
apple ape apt goat goa
Implementation
Heap
A min heap is complete binary tree based data structure in which value of root node is less than or equal to value of child nodes.
Implementation
package org.arpit.java2blog.datastructures;
import java.util.Arrays;
public class MinHeap
{
int Heap[];
int size;
int capacity;
public MinHeap(int size)
{
this.capacity = size;
this.size = 0;
Heap = new int[size];
}
int parent(int i)
{
return (i - 1)/2; //returns the parent node index for ith node
}
int leftChild(int i)
{
return (2 * i) + 1; //returns the left child index.
}
int rightChild(int i)
{
return (2 * i) + 2; //return the right child index.
}
boolean isLeaf(int i) //checks if ith node is leaf node or not.
{
if (rightChild(i) >= size || leftChild(i) >= size)
return true;
return false;
}
/* Method to insert node in MinHeap
*/
void insert(int data)
{
if (size >= capacity)
return;
Heap[size] = data;
int tempCurr = size;
while (Heap[tempCurr] < Heap[parent(tempCurr)])
{
swap(tempCurr, parent(tempCurr));
tempCurr = parent(tempCurr);
}
size++;
}
//removes and returns the minimum element or the root from the heap
int extractMinimum()
{
int min = Heap[0];
Heap[0] = Heap[--size];
minHeapify(0);
System.out.print("\nThe Min Heap after Removing node is :");
for(int i=0;i Heap[leftChild(i)] || Heap[i] > Heap[rightChild(i)])
{
if(Heap[leftChild(i)] < Heap[rightChild(i)])
{
swap(i, leftChild(i));
minHeapify(leftChild(i));
}
else
{
swap(i, rightChild(i));
minHeapify(rightChild(i));
}
}
}
}
// builds the min-heap using the minHeapify
public void minHeap()
{
// we call until size/2 cause parent nodes present till that index.
for (int i = (size-1)/2; i >= 0; i--)
{
minHeapify(i);
}
}
//Prints the contents of heap
public void printHeap()
{
for (int i = 0; i < (size / 2); i++)
{
if(i==0)
System.out.print("Root : "+ Heap[i]);
else
System.out.print("Parent : " + Heap[i]);
if (leftChild(i) < size)
System.out.print(" Left : " + Heap[leftChild(i)]);
if (rightChild(i) < size)
System.out.print(" Right : " + Heap[rightChild(i)]);
System.out.println();
}
}
// swaps two nodes of the heap
void swap(int x, int y)
{
int temp;
temp = Heap[x];
Heap[x] = Heap[y];
Heap[y] = temp;
}
//Driver Code to test above methods.
public static void main(String[] args)
{
// Creating a Min heap of capacity 6.
MinHeap heap = new MinHeap(6);
heap.insert(100);
heap.insert(200);
heap.insert(500);
heap.insert(700);
heap.insert(800);
heap.insert(900);
// then build the Min Heap
heap.minHeap();
System.out.println("The Min Heap is : "+ Arrays.toString(heap.Heap));
// Get Minimum Operation
System.out.println("\nThe Min Value in the heap : " + heap.getMinimum());
System.out.println();
heap.printHeap();
// Extract Minimum Operation
System.out.println("Extracted Minimum Node in the heap : " + heap.extractMinimum());
System.out.println();
// Finally print heap to check deleted item.
heap.printHeap();
}
}
Output:
The Min Heap is : [100, 200, 500, 700, 800, 900]
The Min Value in the heap : 100
Root : 100 Left : 200 Right : 500
Parent : 200 Left : 700 Right : 800
Parent : 500 Left : 900
The Min Heap after Removing node is :200 700 500 900 800
Extracted Minimum Node in the heap : 100
Root : 200 Left : 700 Right : 500
Parent : 700 Left : 900 Right : 800
Graph
- Graph is a data structure for storing connected data
- It contains group of vertices and edges
- Graph can be of two types: Directed and undirected
- It contains group of vertices and edges
- Graph can be disjoint or connected and there are various algorithms such as depth first search to find this out.
Implementation
package org.arpit.java2blog.datastructures;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
public class GraphMain
{
static class Node
{
int data;
boolean visited;
List neighbours;
Node(int data)
{
this.data=data;
this.neighbours=new ArrayList<>();
}
public void addneighbours(Node neighbourNode)
{
this.neighbours.add(neighbourNode);
}
public List getNeighbours() {
return neighbours;
}
public void setNeighbours(List neighbours) {
this.neighbours = neighbours;
}
}
// Recursive DFS
public void recursiveDFS(Node node)
{
System.out.print(node.data + " ");
List neighbours=node.getNeighbours();
node.visited=true;
for (int i = 0; i < neighbours.size(); i++) {
Node n=neighbours.get(i);
if(n!=null && !n.visited)
{
recursiveDFS(n);
}
}
}
// Iterative DFS using stack
public void iterativeDFS(Node node)
{
Stack stack=new Stack();
stack.add(node);
while (!stack.isEmpty())
{
Node element=stack.pop();
if(!element.visited)
{
System.out.print(element.data + " ");
element.visited=true;
}
List neighbours=element.getNeighbours();
for (int i = 0; i < neighbours.size(); i++) {
Node n=neighbours.get(i);
if(n!=null && !n.visited)
{
stack.add(n);
}
}
}
}
public static void main(String arg[])
{
Node node40 =new Node(40);
Node node10 =new Node(10);
Node node20 =new Node(20);
Node node30 =new Node(30);
Node node60 =new Node(60);
Node node50 =new Node(50);
Node node70 =new Node(70);
node40.addneighbours(node10);
node40.addneighbours(node20);
node10.addneighbours(node30);
node20.addneighbours(node10);
node20.addneighbours(node30);
node20.addneighbours(node60);
node20.addneighbours(node50);
node30.addneighbours(node60);
node60.addneighbours(node70);
node50.addneighbours(node70);
GraphMain gm = new GraphMain();
System.out.println("Iterative DFS traversal ");
gm.iterativeDFS(node40);
System.out.println();
// Resetting the visited flag for nodes
node40.visited=false;
node10.visited=false;
node20.visited=false;
node30.visited=false;
node60.visited=false;
node50.visited=false;
node70.visited=false;
System.out.println("Recursive DFS traversal ");
gm.recursiveDFS(node40);
}
}
Output:
Iterative DFS traversal
40 20 50 70 60 30 10
Recursive DFS traversal
40 10 30 60 70 20 50
Inbuild data structures in java
There are lot of good data structures provided by Java language.
Here are few important ones:
String
String is most used data structure in java. There are lot of java interview programs on String which can be asked in interview.
- How to reverse String in java
- How to check if two Strings are angrams
- Find length of String without using java inbuilt length method
- Find all substrings of String in java
- Find First non repeated character in a String
- Java Program to check Palindrome String
- Why String is immutable in java
- Find duplicate characters in String
- Longest common prefix in array of Strings
HashMap
- HashMap is used to store key value pairs
- HashMap is neither synchronized nor thread safe.
- HashMap does not allow duplicate keys
- HashMap is unordered collection and does not give guarantee for specific order
package org.arpit.java2blog;
import java.util.HashMap;
public class HashMapMain {
public static void main(String[] args) {
HashMap map = new HashMap();
// Putting key-values pairs in HashMap
map.put(1, "One");
map.put(2, "Two");
map.put(3, "Three");
map.put(4, "Four");
System.out.println(map);
}
}
Output:
{1=One, 3=Three, 2=Two, 4=Four}
LinkedHashMap
- LinkedHashMap implements Map interface and extends HashMap class
- LinkedHashMap maintains insertion order for key value pair
- LinkedHashMap does not allow duplicate keys
- LinkedHashMap uses double linked list to maintain insertion order
package org.arpit.java2blog;
import java.util.HashMap;
public class LinkedHashMapMain {
public static void main(String[] args) {
Map map = new LinkedHashMap();
// Putting key-values pairs in HashMap
map.put(1, "One");
map.put(2, "Two");
map.put(3, "Three");
map.put(4, "Four");
System.out.println(map);
}
}
Output:
{1=One, 2=Two, 3=Three, 4=Four}
ArrayList
- ArrayList is resizable array which can dynamically grow
- It uses array as internal data structure and increses its size by half when its size is increased
- ArrayList is not synchronized
- ArrayList implements List interface
package org.arpit.java2blog.datastructures;
import java.util.ArrayList;
public class ArrayListMain {
/*
* @author : Arpit Mandliya
*/
public static void main(String[] args) {
ArrayList list = new ArrayList<>();
list.add("One");
list.add("Two");
list.add("Three");
list.add("Four");
System.out.println("ArrayList:");
for (String str : list) {
System.out.println(str);
}
}
}
Output:
ArrayList:
One
Two
Three
Four
LinkedList
- Java LinkedList class used doubly linked list to store the elements
- LinkedList maintains insertion order
- It is not synchronized
- Manipulation is quite fast in LinkedList as no shifting is required
- LinkedList can be Stack, Queue or LinkedList
import java.util.LinkedList;
import java.util.Iterator;
public class LinkedListMain {
/*
* @author : Arpit Mandliya
*/
public static void main(String[] args) {
LinkedList list = new LinkedList<>();
list.add("One");
list.add("Two");
list.add("Three");
list.add("Four");
System.out.println("LinkedList:");
Iterator it=list.iterator();
while(it.hasNext()){
System.out.println(it.next());
}
}
}
Output:
LinkedList:
One
Two
Three
Four
HashSet
- https://java2blog.com/how-hashset-works-in-java/ implements Set interface and it does not allow duplicate elements
- HashSet does not maintain insertion order
- It is not synchronized and not thread safe
package org.arpit.java2blog.datastructures;
import java.util.HashSet;
import java.util.Iterator;
public class HashSetMain {
/*
* @author : Arpit Mandliya
*/
public static void main(String[] args) {
HashSet set = new HashSet<>();
set.add("One");
set.add("Two");
set.add("One");
set.add("Three");
set.add("Two");
System.out.println("HashSet:");
Iterator it=set.iterator();
while(it.hasNext()){
System.out.println(it.next());
}
}
}
Output:
HashSet:
One
Two
Three
As you can see, duplicate Strings are removed from the HashSet.
That's all about Data structures in Java.
