This blog post part 1 of a series of blog posts on data structures. In this blog post, we will be covering the following data structures:
- What is an Array?
- How to declare an array?
(With JavaScript and Java) - Advantages and Disadvantages of Arrays
- Advantages
- Disadvantages
- Time Complexities of Array Operations
- Basic Process of Array Operations
(With JavaScript and Java)- Add
- Remove
- Sorting of Arrays
(With JavaScript and Java)- Merge Sort
- Quick Sort
- Searching of Arrays
(With JavaScript and Java)- Binary Search
Array
What is an Array?
An array is a collection of items stored at contiguous memory locations. The idea is to store multiple items of the same type together. This makes it easier to calculate the position of each element by simply adding an offset to a base value,
For simplicity, we can think of an array a fleet of stairs where on each step is placed a value (let’s say one of your friends). Here, you can identify the location of any of your friends by simply knowing the count of the step they are on.
Index of an array starts from 0 to (size of array – 1). For example, in the array given below, the index of the first element 2 is 0. The index of the last element 9 is 4.
let arr = [2, 3, 4, 5, 9];
int[] arr = {2, 3, 4, 5, 9};
How to declare an array?
In JavaScript, we can declare an array in the following ways:
// Method 1
let arr = new Array();
// Method 2
let arr = [];
// Method 3
let arr = [1, 2, 3, 4, 5];
In Java, we can declare an array in the following ways:
// Method 1
int[] arr = new int[5];
// Method 2
int[] arr = {1, 2, 3, 4, 5};
Source: GeeksforGeeks
Advantages and Disadvantages of Arrays
Advantages
- Arrays are easy to implement.
- Arrays provide better cache locality that can make a pretty big difference in performance.
- Arrays offer O(1) search if we know the index.
Disadvantages
- The size of the arrays is fixed: So we must know the upper limit on the number of elements in advance. Also, generally, the allocated memory is equal to the upper limit irrespective of the usage.
- Inserting a new element in an array of elements is expensive because the room has to be created for the new elements and to create room existing elements have to shift.
- Deleting an element in an array of elements is expensive because the room has to be created for the new elements and to create room existing elements have to shift.
- Searching in an array is expensive as we have to go through all the elements to find the element we are looking for.
Time Complexities of Array Operations
| Operation | Time Complexity |
|---|---|
| Access | O(1) |
| Search | O(n) |
| Insertion | O(n) |
| Appending | O(1) |
| Deletion | O(n) |
Basic Process of Array Operations
Add
- Add an element at the end: O(1)
- Add an element at the beginning: O(n)
- Add an element in the middle: O(n)
// Add an element at the end
let arr = [1, 2, 3, 4, 5];
arr.push(6);
// Add an element at the beginning
let arr = [1, 2, 3, 4, 5];
arr.unshift(0);
// Add an element in the middle
let arr = [1, 2, 3, 4, 5];
arr.splice(2, 0, 2.5);
// Add an element at the end
int[] arr = {1, 2, 3, 4, 5};
int[] newArr = new int[arr.length + 1];
for (int i = 0; i < arr.length; i++) {
newArr[i] = arr[i];
}
newArr[arr.length] = 6;
// Add an element at the beginning
int[] arr = {1, 2, 3, 4, 5};
int[] newArr = new int[arr.length + 1];
newArr[0] = 0;
for (int i = 0; i < arr.length; i++) {
newArr[i + 1] = arr[i];
}
// Add an element in the middle
int[] arr = {1, 2, 3, 4, 5};
int[] newArr = new int[arr.length + 1];
for (int i = 0; i < 2; i++) {
newArr[i] = arr[i];
}
newArr[2] = 2.5;
for (int i = 2; i < arr.length; i++) {
newArr[i + 1] = arr[i];
}
Remove
- Remove an element at the end: O(1)
- Remove an element at the beginning: O(n)
- Remove an element in the middle: O(n)
// Remove an element at the end
let arr = [1, 2, 3, 4, 5];
arr.pop();
// Remove an element at the beginning
let arr = [1, 2, 3, 4, 5];
arr.shift();
// Remove an element in the middle
let arr = [1, 2, 3, 4, 5];
arr.splice(2, 1);
// Remove an element at the end
int[] arr = {1, 2, 3, 4, 5};
int[] newArr = new int[arr.length - 1];
for (int i = 0; i < newArr.length; i++) {
newArr[i] = arr[i];
}
// Remove an element at the beginning
int[] arr = {1, 2, 3, 4, 5};
int[] newArr = new int[arr.length - 1];
for (int i = 0; i < newArr.length; i++) {
newArr[i] = arr[i + 1];
}
// Remove an element in the middle
int[] arr = {1, 2, 3, 4, 5};
int[] newArr = new int[arr.length - 1];
for (int i = 0; i < 2; i++) {
newArr[i] = arr[i];
}
for (int i = 2; i < newArr.length; i++) {
newArr[i] = arr[i + 1];
}
Traverse
- Traverse an array: O(n)
let arr = [1, 2, 3, 4, 5];
for (let i = 0; i < arr.length; i++) {
console.log(arr[i]);
}
int[] arr = {1, 2, 3, 4, 5};
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}
Sorting of Arrays
Merge Sort
- Time Complexity: O(n log n)
- Space Complexity: O(n)
- Merge sort is a divide and conquer algorithm that was invented by John von Neumann in 1945.
- Merge sort is a sorting technique based on divide and conquer technique.
- With worst-case time complexity being Ο(n log n), it is one of the most respected algorithms.
How is Merge Sort Algorithm Works?
Divide the unsorted list into n sublists, each containing 1 element (a list of 1 element is considered sorted). Repeatedly merge sublists to produce new sorted sublists until there is only 1 sublist remaining. This will be the sorted list.
Image Source: wikimedia
Merge Sort Algorithm Implementation
function mergeSort(arr) {
if (arr.length <= 1) {
return arr;
}
let mid = Math.floor(arr.length / 2);
let left = mergeSort(arr.slice(0, mid));
let right = mergeSort(arr.slice(mid));
return merge(left, right);
}
function merge(left, right) {
let result = [];
let i = 0;
let j = 0;
while (i < left.length && j < right.length) {
if (left[i] < right[j]) {
result.push(left[i]);
i++;
} else {
result.push(right[j]);
j++;
}
}
while (i < left.length) {
result.push(left[i]);
i++;
}
while (j < right.length) {
result.push(right[j]);
j++;
}
return result;
}
let arr = [5, 4, 3, 2, 1];
console.log(mergeSort(arr));
public class MergeSort {
public static void main(String[] args) {
int[] arr = {5, 4, 3, 2, 1};
mergeSort(arr, 0, arr.length - 1);
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
public static void mergeSort(int[] arr, int start, int end) {
if (start < end) {
int mid = (start + end) / 2;
mergeSort(arr, start, mid);
mergeSort(arr, mid + 1, end);
merge(arr, start, mid, end);
}
}
public static void merge(int[] arr, int start, int mid, int end) {
int[] temp = new int[end - start + 1];
int i = start;
int j = mid + 1;
int k = 0;
while (i <= mid && j <= end) {
if (arr[i] < arr[j]) {
temp[k] = arr[i];
i++;
} else {
temp[k] = arr[j];
j++;
}
k++;
}
while (i <= mid) {
temp[k] = arr[i];
i++;
k++;
}
while (j <= end) {
temp[k] = arr[j];
j++;
k++;
}
for (int l = start; l <= end; l++) {
arr[l] = temp[l - start];
}
}
}
Quick Sort
- Time Complexity: O(n log n)
- Space Complexity: O(log n)
- Quick sort is a highly efficient sorting algorithm and is based on partitioning of array of data into smaller arrays.
How is Quick Sort Algorithm Works?
Quick sort works like this:
- Select an element, called a pivot, from the array.
- Reorder the array so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.
- Recursively apply the above steps to the sub-array of elements with smaller values and separately to the sub-array of elements with greater values.
Image Source: tutorialspoint
Quick Sort Algorithm Implementation
function quickSort(arr) {
if (arr.length <= 1) {
return arr;
}
let pivot = arr[0];
let left = [];
let right = [];
for (let i = 1; i < arr.length; i++) {
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return quickSort(left).concat(pivot, quickSort(right));
}
let arr = [5, 4, 3, 2, 1];
console.log(quickSort(arr));
public class QuickSort {
public static void main(String[] args) {
int[] arr = {5, 4, 3, 2, 1};
quickSort(arr, 0, arr.length - 1);
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
public static void quickSort(int[] arr, int start, int end) {
if (start < end) {
int pivot = partition(arr, start, end);
quickSort(arr, start, pivot - 1);
quickSort(arr, pivot + 1, end);
}
}
public static int partition(int[] arr, int start, int end) {
int pivot = arr[end];
int i = start - 1;
for (int j = start; j < end; j++) {
if (arr[j] < pivot) {
i++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i + 1];
arr[i + 1] = arr[end];
arr[end] = temp;
return i + 1;
}
}
Searching of Arrays
Searching is the process of finding a particular value in a list of values. A search typically answers either True or False as to whether the value is present. On occasion it may be modified to return where the value is found.
Binary Search
- Time Complexity: O(log n)
- Space Complexity: O(1)
- Binary search is a fast search algorithm with run-time complexity of Ο(log n). This search algorithm works on the principle of divide and conquer. For this algorithm to work properly, the data collection should be in the sorted form.
How Binary Search Algorithm Works?
Binary search works like this:
- Binary search begins by comparing the middle element of the array with the target value.
- If the target value matches the middle element, its position in the array is returned.
- If the target value is less than or greater than the middle element, the search continues in the lower or upper half of the array respectively, eliminating the other half from consideration.
Binary Search Algorithm Implementation
function binarySearch(arr, target) {
let start = 0;
let end = arr.length - 1;
while (start <= end) {
let mid = Math.floor((start + end) / 2);
if (arr[mid] === target) {
return mid;
} else if (arr[mid] < target) {
start = mid + 1;
} else {
end = mid - 1;
}
}
return -1;
}
let arr = [1, 2, 3, 4, 5];
console.log(binarySearch(arr, 3));
public class BinarySearch {
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5};
System.out.println(binarySearch(arr, 3));
}
public static int binarySearch(int[] arr, int target) {
int start = 0;
int end = arr.length - 1;
while (start <= end) {
int mid = (start + end) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
start = mid + 1;
} else {
end = mid - 1;
}
}
return -1;
}
}
References
Thanks for Reading :)
Follow me on GitHub for more.
Top comments (1)
This applies only to the Java programming language arrays.