Data Structures and Algorithms in Java

All of us, irrespective of whether we have majored in computer science or not, have come across the term ALGORITHM. What exactly does this word mean? Let us discuss it with you in a very elusive manner. We will start explaining it to you with a basic level, and then will go to the veteran level. Let us also throw some light on Data Structures and algorithms in Java.

When there were no computers, there were algorithms, and when there are computers, there are even more algorithms. Algorithms are nothing but a formal set of instructions that help a system or a person break the problems, analyse them part by part, and then develop a set of mathematical instructions to solve that problem. But then, understand this fact that algorithms and core logic building is the mother of all present-day mathematics.

With the onset of a particular strategy to solve an issue, there came logics, and with the onset of logics, there came algorithms. When there came algorithms, there came formal languages to solve such problems with programs called programming languages in today’s world. One thing you can consider is that Algorithms are the bedrock of any programming language.

But, “Algorithms are not confined to mathematics alone”. When you cook bread from a recipe, you’re following an algorithm. When you knit a sweater from a pattern, you’re following an algorithm. When you put a sharp edge on a piece of flint by executing a precise sequence of strikes with the end of an antler—a key step in making fine stone tools—you’re following an algorithm. Algorithms have been a part of human technology ever since the Stone Age. 

Looking through the lens of computer science algorithms can teach us about the nature of the human mind, the meaning of rationality, and the oldest question of all: how to live. Examining cognition to solve the fundamental computational problems posed by our environment can utterly change the way we think about human rationality. 

The notion that studying the inner workings of computers might reveal how to think and decide, what to believe and how to behave might strike many people as not only wildly reductive but, in fact, misguided. Even if computer science did have things to say about how to think and act, would we want to listen? We look at the AI and robots of science fiction, and it seems like theirs is not a life any of us would want to live. Alan Turing (one of the greatest computer scientists, often informally called a Newton of Computer Science) defined the very notion of computation by an analogy to a human mathematician who carefully works through the steps of a lengthy calculation yielding an unmistakably right answer. Many people say that studying algorithms is somewhat similar to learning to code, and they often refer to algorithms as pseudocode. Yes, that is true up to a certain extent, but studying algorithms is not the same thing as learning to write code; learning to write an algorithm means you have laid the foundation of the code, and now the skyscraper (our code) is ready to be implemented.

Also Read: Top Java Interview Questions and Answers for Freshers in 2021

ASYMPTOTIC ANALYSIS (Time space complexity) 

Before coming to the asymptotic analysis, we would like to discuss the time-space complexity.  In any computer program or any algorithm, this term is used quite often. So what’s that typically mean? It means, in a situation of limited time (where a user would be waiting to get the reply). Limited space (where we have limited RAM and hard disk), we need to use the computational resources very carefully. Hence, we need to check how much these resources are being consumed. Hence, if a program is consuming too much of these resources, then we should try to find out (if possible) to get an optimum solution for reducing the time-space complexity. Time-space complexity is a trade-off. You can write an algorithm that has a very less number of lines in the code during implementation. Still, then, it may result that the time complexity is huge (for example, in the case of recurring functions and recurring programs), it’s even possible that with very less time complexity, the algorithm is taking very high space ( in the case of iterative programs, if the number of iterations is too large then such thing is quite possible). So, we need to find a perfect balance that should consume too much time nor take up too much space. So, this particular concept is called time-space complexity. Now before going to the next topic, we  would like to talk about a very basic point. If we are finding the upper bound or the lower bound of any algorithm, then it is usually after a certain input. Before that input, the function curve can have any fluctuations even beyond the upper bound and even lower than the lower bound. So, this particular input value, which is denoted by N, and beyond this input value,  our main calculation would begin. Since the algorithms have the main fluctuations in the initial values, N is an input value at the starting range of the inputs. After that,  when the curve is somewhat stable, we apply all the concepts to find the upper bound and the lower bound. 

For every quantity, we usually have an upper limit and one lower limit. Be it anything, we as human beings tend to know the range between which any quantity lies. There are maximum profit estimates in any business and maximum run rate in a match of cricket.  So, computers are no exception. Whenever a computer performs any task, we tend to think that in the worst-case scenario, what will be the time taken by the computer to complete the given task. So in that sense, we need some parameter to define the upper bound and the lower bound (which would signify the best case scenario). And also, it not always we are so unfortunate that it would be the worst-case scenario every time we run a program, neither it is the case that it is always the best case, so technically, we need some cases that would tell us the average case scenario for which the computer would tell us about how much time it would require to get the output if the given input is somewhat in between the best case input and the worst-case input. Now, we have another parameter, which would be used most if we need to find the computational complexity. So, let’s start one by one to explore what these concepts are and how they are implemented in each case.

