All applications and systems we see and use today require data to function. When there is a large set of data that the application needs to access, show, or edit, there arises a need to store the data in an easily accessible and manageable way. This is where data structures come into play.
Table of Contents
What are Data Structures?
A data structure is a method of organizing and storing data in a computer to enable efficient access and manipulation. It represents the logical or mathematical arrangement of data, along with its implementation in a program. Java provides various data structures that allow developers to store, manage, and manipulate data in a straightforward and scalable manner. Mastering data structures is an integral part of building high-performing and scalable modern applications and systems.
Importance of Data Structures in Java
Managing data is an integral part of building and maintaining any kind of application or system. Data structures and algorithms in Java provide a clean way for developers to store, access, and manipulate data efficiently. They are implemented through both built-in types and custom user-defined structures, allowing extensive flexibility to developers. Think of data structures as containers that store data, and so, depending on the size and shape of the data, you choose the most suitable one from all the available options.
Classification of Data Structures
Data Structures in Java are classified based on how the data is stored, organized, and accessed. There are mainly 4 categories, namely linear, non-linear, static, and dynamic data structures.
- Linear Data Structures: Elements are arranged sequentially, one after the other. Each item is connected to the previous and next, making traversal straightforward.
- Non-linear Data Structures: Not all elements are directly connected, allowing for more complex relationships.
Linear Data Structures in Java
Let’s delve a bit further into all the available linear data structures in Java and their practical applications.
1. Array Data Structure in Java
An array is the simplest and most fundamental data structure in Java and all of computer science. It is a fixed-size container allowing the developer to store data of the same type. Values in the array are assigned an index starting from 0, and you can access the data by using the index of the item.
Here is an example of how to create an array of 5 numbers. The first two places in the array are assigned 10 and 20 using the index, and the rest are still 0:
Advantages:
- Arrays allow for faster access to values.
- Less memory is utilized as compared to linked structures.
- Arrays have a simple syntax and are easy to use and understand.
Disadvantages:
- The Size of an array is defined at declaration, making it a less flexible choice.
- Removing or inserting elements at positions other than the end of the array involves shifting elements (O(n) time complexity).
2. Linked List Data Structure in Java
A linked list data structure in Java is a linear data structure where elements(nodes) are linked together using pointers. Unlike arrays, linked lists do not have a fixed size and can grow as and when required. Each node is made up of two components: the actual data and a pointer to the next node in the chain.
Linked lists in Java are supported through the LinkedList class in java.util package.
The illustration above demonstrates how a new node E is inserted after node D in a singly linked list. Initially, D points to NULL, but after insertion, it points to the new node E, which in turn points to NULL, preserving the structure of the list.
Example:
Output:
[New York, London, Tokyo]
Advantages:
- Linked lists can grow or shrink when required, unlike arrays.
- Adding or removing elements from the beginning or middle can be done more efficiently than in an array.
- Memory is allocated as needed, unlike arrays that reserve memory at declaration.
Disadvantages:
- Accessing elements in a linked list is slower when compared to arrays.
- Operations are more error-prone due to pointer management.
3. Stack
A stack data structure in Java utilizes the Last-In, First-Out(LIFO) principle, and the last item added to the stack is the last one removed. You can implement it by using the ArrayDeque utility in Java like so:
Elements are added using the push() operation and removed using the pop() operation. The topmost element can be accessed using top().
Example:
Output:
Top element (peek): 50
Removed top element (pop): 50
New top after pop: 40
Stack size: 4
Java’s ArrayDeque is generally preferred over Stack for performance reasons, as it is faster and more memory-efficient. You can use the following statements to perform actions on a stack in Java:
- push() – Add an element to the top
- pop() – Remove and return the top element
- peek() – View the top element without removing it
- isEmpty() – Check if the stack is empty
Advantages:
- The LIFO principle allows stacks to be the optimal choice for problems like expression evaluation, undo operation, etc.
- The simple operations in stacks allow for an intuitive and efficient experience.
Disadvantages:
- You can only access the top element, which is a limiting factor.
4. Queue Data Structure in Java
A queue data structure in Java is similar to a stack, but instead of LIFO, queues use the FIFO principle (First-In, First-Out). Picture, if you can, a queue of people waiting their turn. The most commonly used way to integrate queues in Java is the Queue interface and classes like LinkedList and ArrayDeque.
As you can see, elements are added at the rear (enqueue) and removed from the front (dequeue), demonstrating FIFO (First-In-First-Out) behavior.
Example:
Output:
1
2
Just like in stacks, Java provides methods that will let you perform actions on the queue:
- offer() / add() – Insert an element at the rear
- poll() / remove() – Remove and return the front element
- peek() / element() – View the front element without removing it
Advantages:
- Queues in Java follow the FIFO principle, making it an ideal choice for scheduling, buffering, and task queues.
- Java provides various variants of queues, such as Queue, LinkedList, PriorityQueue, and ArrayDeque, for varying requirements.
Disadvantages:
- Only the front and rear elements are accessible, making it less flexible for more complex use cases.
- If not managed properly, queues may consume a lot of memory.
Non-Linear Data Structures in Java
Non-linear data structures in Java are used to store more complex data. Let’s have a look at a few of them in detail.
1. The Tree Data Structure in Java
A tree data structure in Java resembles a family tree or an organizational chart. Unlike arrays or lists, trees do not store data sequentially; instead, they branch out where each item(node) can connect to multiple items in the tree. The first node is called the root, and it branches out to child nodes, which branch out to child nodes of their own. Trees are used when you have data that has a natural hierarchy.
At the top is the root node (A), which is the starting point of the tree. Each node may have child nodes, and those sharing the same parent are called siblings. For example, D and E are children of B, and also siblings. The connections between nodes are called edges, and groups of connected nodes form subtrees. Nodes with no children—like K, L, and P—are known as leaf nodes. The level of a node represents its depth in the tree, and the height of the tree is determined by the longest path from the root to a leaf.
Java doesn’t have a built-in Tree class like it does for lists or maps, but you can easily build one yourself:
Example:
Output:
Height of tree: 5
Advantages:
- The hierarchical layout of trees makes it the ideal choice for file systems, DOMs, etc.
- Trees maintain sorted data, enabling in-order traversal.
Disadvantages:
- Trees require careful implementation, which may not be viable for a beginner.
- Access time for trees is usually slower than for Arrays.
2. Graphs
A graph data structure in Java is similar to trees; the difference is that, unlike trees, graphs can connect nodes in any direction and not only from parent to child. Graphs in Java are made up of nodes(also called vertices), and the connections between them are called edges.
The diagram above visualizes a directed graph where:
- Vertices (green circles labeled 0 to 4) represent the nodes in the graph.
- Edges (the arrows) represent the connections between these nodes.
- Unlike trees, edges in a graph can form cycles and travel in multiple directions.
Think of graphs like a map where cities are nodes and the roads connecting them are the edges.
While Java doesn’t provide a Graph class out of the box, you can create one using data structures like HashMap, ArrayList, or custom classes.
Output:
0 -> [1, 4]
1 -> [3, 2, 4]
2 -> [3]
3 -> [4]
Advantages:
- Graphs have a flexible relationship between elements, making them the ideal choice for networks, maps, and so forth.
- Using algorithms like DFS and BFS, graphs can solve problems like shortest path, cycle detection, and topological sorting.
Disadvantages:
- Requires a good understanding of traversal algorithms and edge cases (like cycles).
- Visualization and debugging can be tricky in large or dense graphs.
Hash-Based Data Structures
Hash-based data structures in Java provide a better way to store key-value pairs and retrieve them quickly. They utilize a technique known as hashing that converts keys into a unique index called a hash code, where the value is stored. Let’s have a look at some of the most commonly used hash-based data structures.
1. HashMap
Let’s start with the most popular hash-based data structure, the HashMap. It is a part of java.util package and allows you to store and retrieve values using unique keys.
Each key (in blue) is uniquely associated with a value (in purple). The red arrows show the one-to-one mapping between keys and their corresponding values. This structure allows for quick data retrieval when the key is known, which is why it’s commonly used in scenarios like storing user data, caching, or configuration settings.
Here is a simple example of HashMaps in Java:
Example:
Output:
Alice’s score: 90
Bob’s score: 85
Alice scored 90
Bob scored 85
2. HashSet
A HashSet is similar to a HashMap but is used to store unique elements. Internally, it uses a HashMap providing fast performance. A HashSet is the optimal choice if you want to make sure that there are no duplicate items in your list.
Example:
Output:
[Banana, Apple]
3. HashTable
Yet another hash-based data structure in Java is the HashTable. Similar to a HashMap, it also stores key-value pairs. However, HashTable is synchronized, meaning it is safe to use in a multi-thread environment without any extra code.
Example:
Output:
95
Advantages of Using Data Structures in Java
Java provides a wide range of data structures that developers can utilize to manage and store data as per their requirements. The right use of data structures in the right scenario can make your code more readable and efficient. You can create data structures using Java with the Collections Framework, which provides well-tested implementations of lists, sets, queues, maps, and more. This saves time and reduces the need to build complex data structures from scratch. Let’s delve a little deeper into the different types of data structures and their application in Java.
Java Data Structures Interview Questions
Mastering data structures and algorithms in Java is integral, whether you are applying for an entry-level position or a senior-level one. Now let’s have a look at some of the commonly asked data structures and algorithms interview questions.
1. What is the difference between ArrayList and LinkedList in Java?
Both ArrayList and LinkedList are part of the Java collections framework. They differ in how they store and manage data. ArrayList uses a dynamic array to store elements, which can be accessed using the index of the element. This makes it faster in terms of accessing values. LinkedList stores elements in a chain of nodes, which makes it faster for insertion and deletion of data.
2. How does a HashMap work internally in Java?
HashMaps in Java use an array of buckets to store key-value pairs. Each bucket is a linked list, and each element in the bucket is called an entry. While adding an entry into a HashMap, Java initially calculates the hash code of the key using the hashCode() method, which is then processed to find the appropriate bucket index where the value is stored.
3. What are the time complexities of basic operations in HashMap, ArrayList, and LinkedList?
Understanding time complexity helps you use the right data structure for the right job. Here is a comprehensive table of the time complexity of basic operations in Java:
| Operation |
HashMap (Average) |
ArrayList |
LinkedList |
| put(), get(), and remove() |
O(1) |
O(1) |
O(n) |
| Insert (add) |
O(1) |
O(1) |
O(1) |
| Delete (remove) |
O(1) |
O(n) |
O(1) |
| Search |
O(1) |
O(n) |
O(n) |
4. When would you use a Stack vs a Queue?
When choosing a stack vs a queue data structure in Java, it is important to think about the order in need you need to process each element. A stack follows a Last-In, First-Out principle, where the last element added is the first to be removed. Common example scenarios include, but are not limited to, undo functionality in text editors and tracking recent history.
However, a queue follows the First-In, First-Out principle, where elements are removed in the same order they are added. Queues are ideal for tasks such as job scheduling, handling server requests, and so on.
5. What is the difference between HashMap and HashTable?
Synchronization is the differentiating factor between HashMap and HashTable. HasTable is synchronized(thread-safe) and HashMap is not. HashMap allows one null key and multiple null values while HashTable does not. It is to be noted that HashTable is considered legacy and has been replaced by HashMap or ConcurrentHashMap in modern code.
Conclusion
We have so far covered all the fundamentals of data structures in Java. Data structures can be a difficult topic for beginner programmers to understand, and that is why we suggest that you gain further knowledge from our data structures and algorithms in Java made easy tutorial. For further reading material, we suggest the highly acclaimed Data Structures and Algorithms in Java by Robert Lafore. Don’t forget to apply what you have learned in real-world applications and scenarios.