Data Structures in Java Every Java Programmer Must know
Let us look at a real-life example before we progress to this topic of Data Structures in Java.
Suppose, there is a task where you need to calculate the number of coins in a bag. What you decide to do is you simply take one coin, count it, and put it back in the bag. You may count incorrectly if you use this method. So you take out all the coins at once and lay them beside one another in a linear fashion. You then start counting from the first coin till the last coin and thus manage to count the number of coins easily.
This linear style of putting elements is a data structure for programming languages. This particular style is an array. Let us dive in!
Don't become Obsolete & get a Pink Slip
Follow DataFlair on Google News & Stay ahead of the game
Data Structures in Java
The primary definition of a data structure is a mode of storing data that is efficient for insertion, deletion, and location of data. In today’s world, quick and efficient software is essential for users. Nobody can wait for a 14-minute buffer to watch a tutorial on Java.
Data Structures help in improving the response time of software. Hence Data Structures are of prime importance in software design and programming. Data Structures are essential for software development as quick and efficient software is of prime importance.
Hence Data Structures are an irreplaceable part of programming.
Need for Data Structures in Java
- Speed of processing – Data is growing in size as we speak. Efficient Data Structures allow us to manipulate and retrieve data easily. Data Structures also help in reducing the response time of software.
- Retrieval of Data – The faster the data retrieval from a database, the better the application. Hence using the correct data structure to store data is important.
- Multiple requests – A single web server can get a million hits in a very short amount of time. Take the example of a website that posts the result of JEE. Hundreds of thousands of people all over the country log in and try to retrieve data from the database. In this case, without the proper implementation of a good data structure and efficient algorithms, the website is doomed to fail.
Advantages of using Data Structures in Java
- Efficiency – Efficiency, every aspect of data structures revolves around this word. Whenever you think of any particular data structure, be it arrays or hashmaps, has a particular efficiency of work. This means that the output for the same amount of work is different in different data structures.
- Reusability – A data structure should be reusable. This is because the same data structure may come in handy for solving a lot of different problems. So data structures define a particular blueprint of managing these data so that they are reusable.
- Abstraction – Hiding unnecessary details about a function and focusing on the important aspects of it is Abstraction. There are Abstract Data Types (ADT) in java which implement abstraction.
Classification of Data Structure in Java
There are primarily two divisions of data structures in Java
- Linear Data Structures
- Non-Linear Data Structures.
Linear Data Structures in Java
If all the elements in the structure formation in a linear fashion, then the data structure is linear. For example, Arrays are linear data structures as the elements inside it arrange themselves in a linear order.
Non-Linear Data Structures in Java
Non-linear data structures, as the name suggests, orders its elements in a non-linear fashion. They position their elements across multiple levels. A very good example of a non-linear data structure are binary trees.
Types of Data Structures in Java
Some of the very basic data structures in java are as follows.
- Linked Lists
Arrays in Java
This is the most simple data structure you will ever come across. It is a linear data structure. This data structure can refer to a group of similar data types by a common name. This is essentially useful when we need to conserve variable names. That’s where we can use the same name for all the different variables of the same type.
There are a few points to remember while using arrays.
- All arrays are objects in Java.
- Arrays contain elements of similar data types. This means that you can create arrays containing elements that are int, float, or long. You can even create arrays of user-defined datatypes, i.e, of a particular class.
- All indexing in arrays start from zero. (0)
- The last element has an index(Length of array-1)
- There is a member variable of array objects called “length”. We can use this variable to get the length of the array.
- This value of the length variable is always an integer. An array cannot contain a fraction of an element.
- Arrays store dynamic information with the help of heaps.
- You need to statically declare the number of array elements when declaring an array. This is why arrays are static data structures.
Types of Java Arrays
- Single dimensional Array
- Double Dimensional Array
- Multi-Dimensional Array
Time complexities for Arrays in Java
- Data Retrieval- O(1) – This is because array indexes point to each element in the array.
- Data Insertion-O(n)– It takes linear time to insert an element in an array. This is because you need to traverse the entire length of the array while inserting an element.
- Data Deletion – O(n)– It takes linear time to delete an element. This is due to the fact that you have to traverse an entire length to delete a single element.
Linked Lists in Java
If you want to understand Linked Lists, let us see a real-life example first. For example, if you live far away from the place you work and there is only one bus connecting your house to your office. So if one day you miss the bus, then you won’t be able to come to work that day. This means that your presence in the office is linked to the availability of that bus.
If you miss the link bus, you do not arrive at your office. This is similar to linked lists in Java where every element has a data value and a pointer of type “Node” that points to the next node in the list.
Advantages of Linked Lists over other data structures in Java
Linked lists are better than arrays because they do not require the length specified to them. This means that linked lists are dynamic. Their sizes vary according to the user. This also means that the insertion and deletion operations are simpler.
Types of Linked Lists in Java
- Singly Linked lists
- Doubly Linked Lists
- Circular Linked Lists
Singly Linked Lists in Java
Singly-linked lists are the simplest form of linked lists. These linked lists contain a data node and a pointer pointing to the next node. The terminating node has null as the next pointer. This means that the list ends there and there are no nodes after that.
A “HEAD” or a “START” pointer is pointing to the start of the list. If you have to traverse the list, then simply start from the HEAD pointer. Keep progressing through the pointers and end at the last node.
Java Doubly Linked Lists
Doubly linked lists are similar to singly-linked lists. However, the only difference is that each node also contains an additional pointer to the previous node in the list. Note that singly-linked lists only point to the next node. However, the doubly linked lists point to the previous node as well. This means that doubly linked lists allow you to traverse both ways inside a list.
Java Circular Linked Lists
Circular linked lists, as the name suggests, are circular in fashion. How? The last node always pointed to NULL. Remember? That indicated the endpoint of the list. However, in circular linked lists, the last node in the list points to the first node. All other characteristics of circular linked lists are the same as doubly-linked lists.
Time complexities for Linked Lists in Java
- For Data Traversal – O(n)
- For Data Searching – O(n)
- Time for Data Insertion – O(1)
- For Data Deletion – O(1)
Stack in Java
Stacks are a very popular data structure in programming. A lot of programs follow the stack concept. To understand stacks, imagine a book. Now you have 10 books. You keep putting books one on top of another. The result you see in front of you is a stack of books.
Now note, whenever you put a book in the stack, you always put it on top of the last book you placed in the stack. Also whenever you want to remove an element from the stack, you remove the last book you placed on top of the stack.
Similarly, in a stack data structure, you can insert and delete from the top of the stack. You cannot remove or add elements to any other position of the stack.
This means that stack implements LIFO(Last In First Out). The last element to enter the stack is the first one to leave the stack.
There are a few technical terms related to stacks that you need to know.
- Pushing– Pushing is the addition of data items at the top of the stack.
- Popping– Popping is the process of deleting the topmost element in the stack
- Peeking– Peeking is the process of reading the topmost element in the stack.
You can use arrays or linked lists to implement stacks in Java. The stack will behave like an array if you use an array to implement stacks. In the same way, the stack will inherit all the properties of linked lists if you use lists to implement the stack.
Stacks are particularly useful in
- Maze problems
- Nested parentheses matching
- Nested function calls.
Queue in Java
You must be familiar with queues in real life. Whenever you need to watch the latest Avengers movie or buy the latest iPhone you have to face the terrible queues at the front of the hall or the shop. This phenomenon is also useful in programs.
Queues, unlike stacks, queues implement the FIFO strategy(First In First Out). This means that the first element to get into the queue is the first one to leave the queue. In real life, the faster you arrive at the store, the lesser people there are in front of you. In this way, you get your new iPhone faster than anyone else.
Every time a data item gets inserted in a queue it takes the last position of the queue. This is the rear end of the queue. Some popular terms related to a queue that you need to know are:
- Enqueue– This is the process of adding elements to the rear of a queue.
- Dequeue– This is the process of removing data items from the front of a queue.
Variations in Queue in java
- Circular queue– Circular queues are queues that arrange the front and the rear end of it in a circular fashion. This eliminates the storage crunch which is a result of using linear arrays as queues.
- Dequeue– Dequeues is short for double-ended queues. This essentially means that the insertion and deletions operations can take place on both ends of the queue. Note that you can add or delete data items from only the two ends of the queue and not the middle.
Famous Applications of Queues in Java
- Queues are useful in designing operating system scheduling algorithms such as FCFS(First Come First Serve).
- They help power reservation systems, service center helplines, and traffic flow.
- They are essential for implementing Graph algorithms.
Graphs in Java
Graphs are the non-linear data structures in Java which have :
- Vertices/Nodes – These are the endpoints of an edge
- Edges- These connect the Nodes amongst each other.
- All edges are connected to two Nodes. Hence we can represent them by a finite set of ordered pairs(u,v).
- Generally, V denotes the number of Vertices and N denotes the number of edges in the graph.
Graphs are of 4 types:
- Directed Graphs
- Undirected graphs
- Weighted Graphs
- Non-Weighted Graphs
Let us take a look at all of them one by one.
Directed graphs are those graphs where there is only one way to traverse a single edge. This essentially means that you can only travel from one node to another if the direction on the edge allows it. If there is a direction from A to B and B to C and C to A, then you can travel from A to B but not from B to A.
Undirected Graphs are essentially the complete opposite of Directed Graphs. They do not have directions associated with the individual edges.
You can travel either way in between two nodes.
Weighted graphs, as the name suggests, have a specific weight to each of its edges. This generally gets interpreted as the cost of traversing the edge. Every node in a weighted graph has a cost.
Non-weighted graphs are opposite to weighted graphs. They do not have weights assigned to their edges. You can traverse every edge without incurring a cost.
Sets in Java
A set is a similar collection as an array. It contains elements in a linear order. However, there is a catch. There can not be any repeating elements in a set. This interface is present in the java. util package and extends the collection interface in Java. SortedSet and NavigableSet implement the Set Interface.
Sets particularly find use in situations where we need to store the data which is unique for each entry. If you have read about databases, sets are useful for storing the unique ID.
For example, if a database is storing all the addresses of a group of people working in a company. For each person, the program would assign a Unique ID that points to that individual only.
We understood the underlying concepts of data structures in Java. We learned about arrays, stacks, queues, graphs, and sets in Java. Hope you liked the article. Do post your queries in the comment section.