1. THE BEST CASE SCENARIO –

This is also known as the big omega (Ω). This describes the lower limit of any performance curve, as the best-case scenario will take the least time to get the function or program to be executed. By looking at the lower bound of the performance curve, a computer scientist can quickly determine the minimum time required when everything goes fine. This will give a clear idea that the algorithm or the program won’t be possible to optimise further beyond this. But,  in the real world scenario, the best cases occur significantly less. This means it is not something that is very frequently used for all the cases. 

2. THE WORST CASE SCENARIO-

It is the case, when the inputs given are totally  against the working flow of the algorithm. Seems confusing right? Hold on. Just keep  reading. The worst case scenario will come into play, when we need to consider  the worst case scenario, that if all the inputs are lengthy, complex inputs and even  complicated, so does the computer have any choice to say, “this is too much, I am sorry  I can’t handle this! No right? That means, no matter how many complex inputs are  given, the computer has got no choice but to execute it. Seems perfect? Just as we  human beings, when we are asked to calculate the value of 2+2, we can do it in  seconds, but then, if the input given to us is, let’s say, (1 + x)^n = 1+(nx/1!)+(n(n-1)x^2)/2!+… ⋯where x=6? 

It will take at least a few minutes, or even more  than that to evaluate the exact answer. So, the computational time and computational  complexity depends upon how simple or how complicated the input that has been  given to us. So, as the old saying goes, prepare for the worst, be ready for the best. So  in the same way, computer scientists evaluate the worst case scenario, just to get an  idea, whether or not the worst case is too bad to be handled. At times, the worst  case scenario is so frustrating, that it may take a few days to get the results, yes, we are not joking, programs which have exponential time space complexity, and the input  given is too long, then it could result in a deadlock type of scenario. So now, the worst  case scenario needs to be calculated to get the estimate. It is usually denoted by the  big O.

3. THE AVERAGE CASE SCENARIO-

Finally, we have something that we can refer to for most of the common uses, which are not highly technical. When someone asks you about how much time it takes to reach Mumbai from Goa, we would obviously tend to give an average estimate; it may be somewhat more or somewhat less than that. If there is no traffic, we can have the best case, and if there is heavy traffic, we can have the worst case, but what if there is somewhat moderate traffic? So here comes our last parameter to calculate the time-space complexity of any algorithm. This is denoted by big theta (Ө). At times, when there are NP-hard problems, there is no particular solution to the given problem statement. There are many possible solutions. That’s why they are called non -deterministic and non-polynomial problems. So in those cases, the worst time is something which can give you a shock, and the best case also doesn’t work every time because in best cases, inputs are very less likely to occur, and hence, this notation is especially useful for NP-hard cases of problems.  

DATA STRUCTURES 

Data structures, as the name suggests, are the structures that store data. And when we need data, we usually fetch it by some data fetching algorithms and utilise the data in our work. Now, why are data structures so important in core computer science? The answer is simple. In your house, you generally keep all your books and stationery items in your cupboard on different organised shelves, right?

Similarly, we keep these data in an organised manner by storing them into the data structures, and hence data structures are so useful. It keeps all the data maintained and in order. Also, when in a hurry, when you look for a particular dress or handkerchief, you get it very easily because you have kept them in an orderly manner, right? Able to relate to daily life? Similarly, when fetched, the data has a lo0t easier access to get when we store them into a data structure. Now let’s see how these data structures are used in real life. We will take up a few examples and showcase how they are used today in daily lives. 

CAREER PROSPECT OF STUDYING ALGORITHM AND  DATA STRUCTURES 

So, everyone must be thinking that it’s ok to make our daily life a lot easier by studying algorithms, but then, how is it possible to make a career out of it? How can I earn a living if I choose to study algorithms? What are the career prospects that are available for us? How is it helpful in this aspect? So guys, hold your breath, let me answer all your questions one by one.  

You can become an outstanding academician, a researcher and, of course, a faculty of core computer science.  

