Chapter 8:Arrays in Java: A Comprehensive Guide
Table of contents
- 1) Introduction to Arrays
- Storing Marks Without Arrays
- Using Arrays to Store Marks
- Formal Definition of an Array
- Contiguous Memory Visualization
- 2) Operations on Arrays
- 1. Creating an Array
- Example:
- What the new Keyword Does:
- 2. Input in an Array
- Example of Input:
- 3. Output in an Array
- Example of Output:
- 4. Updating an Array
- Example of Update:
- 5. Calculating Percentage
- Example:
- 6. Finding the Length of an Array
- Example:
- Full Example Code:
- Summary:
- 3) Passing Arrays as Arguments
- Key Concepts:
- Example: Verifying Pass-by-Reference with Arrays
- Explanation:
- Important Points:
- 4) Linear Search in Arrays
- Linear Search Explanation
- Example: Linear Search in Arrays
- Java Program for Linear Search
- Homework Example: Menu Search
- Homework Program: Linear Search in a Menu
- Time Complexity of Linear Search
- Conclusion
- 5) Binary Search
1) Introduction to Arrays
In programming, arrays serve as a fundamental data structure that stores elements of the same type in contiguous memory locations. Let’s begin with an example to highlight the problem arrays solve:
Storing Marks Without Arrays
Suppose you want to store the marks of three subjects for a student: Physics, Chemistry, and Maths. The simplest way to do this is by creating individual integer variables for each subject:
int phy = 78;
int chem = 81;
int math = 90;
This approach is manageable for a small number of subjects, but imagine if you had to store the marks for 60 subjects across different semesters in a college course. Creating 60 separate variables would be highly inefficient and cumbersome to manage.
Using Arrays to Store Marks
Arrays solve this problem by allowing us to store multiple values in a single data structure, which can be accessed using an index. For instance, to store the marks of 60 subjects, we can create an array of integers:
int marks[] = new int[60];
In this array:
marks[0]
refers to the marks of the first subject,marks[1]
refers to the marks of the second subject, and so on.
Formal Definition of an Array
An array is a collection of elements of the same type, stored in contiguous memory locations. You can visualize it as a list where each element is indexed starting from 0
(0-based indexing).
Arrays cannot store elements of different types. For example, an array cannot contain the following elements:
{ "Apple", "Rohit", 4.9, 8 }
Contiguous Memory Visualization
Imagine you have an integer array storing the marks of three subjects. These marks are stored in contiguous memory locations as shown below:
Address | Value | Description |
1000 | 78 | marks[0] (Physics) |
1004 | 81 | marks[1] (Chemistry) |
1008 | 90 | marks[2] (Maths) |
Each integer takes 4 bytes of memory, and hence the next element is stored 4 bytes apart from the previous one.
Similarly, a char
array can be visualized as:
Address | Value | Description |
2000 | 'A' | charArray[0] |
2001 | 'B' | charArray[1] |
2002 | 'C' | charArray[2] |
Each character takes 1 byte of memory, so they are stored contiguously.
2) Operations on Arrays
Arrays in Java are one of the fundamental data structures, which allow you to store multiple elements of the same type in a contiguous memory location. Let's break down the different operations you can perform on arrays: Create, Input, Output, and Update.
1. Creating an Array
To create an array in Java, you need to specify the data type, the array name, and the size (for new arrays). Arrays are static in size, meaning once you define the size, it cannot be changed.
Syntax:
dataType arrName[] = new dataType[size];
Here:
dataType
is the type of elements (e.g.,int
,String
).arrName
is the name of the array.new
keyword allocates memory for the array.size
is the number of elements the array will hold.
Example:
int marks[] = new int[50]; // Creates an empty array of size 50.
int num[] = {1, 2, 3}; // Creates an array with initial values.
int moreNum[] = {4, 5, 6}; // Another example of initializing an array.
String fruits[] = {"Apple", "Mango", "Orange"}; // Array of Strings.
What the new
Keyword Does:
- The
new
keyword in Java is used to dynamically allocate memory for arrays or objects. For an array, it reserves space in memory based on the size you provide.
2. Input in an Array
You can input values into the array using indexing (where the index starts at 0). You can either hard-code the values or take input from the user using a Scanner
object.
Example of Input:
import java.util.Scanner;
public class InputArray {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int arr[] = new int[3]; // Array of size 3 (for 3 subjects)
// Taking input for each subject
System.out.print("Enter marks for Physics: ");
arr[0] = sc.nextInt(); // Physics
System.out.print("Enter marks for Chemistry: ");
arr[1] = sc.nextInt(); // Chemistry
System.out.print("Enter marks for Maths: ");
arr[2] = sc.nextInt(); // Maths
}
}
3. Output in an Array
You can output the values of an array by accessing each element through its index.
Example of Output:
// Output for each subject's marks
System.out.println("Physics: " + arr[0]);
System.out.println("Chemistry: " + arr[1]);
System.out.println("Maths: " + arr[2]);
4. Updating an Array
You can update the values of an array by directly accessing an index and assigning a new value.
Example of Update:
// Updating the Physics marks
arr[0] = 67; // Updating Physics marks to 67
System.out.println("Updated Physics marks: " + arr[0]);
5. Calculating Percentage
To calculate the average or percentage of marks (or any similar calculation), you can use the elements in the array and apply arithmetic operations.
Example:
// Calculating the percentage (assuming 3 subjects)
int percentage = (arr[0] + arr[1] + arr[2]) / 3;
System.out.println("Percentage: " + percentage);
6. Finding the Length of an Array
You can use the length
property of an array to get the number of elements it holds.
Example:
// Getting the length of the array
System.out.println("Length of the array: " + arr.length);
Full Example Code:
import java.util.Scanner;
public class ArrayOperations {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int arr[] = new int[3]; // Array of size 3 for marks
// Input values
System.out.print("Enter marks for Physics: ");
arr[0] = sc.nextInt(); // Physics
System.out.print("Enter marks for Chemistry: ");
arr[1] = sc.nextInt(); // Chemistry
System.out.print("Enter marks for Maths: ");
arr[2] = sc.nextInt(); // Maths
// Output values
System.out.println("Physics: " + arr[0]);
System.out.println("Chemistry: " + arr[1]);
System.out.println("Maths: " + arr[2]);
// Update Physics marks
arr[0] = 67;
System.out.println("Updated Physics marks: " + arr[0]);
// Calculate percentage
int percentage = (arr[0] + arr[1] + arr[2]) / 3;
System.out.println("Percentage: " + percentage);
// Get the length of the array
System.out.println("Length of the array: " + arr.length);
}
}
Summary:
Create: Use the
new
keyword to create arrays.Input: Take values from the user or assign them directly using indexing.
Output: Access and print array values using the array's index.
Update: Change the values by directly assigning new values to the array's elements.
Array Length: Use the
length
property to get the size of the array.
This allows you to efficiently work with arrays in Java, enabling you to store and manipulate multiple values with ease.
3) Passing Arrays as Arguments
In Java, when you pass an array to a function, it behaves as pass-by-reference. This means that any changes made to the array inside the function will reflect in the original array, unlike primitive data types which follow pass-by-value, meaning changes made to the parameter inside the function do not affect the original value.
Key Concepts:
Pass by Value (for primitive types):
- If you pass a primitive type (like
int
,char
, etc.) to a function, a copy of that variable is passed. Any changes made inside the function do not affect the original variable in the main function.
- If you pass a primitive type (like
Pass by Reference (for arrays/objects):
- Arrays are passed by reference, meaning the reference to the original array is passed, so any changes made to the array inside the function will reflect in the original array.
Example: Verifying Pass-by-Reference with Arrays
In this example, the update
function takes an array of integers and increments each element by 1. Since arrays are passed by reference in Java, the changes made to the array inside the function will affect the array in the main function.
public class Update {
public static void update(int marks[]) {
// Increment each element of the array by 1
for (int i = 0; i < marks.length; i++) {
marks[i] = marks[i] + 1;
}
}
public static void main(String[] args) {
int marks[] = {3, 5, 6, 7}; // Original array
// Calling the update function, which modifies the array
update(marks);
// Printing the updated array
for (int i = 0; i < marks.length; i++) {
System.out.print(marks[i] + " "); // Output: 4 6 7 8
}
System.out.println(); // To add a new line
}
}
Explanation:
Initial Array:
{3, 5, 6, 7}
The
update()
function adds1
to each element, so the array becomes{4, 6, 7, 8}
.When we print the array in the
main()
function, the changes reflect because arrays are passed by reference in Java.
Important Points:
Arrays in Java are treated as objects, so the reference to the original array is passed to the function.
If this were a primitive type like
int
, the changes inside the function wouldn’t reflect in the original variable in themain()
function.
This behavior of arrays makes them powerful when you want to modify data in a method and have those changes reflected in the calling environment.
4) Linear Search in Arrays
Linear Search Explanation
Linear search is one of the simplest searching techniques used to find an element in an array or a list. You compare each element of the array with the key (the element you are searching for) until you find a match or reach the end of the array. In real life, you can think of it as searching for an item (like a samosa) in your college canteen menu by scanning through every option one by one.
Example: Linear Search in Arrays
Given the task of finding the index of an element in an array, here’s a quick overview using the key 10
in the array:
Array: 2 4 6 8 10 12 14 16
We’ll scan through the array from the first element to the last, checking each index:
Check
2
at index0
Check
4
at index1
Check
6
at index2
Check
8
at index3
Check
10
at index4
: Found the key! We return index4
as the output.
Java Program for Linear Search
public class LinearSearch {
public static int linearSearch(int num[], int key) {
for (int i = 0; i < num.length; i++) {
if (num[i] == key) { // If the element matches the key
return i; // Return the index
}
}
return -1; // If key not found, return -1
}
public static void main(String[] args) {
int num[] = {2, 4, 6, 8, 10, 12, 14, 16}; // Example array
int key = 10; // Element to search for
int index = linearSearch(num, key);
if (index == -1) {
System.out.println("Key Not found");
} else {
System.out.println("Key is at index: " + index);
}
}
}
Output:
Key is at index: 4
Homework Example: Menu Search
Now let's apply the same idea to searching through a menu. If you’re looking for an item like "Idli" from the menu, we scan through the entire list to find its position.
Homework Program: Linear Search in a Menu
public class HW {
public static int FindKey(String[] menu, String key) {
for (int i = 0; i < menu.length; i++) {
if (menu[i].equals(key)) { // Using `equals()` for string comparison
return i;
}
}
return -1; // If the key is not found
}
public static void main(String[] args) {
String[] menu = {"Samosa", "Dosa", "Idli", "Kachori", "Menduvada"}; // Menu items
String key = "Idli"; // Item to search for
int index = FindKey(menu, key);
if (index == -1) {
System.out.println("Key not found");
} else {
System.out.println("Key found at index: " + index);
}
}
}
Time Complexity of Linear Search
When discussing the efficiency of algorithms, we often talk about time complexity, which measures the time taken by an algorithm as a function of input size.
Time Complexity of Linear Search:
In the best case scenario (when the key is at the first position), the time complexity is
O(1)
, meaning the search finishes in constant time.In the worst case scenario (when the key is not present or is at the last position), the time complexity is
O(n)
, wheren
is the size of the array. This is because the algorithm must check every element in the array before concluding.
Thus, linear search has a time complexity of O(n)
in the worst case, where n
is the number of elements in the array.
Space Complexity:
- Linear search uses a constant amount of extra space, so the space complexity is
O(1)
.
Conclusion
In this case, both the number-based linear search and the menu-based search operate similarly. The only difference is the data type being searched (integers vs. strings). The time complexity remains O(n)
for both, and the programs perform well on small datasets. However, for larger datasets, more efficient search algorithms (like binary search) would be preferable.
5) Binary Search
Binary search is an efficient search algorithm used on sorted arrays. Instead of checking each element one by one, binary search works by repeatedly dividing the array in half, based on whether the target element is larger or smaller than the middle element.
Further Reading and Resources
If you found this post insightful, you might be interested in exploring more detailed topics in my ongoing series:
Full Stack Java Development: A comprehensive guide to becoming a full stack Java developer, covering everything from the basics to advanced concepts.
DSA in Java: Dive into data structures and algorithms in Java with detailed explanations and examples.
HashMap Implementation Explained: Understand the underlying mechanics of Java’s HashMap.
Inner Classes and Interfaces in Java: Explore the intricacies of inner classes and interfaces.
Connect with Me
Stay updated with my latest posts and projects by following me on social media:
LinkedIn: Connect with me for professional updates and insights.
GitHub: Explore my repositories and contributions to various projects.
LeetCode: Check out my coding practice and challenges.
Your feedback and engagement are invaluable. Feel free to reach out with questions, comments, or suggestions. Happy coding!
Rohit Gawande
Full Stack Java Developer | Blogger | Coding Enthusiast