# Data Structures in Java

February 3, 2022A data structure is a way of storing and organizing data in the memory. It provides a way to store and process data effectively. The main purpose is to reduce the space and better time management to perform various tasks. And thus efficient data structures help us to design better algorithms.

Now, take an example of data structures in java to get a clear picture of it:

Let us assume you have a heap of books and you are going to read each of these books one by one from top to bottom or bottom to top. Yes, you are thinking right! Here the role of data structure comes into action. You can easily use the stack to store the books. We all are going to discuss all types of data structures below.

So, here’s the list of **data structures in java**:

- Array
- Stack
- Queue
- Linked List
- Binary Tree
- Binary Search Tree
- Heap
- Hashing
- Graph

**Array **

An array is a collection of data structures stored at contiguous memory locations. As an array is homogeneous, thus it can store only the same kind of primitive data types as well as objects.

The size of an array should be provided before indexing the data. We mostly use arrays in Java.

**Declaration of array in Java **

String[] strArr = new String[5] |

**Initialization of array in Java **

String[] strArr = { “one, two”}; |

**Advantages of array **

- It can represent multiple elements of the same type with a single name.
- We can randomly access array elements easily using the index number.
- We can implement data structures like Linked Lists, Stacks, Queues, Trees, graphs, and many more using arrays.

**Disadvantages of Array **

- The number of elements to be stored is known in advance.
- Insertion and deletion are quite difficult in array as the shifting operation is costly.
- An array is a static structure which means size can’t be modified once it is defined.

**Applications of Array **

- It stores data elements of the same type.
- Arrays can be used to perform matrix operations and also it is used for CPU scheduling.
- Arrays help to maintain large data under a single variable name.

Example:-

We often use arrays all the time in programming. On every occasion you have to maintain track of an ordered listing of items, you will end up the usage of an array. Be it a listing of songs, a list of books, or listing of anything for

that count number. Even in the JSON information format, you may regularly use an array to keep a list of gadgets. Databases generally provide an exclusive capability, as in they let you maintain records through the years. We can retrieve that statistics and replace it and examine it from different computers using other net browsers. We’ll often retrieve facts from a database and store it for neighborhood processing in an array. So arrays are a critical concept in programming languages.

**Stack **

It is an abstract data structure that is inserted and removed according to the LIFO principle. Also, this is a statistics shape that implements the LIFO (closing In First Out) paradigm.It contains only one pointer top pointer pointing to the topmost element of the stack. Whenever an element is added in the stack, it is added on the top of the stack, and the element can be deleted only from the stack. It can be carried out each through arrays and linked listings. Push and pop are the two predominant operations at the stack. It is largely utilized in recursion.

**Advantages of Stack **

- It allows you to manage the data in LIFO method which is usually not possible with Linked Lists and arrays.
- It allows you to control memory allocation and deallocation.
- It cleans the object automatically and cannot be corrupted easily.
- It is used when a variable is not used outside the function.

**Disadvantages of Stack **

- It can increase the risk of stackoverflow.
- Random access is not possible and stack memory is limited.
- Much risk of abnormal termination.
- It is not very flexible and that’s why it sometimes shows undefined behaviour of the program.

**Applications of Stack **

- Stack is used for reversing a string.
- We can do backtracking with the help of it. ● It is used to check opening as well as closing of the tag.
- It helps in syntax parsing.

Example:-

A good real-life example of a stack is the pile of dinner plates that you encounter when you eat at the local cafeteria: When you remove a plate from the pile, you take

the plate on the top of the pile. But this is exactly the plate that was added (“inserted”) most recently to the pile by the dishwasher. If you want the plate at the bottom of the pile, you must remove all the plates on top of it to reach it. Another, sadder, example of a stack is the slogan, “last hired, first fired,” which is typically utilized when a company reduces its workforce.

**Queue **