There are venues in an industry where research is a specially vigorous activity, and researchers are treated very respectfully. They are the well-known industry CS “labs”. A few years ago, the big five were: Microsoft Labs, IBM Labs, Sun Labs and HP Labs, NOKIA labs. They were shining examples of how research could be embedded in an industrial setting, advancing the state of the art while also positively impacting the company’s bottom line. They were clearly delineated from the rest of the company and essentially served as an in-house CS department. One of such labs’ core activities was “technology transfer” so that the cool things they came up with could be disseminated to the rest of the company.  

HOW IS DATA STRUCTURES USED IN REAL LIFE 

Many of you guys might be thinking about how these data structures are used in real life. Let’s see that now. 

1. Keeping track of a leader board and maintaining the records in an orderly manner requires the application of an array. 
2. 2D arrays, known as matrices, are usually used in image processing. 
3. The various web pages attached to websites are linked with each other with the help of linked lists.  
4. GPS navigation uses the shortest path in a graph to find the shortest distance and find the best possible path. 

There are many more such operations where data structures are extremely helpful. 

TWO IMPORTANT TYPES OF DATA STRUCTURES

The 2 most important type of data structures are:

1. Contiguous memory structures (Arrays) 
2. Linked lists. 

Let’s look at each one of them one by one. 

CONTIGUOUS DATA STRUCTURES 

Arrays are the data structures that help store data into a system by allocating contiguous memory locations in the memory. This means that inside the hard disk, the memory blocks allocated for the arrays are all present, one next to the other and not random blocks of storage. This has many advantages. The first thing is that the read-write speed is very fast because we know where the next block is present. Also, easy to fetch and present the data and hence more chances of cache hit and page hit in any operating system. One of the major drawbacks of this kind of data structure is that, if allocated for any particular purpose, then it would remain static. Before implementing any program, you need to check how much exact space this structure requires. Depending upon that estimate, you need to allocate the storage, as once allocated, it would become very difficult to change. So that’s why sometimes it is also called a static allocation data structure. 

NON CONTIGUOUS DATA STRUCTURES 

When it comes to linked lists, automatically, the first thing that comes to our minds is dynamic storage data structures. In this case, what happens is that when we are not sure how much exact storage we require to implement a program, then we store one block of storage, and then as per our further needs and requirements, we extend the storage by linking one block to another. But in this case, all the blocks don’t necessarily stay at a contiguous block of memory, but the address of the next block of the linked list is present at the header of each block, which points at some reference address. So in this way, each address points to another address. At the end of the list, there is the null value which means that the list ends. It is typically represented by the “” value.  

OTHER TYPES OF IMPORTANT DATA STRUCTURES 

1. STACK- A stack is the type of data structure that will usually store data where the input is only from one direction. Input is usually from the top side of the stack, and the data gets piled up from the bottom to up, and when you want to remove a particular piece of data, you need to empty it from the “last added” piece of data. Consider it as a  pile of CDs, where the first disk entered can be only removed once all the CDs placed above it have been removed. This kind of structure is also called LIFO order,  which means last in, first out. 
   
2. HASH TABLES – A hash table is a data structure, typically a table that stores data that is repeatedly used into running an algorithm designed for dynamic programming purposes. Sounds confusing, right? Let me tell you more simply. In dynamic programming, there are two things; one is the optimal substructure and recurrent function. When some part of a problem is repeating over time, then, in that case, we usually frame the equation and store the data that is required repeatedly into a table, called a HASH TABLE. HASH TABLES are often analogous to routing tables in computer networks. 
   
3. GRAPHS- A graph is something that comprises nodes and vertices. They are the mathematical versions of representing paths or options available for solving one particular type of optimisation problems. There can be very complicated problems that may require very detailed analysis, and graphs are the ideal data structure for that.  
   
4. HEAP- As the name suggests, heap refers to the data structure, which will pile up the elements into a particular order. There are two types of heaps present. The first one is called the max heap, which has got all the elements arranged into an order where each subtree’s root element is the maximum. The overall root is the maximum element of the whole set of data, and then comes the min-heap, which has all the elements arranged into the reverse order; that is, the minimum element is at the root of each subtree. Heaps are very crucial in the implementation of algorithmic simulations of various programs. One of the best examples of heap implementation is implementing Dijkstra’s algorithm by using a Fibonacci heap. Dijkstra’s original shortest path algorithm does not use a priority queue and runs in O(V2) time. When using a Fibonacci heap as a priority queue, it runs in O(E + V log V) time, asymptotically the fastest known time complexity for this problem. 
   
