Data Structures in java

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.

Array

Declare and initialize array in java

You can declare a String array as below:

Here,
String is data type
strArr is variable name
10 is size of the array

You can also initialize array as below:

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.

Output:

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

Stack

Stack is abstract data type which depicts Last in first out (LIFO) behavior.

Stack in java

Stack implementation using Array

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

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 in java

Queue implementation using array

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

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.

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.

Doubly Linked List in java

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:

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.

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:

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.

HashMap in java

Implementation

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

  1. Graph is a data structure for storing connected data
  2. It contains group of vertices and edges
  3. Graph can be of two types: Directed and undirected
  4. It contains group of vertices and edges
  5. Graph can be disjoint or connected and there are various algorithms such as depth first search to find this out.

HashMap in java

Implementation

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:

HashMap

  1. HashMap is used to store key value pairs
  2. HashMap is neither synchronized nor thread safe.
  3. HashMap does not allow duplicate keys
  4. HashMap is unordered collection and does not give guarantee for specific order

HashMap in java

Output:

{1=One, 3=Three, 2=Two, 4=Four}

LinkedHashMap

  1. LinkedHashMap implements Map interface and extends HashMap class
  2. LinkedHashMap maintains insertion order for key value pair
  3. LinkedHashMap does not allow duplicate keys
  4. LinkedHashMap uses double linked list to maintain insertion order

HashMap in java

Output:

{1=One, 2=Two, 3=Three, 4=Four}

ArrayList

  1. ArrayList is resizable array which can dynamically grow
  2. It uses array as internal data structure and increses its size by half when its size is increased
  3. ArrayList is not synchronized
  4. ArrayList implements List interface

HashMap in java

Output:

ArrayList:
One
Two
Three
Four

LinkedList

  1. Java LinkedList class used doubly linked list to store the elements
  2. LinkedList maintains insertion order
  3. It is not synchronized
  4. Manipulation is quite fast in LinkedList as no shifting is required
  5. LinkedList can be Stack, Queue or LinkedList

Output:

LinkedList:
One
Two
Three
Four

HashSet

  1. https://java2blog.com/how-hashset-works-in-java/ implements Set interface and it does not allow duplicate elements
  2. HashSet does not maintain insertion order
  3. It is not synchronized and not thread safe

Output:

HashSet:
One
Two
Three

As you can see, duplicate Strings are removed from the HashSet.
That’s all about Data structures in Java.

Related Posts

  • Rotate matrix by 90 degrees in java
    20 May

    Rotate Matrix by 90 degrees in java

    Table of ContentsClockwise or Right Rotate a MatrixAnti-Clockwise or Left Rotate a MatrixHow to Rotate Matrix K Times? In this article, we will look into another interesting problem related to 2D Arrays. Given a Matrix of N X N Dimension we have to Rotate matrix by 90 degrees. We will perform Rotation both Clockwise i.e. […]

  • 29 November

    Top 100+ Java coding interview questions

    Table of ContentsStringQuestion 1 : How to reverse a String in java? Can you write a program without using any java inbuilt methods?Question 2 : Write a java program to check if two Strings are anagram in java?Question 3 : Write a program to check if String has all unique characters in java?Question 4 : […]

  • 18 April

    Minimum Number of Jumps to reach last Index

    Table of ContentsProblemSolution If you want to practice data structure and algorithm programs, you can go through Java coding interview questions. In this post, we will see how to find Minimum Number of Jumps to reach last Index. Problem Given an array A of positive integers possibly zeroes, every index indicating the maximum length of a […]

  • 20 February

    Inorder Successor in a Binary Search Tree

    Table of ContentsProblemSolutionAPPROACH – I :Approach – II:(i) If the target node has a right child :(ii) If the target node does not have a right child :Time Complexity Discussion If you want to practice data structure and algorithm programs, you can go through Java coding interview questions. In this post, we will see how to […]

  • 04 February

    LCA of a K-ary Tree in O(Sqrt(height))

    Table of ContentsProblemSolution If you want to practice data structure and algorithm programs, you can go through Java coding interview questions. In this post, we will see about how to find Lowest Common Ancestor of a K-ary Tree in O(Sqrt(height)).We have already seen how to find LCA of n-ary tree in O(n) complexity. Problem Given a […]

  • 03 February

    Largest Rectangular Area in a Histogram

    Table of ContentsProblemSolutionAPPROACH – IAPPROACH – II (RECURSIVE):Approach – III (ITERATIVE) : If you want to practice data structure and algorithm programs, you can go through Java coding interview questions. In this post, we will see about how to find largest rectangular area in a Histogram. Problem Given an Integer representing number of bars in a […]

Leave a Reply

Your email address will not be published. Required fields are marked *

Subscribe to our newletter

Get quality tutorials to your inbox. Subscribe now.