A queue can be defined as an ordered list which enables insert operations to be performed at one end called REAR and delete operations to be performed at another end called FRONT. Unlike a stack, the queue is a collection of objects that are inserted and removed according to the First-In-First-Out (FIFO) principle.The order is First In First Out (FIFO) is an excellent example of a queue. It is any queue of clients for a useful resource where the patron that came first is served first. The difference among stacks and queues is in casting off. In a stack we cast off the object the maximum currently brought. In a queue, we do away with the item the least lately brought.

**Advantages of Queue **

- It is flexible and fast.
- It can handle multiple clients.

**Disadvantages of Queue **

- Due to the FIFO or other order feature, search of elements from a queue is ineffective.
- Elements can be enqueued or dequeued only at the front or end of the queue.

**Applications of Queue **

- Queues are used as buffers in applications like MP3 player, CD player,etc.
- Serving requests on several single shared resources like CPU task scheduling, and printer, etc.
- It handles interrupts in the real-time system following FIFO.

Example:-

Queue q1 = new LinkedList(); |

Queue q2 = new PriorityQueue();

**Linked List **

It can be defined as a collection of objects called nodes that are stored randomly in the memory. A linked list also can be defined as a collection of nodes in which one node is connected to the other node, and one is called the data part and another one is considered as the address part. Thus, the first node is called head and the last node is known as tail.

**Advantages of Linked List **

- The size of the linked lists is not fixed and we can change it according to our requirement.
- The memory consumption of linked lists is efficient. ● Insertion and deletion in linked lists are much easier. ● It is easy to implement. Both the Stacks and Queue can be implemented using this.
- No wastage and also reduces the access time.

**Disadvantages of Linked List **

- It needs to access each node sequentially, therefore, no element can be accessed randomly.
- Reverse transverse is difficult.
- It occupies much more space as compared to array.

**Applications of Linked List **

- The hash tables are implemented using a linked list. ● It helps in performing operations on polynomials. ● It is used to represent sparse matrices.
- It can be used to implement dynamic memory locations.

Example:-

It can be easily clear by the real life example. Human brain can be a good example of a singly linked list. In the initial stages of learning something by heart, the natural process is to link one item to the next. It’s a subconscious act. Let’s take an example of mugging up 8 lines of Wordsworth’s *Solitary Reaper*:

*Behold her, single in the field, *

*Yon solitary Highland Lass! *

*Reaping and singing by herself; *

*Stop here, or gently pass! *

*Alone she cuts and binds the grain, *

*And sings a melancholy strain; *

*O listen! for the Vale profound *

*Is overflowing with the sound. *

Our mind doesn’t work well like an array that facilitates random access. If you ask the guy what’s the last line, it

will be harder for him to tell. He will have to go from line one to reach there. It’s even harder if you ask him what’s the *fifth line*.

But if you give him two lines, it becomes easy for him to get a better flow. And if not then he can only get back his flow by starting from the first line.

I hope you might get an idea behind the working of Linked list.

**Binary Tree **

A binary tree is a recursive data structure where each node can have at most 2 children which are referred to as left child and right child. The topmost node is called the root node, and it is the main node as we can reach any node from the root node. Also, an empty tree is represented by a Null pointer.

**Advantages of Binary Tree **

- It can represent data with some relationship between them.
- Trees are very flexible data, allowing to move subtrees around with minimum effort
- It can easily transverse the elements to retrieve the elements.
- Insertion and search of an element is more efficient.

**Disadvantages of Binary Tree **

- Sorting of elements becomes difficult sometimes.
- It is not flexible enough.

**Applications of Binary Tree **

- It is used in wireless networking and memory allocation.
- It is also used in cryptographic applications to generate a pseudo-number tree.
- It is used in implementing various efficient priority queues.

Example:-

An example of a perfect binary tree is the (non-incestuous) ancestry chart of a person to a depth, as each person has exactly two biological parents (one mother and one father).

**Binary Search Tree **

A binary search tree is a useful data structure in java for addition and removal of data. We also defined it as a class of trees, in which nodes are arranged in specific order. For a binary tree to be a binary seek tree, the statistics of all the nodes within the left subtree of the foundation node have to be less than the statistics of the root. The information of all the nodes in the right subtree of the basis node must be extra than the same to the records of the foundation. As a result, the leaves at the farthest left of the tree have the bottom values, whereas the leaves on the proper of the tree have the greatest values.