5. BINARY TREE/BINARY SEARCH TREE – Trees, especially binary trees, are the type of structures that are extremely useful for all kinds of implementation purposes.  In short, Binary trees are the backbone of any algorithm when it comes to real-life problem-solving. It has one root node, followed by two child nodes. Heaps are a  type of fully completed binary tree or almost complete binary trees. 

ARE DATA STRUCTURES SAME IN ALL THE LANGUAGES? 

Data structures and algorithms at a high level will be the same across all programming languages, although implementation will differ between languages. For example, in C, you may use pointers to node structs to implement a singly linked list and have to understand how dereferencing works to make it work. But, in Java, you would simply have to work with a Node private inner class inside of a Singly Linked List primary class. So, in a nutshell, they are independent of any programming languages. 

IS JAVA GOOD FOR DATA STRUCTURES? 

For sure, the answer is yes. Java is one of the high-level OOPS languages that supports all the data structures we require to write a program and help solve problem-solving in the real world. Also, JAVA offers very simple implementation techniques compared to the first generation high-level languages like C or even, I shall say, C++. Learning java is a lot easier than learning its predecessors. Ask someone who has coded in C language, and they know what is the real pain to write code for each line, and then you would be able to see a few things that get implemented.  

Also Read: Exception Handling in JAVA with Examples

WHAT ARE THE DATA STRUCTURES SUPPORTED IN JAVA

JAVA supports the following types of data structures 

1. Array – The array is a type of data structure, which is used to store the data one after the other in a structured format, and it is a contiguous form of data structure, which means the data which are being stored here, lie one after the other sequentially. 

2. Linked List– Unlike arrays, linked lists are non-contiguous storage structures, which store data at random locations and not one after the other. One element of the linked list can be present at one part of the physical memory, and the other part can be present in another part of the physical memory, linked with a header, will provide the next block’s address. 

3. Stack- Stack is the type of data structure, which is like a CD/DVD stack, where entry and exit is one way only. It is not a two-way process. This means, when you insert a data bit to stack, then the nth data bit has to be removed first to remove the rest of the bits from it. It’s also sometimes referred to as Last in, first-out (LIFO). 

4. Queue– Queue is similar to stack, but a queue operates as a real-world queue. In Queue,  the person who is standing first goes out first—also referred to as first-in, first-out (FIFO).

5. Binary Tree– A binary tree is a type of data structure with a parent node and two child nodes at the most. There can be one child node even, but then, the tree would be called an almost binary tree and not a complete binary tree. A tree (especially a binary tree) helps in a lot of applications like sorting algorithms. 

6. Heap- Heap can be classified primarily into two categories,  

∙ Max Heap- a max heap is a binary tree (or an almost complete binary tree), which has the most significant element at the topmost node, and all the smaller elements followed by that. The lowest node is at the bottom-most place, called the leaf node. Max heap is used to build heap algorithms, heapify algorithms and above all, combining both the things gives us a heap sort algorithm, one of the most efficient algorithms to date for searching. 

∙ Min Heap- Min heap is technically just the opposite of the max heap. Min heap will have the parent node as the minimum of both the child node in all the subtrees and the tree as a whole. It helps in finding the minimum element in the heap sort algorithm.  

7. Hashing- Hashing is an important Data Structure designed to use a special function called the Hash function, which is used to map a given value with a particular key for faster access of elements. The efficiency of mapping depends on the efficiency of the hash function used. 

WHICH DATA STRUCTURE IS BEST FOR JAVA 

As far as any programming language is concerned, there is no best or worse data structure, it all depends upon the type of problem for which we are writing code, and hence it depends on the use case typically. When we want to implement some algorithm requiring matrix and their storage, we need 2D arrays, when we need implementation for some algorithms of cost optimization, let’s say, N Queens problem, we need stack allocation; similarly, for the famous dining philosopher’s problem (In computer science, the dining philosophers problem is an example problem often used in concurrent algorithm design to illustrate CPU/GPU synchronization issues and techniques for resolving them.), you would require almost all types of data structures that you have learnt in undergraduate. So it varies and depends upon the situation.

This brings us to the end of the blog on Java Data Structures. Wondering where to learn the highly coveted in-demand skills for free? Check out the courses on Great Learning Academy. Enrol in any course, learn the in-demand skill and get your free certificate. Hurry!

Engaging in the study of Java programming suggests a keen interest in the realm of software development. For those embarking upon this journey with aspirations towards a career in this field, it is recommended to explore the following pages in order to acquire a comprehensive understanding of the development career path: