Last Updated on December 14, 2022 by Prepbytes
Introduction:
Data structures in Java are an essential aspect of Computer Science. There are different types of data structures that help us store the data in different ways in the memory that in turn allows us to effectively utilise the memory. So, in this article, we are going to discuss 3 very important data structures viz, Arrays, Linked Lists, and Stacks in Java.
Data Structures in Java are an important part of Programming. Get a better understanding of problems by watching these video tutorials created by expert mentors at Prepbytes.
Let’s Discuss various Data Structures in Java.
Arrays in Java
Array: An array is a linear, contiguous collection of the same data type. Let us understand this with the help of the diagram shown below.
So, as you can see in the image above, we have an array of lengths 5. All the elements in this array are integers (same data type).
Now, what do we mean by contiguous memory? So, let us say that the address of the first block of the array is 4k. This is called the base address of the array.
Contiguous memory means addresses will be continuous as shown below.
Now, let us understand the memory mapping concepts of an array.
Array Declaration (With Memory Mapping)
Following is the code to declare an array in Java.
public class Main {
public static void main(String[] args) {
int[] arr;
}
}
So, in the above code, the line: int[] arr; declares a new array with the name arr. In the memory, the stack section of the memory holds the reference variable where null will be stored as the reference arr does not hold any valid address currently.
Array Initialization (With Memory Mapping)
The following is the syntax to initialise an array in Java.
public class Main {
public static void main(String[] args) {
int[] arr;
arr = new int[5];
}
}
This creates an array of length 5 in the heap memory. Since we have not filed any values in the array yet, the array will be filled with all the zeroes.
The above image shows that first the array was declared and the reference variable had null stored in it. Then, the array was initialised, and the reference variable stores the base address of the array. Since we did not fill the array, currently all the values are initialised to 0.
Direct Access
A value in an array can be accessed directly using the valid index. This means that the index should not be less than 0 or should not be greater than or equal to the length of the array.
Consider the following program to show the direct access in an array.
public class Main {
public static void main(String[] args) {
int[] arr = {1,2,3,4}; //another way to intialize the array
System.out.println(arr[1]);
}
}
We directly printed the value present at index 1, hence direct access.
The time complexity to access an element directly in an array is O(1) i.e. constant.
Traversing the Array and Length Property
In order to traverse the array, we can use the length property of the array in Java.
The indices range from 0 to arr.length -1. This is the case for every array. The indices will start from 0 and the last index will be the length of the array -1.
So, using the length property of an array, let us now write a program to input and display an array.
public class Main {
public static void main(String[] args) {
Scanner scn = new Scanner(System.in);
int n = scn.nextInt();
int[] arr = new int[n];
for(int i=0;i<n;i++) {
arr[i] = scn.nextInt();
}
for(int i=0;i<n;i++) {
System.out.print(arr[i] + " ");
}
}
}
So, let us now also learn something about 2-D arrays.
2-D Arrays in Java
A 2-Dimensional array in Java is usually used to represent a matrix. The comparison between a matrix in Mathematics and a 2-D array is shown below.
So, an array has all the indices starting from 0 and hence it differs from a matrix a little bit. Let us understand the 2-D array memory mapping.
2-D Array Declaration (With Memory Mapping)
The syntax to declare a 2-D array is shown below.
public class Main {
public static void main(String[] args) {
int[][] arr;
}
}
2-D Arrays Initialization (With Memory Mapping)
The syntax to initialise a 2-D array is shown below.
public class Main {
public static void main(String[] args) {
int[][] arr;
arr = new int[3][4];
}
}
This is what happens in the memory when we declare and initialise an array.
So, an array of references is created and it stores the address to the 1-d arrays. The reference variable arr stores the base address of the reference array.
2-D Arrays Direct Access
We can directly access any value in a 2-D Array. Consider the following program shown below.
public class Main {
public static void main(String[] args) {
Scanner scn = new Scanner(System.in);
int[][] arr;
arr = new int[3][4];
for(int i=0;i<arr.length;i++) {
for(int j=0;j<arr[0].length;j++) {
arr[i][j] = scn.nextInt();
}
}
System.out.println(arr[2][1]);
}
}
The time complexity for directly accessing a value in a 2-D array is O(1) i.e. constant.
2-D Arrays Traversal
The length property can be used in the 2-D arrays also. Consider the following 2-D array
Here, arr.length gives us the number of rows and arr[0].length gives us the number of elements in the array present at arr[0] i.e. the number of columns in the 0th row
public class Main {
public static void main(String[] args) {
Scanner scn = new Scanner(System.in);
int[][] arr;
arr = new int[3][4];
for(int i=0;i<arr.length;i++) {
for(int j=0;j<arr[0].length;j++) {
arr[i][j] = scn.nextInt();
}
}
for(int i=0;i<arr.length;i++) {
for(int j=0;j<arr[0].length;j++) {
System.out.print(arr[i][j] + " ");
}
System.out.println();
}
}
}
Let us now introduce you to the next data structure i.e. Linked List.
Test your data structure skills by taking this Data Structures in Java Mock Test designed by experienced mentors at PrepBytes.
Linked List in Java
A linked list is another linear data structure. The fact that makes it different from an array is that the elements in a linked list are not contiguous in memory allocation.
This means that they can be present in any order in the actual memory. This is shown in the image given below.
The first node of a linked list is called the head of the linked list.
Direct access:
Direct access to values is not possible on Linked List. We have to traverse the list to get the ith value.
The basic unit of the structure of the linked list shown in the above diagram is called a Node. A node of a linked list contains its data, and a pointer or a reference to the next node.
Creation of Linked List in Java.
A linked list is an inbuilt data structure provided by Java. So, we can use the inbuilt linked list or we may create our own linked list. Here, we will learn how to use the inbuilt Linked List data structure of Java.
A linked list is created as shown below in the program.
public class Main {
public static void main(String[] args) {
LinkedList<Integer> list = new LinkedList<>();
}
}
Doing this creates an empty linked list i.e the head of the linked list will be null and the reference variable list in the program will also have null stored in it.
Add Last in Linked List
This method adds the element to the end of the linked list. So, let us see how we can add an element to the last of the linked list and create our Linked List using it.
public class Main {
public static void main(String[] args) {
LinkedList<Integer> list = new LinkedList<>();
list.addLast(1);
list.addLast(2);
list.addLast(3);
list.addLast(4);
System.out.println(list);
}
}
The image below shows how the linked list grew in the above code.
The time complexity of adding an element to the last of the linked list is O(N).
Add First
The add first operation adds an element to the start of the linked list.
For instance, consider the following program.
public class Main {
public static void main(String[] args) {
LinkedList<Integer> list = new LinkedList<>();
list.addFirst(4);
list.addFirst(3);
list.addFirst(2);
list.addFirst(1);
System.out.println(list);
}
}
So, the linked list grows as follows.
The time complexity of this method is O(1).
Add(), Get() and Size()
The following program shows the syntax of using the methods add(), get(), and size() on the linked list.
public class Main {
public static void main(String[] args) {
LinkedList<Integer> list = new LinkedList<>();
list.addFirst(4);
list.addFirst(3);
list.addFirst(2);
list.addFirst(1);
System.out.println("The size of the Linked List is " + list.size());
System.out.println("The element present at index 0 is " + list.get(0));
list.add(0,10);
System.out.print(list);
}
}
- add(): This method adds an element to a particular index in the linked list. The index values are the same as that of the array i.e. from 0 to size -1. So, the time complexity of this method is O(N) as in the worst case, we might have to add it at the end of the linked list.
- get(): This method is used to get the value at the ith index in the linked list. The time complexity is O(N).
- size(): This method returns the number of nodes in the linked list. The time complexity of the size() method is O(1).
So, with this, we have got a basic idea of the linked list data structure. Let us now learn about the Stack data structure.
Stack in Java
Stack is also a linear data structure that has a LIFO behaviour. LIFO stands for Last in First out. This means that the last inserted element will be removed first from the stack.
push(): So, inserting an element into the stack is called a push() operation. It is an O(1) operation as we just have to insert an element at the top of the stack.
pop(): Removing an element from the stack is called a pop() operation. So, if we pop from the above stack, the topmost element of the stack gets removed. The time complexity is O(1).
Here, we can see the LIFO order being maintained.
peek(): This element returns the topmost element of the stack. So, at this moment, we will get 4 if we use the peek() method. The time complexity of peek() is also O(1).
size(): This method returns the number of elements in the stack. Its time complexity is O(1).
We tried to discuss Data Structures in Java in this article. We hope this article gives you a better understanding of the basics of Data Structures in Java. Prepbytes also provides a good collection of Foundation Courses that can help you enhance your coding skills. Want to make sure you ace the interview in one go? Join our Placement Program that will help you get prepared and land your dream job at MNCs. Mentors of Prepbytes are highly experienced and can provide you with basic, in-depth subject knowledge for better understanding.