**Advantages of Binary Search Tree **

- At each step, we get hints so searching becomes super efficient in the binary search tree.
- As compared to array and linked list, insertion and deletion operation are super fast.
- It is considered as an efficient data structure.

**Disadvantages of Binary Search Tree **

- Random excess is not possible in binary search trees.
- Chain storage wastes is less efficient when reading a specific node.
- Also, ordering adds complexity.

**Applications of Binary Search Tree **

- It is used in every high bandwidth router for storing router tables.
- It is also used in wireless networking and memory allocation.
- It is also used in compression algorithms.

**Heap **

It can visualise a heap as an array as a complete binary tree. And we know a binary tree is a tree which has a maximum of two children. Heaps can be of two types:

Max-Heap: In a Max-Heap the key present at the root node must be greatest among the keys present at all of its children.

**Max-Heap**: In a Max-Heap the important thing present at the basis node needs to be finest among many of the keys present in any respect of its children. The equal property has to be recursively proper for all sub-timber in that Binary Tree.

**Min-Heap**: In a Min-Heap the key present at the root node needs to be minimum among the keys present at all of it’s childrens. The same property has to be recursively authentic for all sub-trees in that Binary Tree.

**Advantages of Heap **

- It helps us to find maximum and minimum numbers.
- It allows us to access the variable globally.
- It doesn’t have any memory size and also heap method used in Priority Queue.
- It runs garbage collection on heap memory to free the memory used by the object.

**Disadvantages of Heap **

- It takes more time to compute.
- The memory management in heap memory is more complicated.
- Random access is not possible in heap.
- Heap sort is unstable and expensive.

Example:-

Heap Sorting can be applied to a sim card store where there are many customers in line. The customers who have to pay bills can be dealt with first because their work will take less time. This method will save time for many customers in line and avoid unnecessary waiting.

**Hashing **

Hashing is a technique to convert a range of key values into a range of indexes of an array. It uses special hash functions and provides constant time access. But sometimes, these hashing functions lead to collisions that two or more keys are mapped to the same value.Chain Hashing avoids collisions. The main idea behind the hashing is used to create a pair. If the key is given, then the algorithm computes the index at which the value would be stored.

**Advantages of Hashing **

- It provides a much effective way of fetching elements in constant time.
- They are synchronized.
- Sometimes, hash tables are much more effective than any other binary tree.

**Disadvantages of Hashing **

- Hash collisions are practically unavoidable.
- Hash Tables don’t provide null values.
- As there are many collisions, they become less efficient.

Example:-

Let us say that I decide to upload all of my documents, music, and videos up to Dropbox or Google Drive. I’m thrilled that I won’t need to store 60 GB of files locally on my computer anymore! But, I might be a little worried: how can I be sure that Dropbox or Google isn’t tampering with my files?

Hashing provides a clever solution. Before I upload all of my files to Dropbox/Drive, I can compute the hash of each file. Each hash is typically just a few bytes (merely 32 bytes in the case of the SHA-256 hash function), so storing hashes for even a million files won’t be a problem.

**Graph **

A graph is a data structure in java for storing connected data like a network of people on a social media platform. It is a pictorial representation of a set of objects where some pairs of objects are connected by links. The

interconnected objects are represented by points termed as vertices, and the links that connect the vertices are called edges.

**Advantages of Graph **

- It is also helpful in drawing activity networks diagrams.
- It helps in finding the shortest path thus making things much efficient.

**Disadvantages of Graph **

- Irregular memory access patterns are usually slow.
- Sometimes it leads to complexities.

**Applications of Graph **

- It is used to represent the flow of computation.
- It is suitable for many applications like Google maps, Facebook, Linkedin, etc.
- It helps in mutually dependent tasks.

We hope that you may find this interesting and this introduction may help you in building your basic foundation of data structure in Java as a beginne