Data Structures in Java

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.

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];

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"};

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<strArr.length;i++)
        {
            System.out.println(strArr[i]);
        }
        System.out.println("====================");
        System.out.println("Printing array elements using Arrays.toString():");
        System.out.println("====================");
        // You can also use Arrays.toString() to print an array
        System.out.println(Arrays.toString(strArr));
    }
}

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<strArr.length;i++)

{

System.out.println(strArr[i]);

}

System.out.println("====================");

System.out.println("Printing array elements using Arrays.toString():");

System.out.println("====================");

// You can also use Arrays.toString() to print an array

System.out.println(Arrays.toString(strArr));

}

Output:

Array elements are:
One
Two
Three
====================
Printing array elements using Arrays.toString():
====================
[One, Two, Three]

There are many java tricky interview programs that can be asked in interview.

You should practice these java interview programs on 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("=================");
    }
}

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();

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);
    }
}

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());

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

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);
    }
}

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);
    }
}

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();
    }
}

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();
    }
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

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

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<Node> s = new Stack<Node>();
        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;
    }
}

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<Node> s = new Stack<Node>();

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 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;
    }

}

100

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 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<TrieNode> 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,"");
    }
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

package org.arpit.java2blog.datastructures;

* Java Program to Implement Trie

import java.util.*;

class TrieNode

{

char data;

boolean isEnd;

int count;

LinkedList<TrieNode> 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

Trie data structure in java

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<size;i++)
            System.out.print(Heap[i]+" ");

        System.out.println();
        return min;
    }

    //just returns the minimum value or root.
    int getMinimum()
    {
        int min=Heap[0];
        return min;
    }

    // heapify the ith node
    void minHeapify(int i)
    {

        // If node is a non-leaf node and any of its child is smaller
        if(!isLeaf(i))
        {
            if(Heap[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();

    }
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

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<size;i++)

System.out.print(Heap[i]+" ");

System.out.println();

return min;

}

//just returns the minimum value or root.

int getMinimum()

{

int min=Heap[0];

return min;

}

// heapify the ith node

void minHeapify(int i)

{

// If node is a non-leaf node and any of its child is smaller

if(!isLeaf(i))

{

if(Heap[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<Node> neighbours;

        Node(int data)
        {
            this.data=data;
            this.neighbours=new ArrayList<>();

        }
        public void addneighbours(Node neighbourNode)
        {
            this.neighbours.add(neighbourNode);
        }
        public List<Node> getNeighbours() {
            return neighbours;
        }
        public void setNeighbours(List<Node> neighbours) {
            this.neighbours = neighbours;
        }
    }

    // Recursive DFS
    public  void recursiveDFS(Node node)
    {
        System.out.print(node.data + " ");
        List<Node> 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<Node> stack=new  Stack<Node>();
        stack.add(node);
        while (!stack.isEmpty())
        {
            Node element=stack.pop();
            if(!element.visited)
            {
                System.out.print(element.data + " ");
                element.visited=true;
            }

            List<Node> 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);
    }
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

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<Node> neighbours;

Node(int data)

{

this.data=data;

this.neighbours=new ArrayList<>();

}

public void addneighbours(Node neighbourNode)

{

this.neighbours.add(neighbourNode);

}

public List<Node> getNeighbours() {

return neighbours;

}

public void setNeighbours(List<Node> neighbours) {

this.neighbours = neighbours;

}

// Recursive DFS

public void recursiveDFS(Node node)

{

System.out.print(node.data + " ");

List<Node> 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<Node> stack=new Stack<Node>();

stack.add(node);

while (!stack.isEmpty())

{

Node element=stack.pop();

if(!element.visited)

{

System.out.print(element.data + " ");

element.visited=true;

}

List<Node> 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 is most used data structure in java. There are lot of java interview programs on String which can be asked in interview.

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<Integer, String> map = new HashMap<Integer, String>();
        // 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);
    }
}

package org.arpit.java2blog;

import java.util.HashMap;

public class HashMapMain {

public static void main(String[] args) {

HashMap<Integer, String> map = new HashMap<Integer, String>();

// 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<Integer, String> map = new LinkedHashMap<Integer, String>();
        // 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);
    }
}

package org.arpit.java2blog;

import java.util.HashMap;

public class LinkedHashMapMain {

public static void main(String[] args) {

Map<Integer, String> map = new LinkedHashMap<Integer, String>();

// 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<String> 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);
        }
    }
}

package org.arpit.java2blog.datastructures;

import java.util.ArrayList;

public class ArrayListMain {

* @author : Arpit Mandliya

public static void main(String[] args) {

ArrayList<String> 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<String> list = new LinkedList<>();
        list.add("One");
        list.add("Two");
        list.add("Three");
        list.add("Four");

        System.out.println("LinkedList:");

        Iterator<String> it=list.iterator();  
        while(it.hasNext()){  
            System.out.println(it.next());  
        }  
    }
}

import java.util.LinkedList;

import java.util.Iterator;

public class LinkedListMain {

* @author : Arpit Mandliya

public static void main(String[] args) {

LinkedList<String> list = new LinkedList<>();

list.add("One");

list.add("Two");

list.add("Three");

list.add("Four");

System.out.println("LinkedList:");

Iterator<String> 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<String> set = new HashSet<>();
        set.add("One");
        set.add("Two");
        set.add("One");
        set.add("Three");
        set.add("Two");

        System.out.println("HashSet:");

        Iterator<String> it=set.iterator();
        while(it.hasNext()){
            System.out.println(it.next());
        }
    }
}

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<String> set = new HashSet<>();

set.add("One");

set.add("Two");

set.add("One");

set.add("Three");

set.add("Two");

System.out.println("HashSet:");

Iterator<String> 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.

Was this post helpful?

Let us know if this post was helpful. Feedbacks are monitored on daily basis. Please do provide feedback as that\'s the only way to improve.

Array

Declare and initialize array in java

Advantages of array

Disadvantages of array

Example

Array practice programs

Stack

Stack implementation using Array

Stack implementation using LinkedList

Implementation

Practice Programs

Queue

Queue implementation using array

Queue implementation using LinkedList

Implementation

LinkedList

Implementation

LinkedList Practice Programs

Binary tree

Implementation

Binary tree practice programs

Binary Search tree

Implementation

Binary search tree Practice programs

Trie

Implementation

Heap

Implementation

Graph

Implementation

Inbuild data structures in java

String

HashMap

LinkedHashMap

ArrayList

LinkedList

HashSet

Was this post helpful?

Related posts:

Share this

Author

Leave a Reply Cancel reply

Let’s be Friends