DEV Community

Cover image for Data Structures - Part 1: Everything You Need to Know About Arrays
Burak Boduroğlu
Burak Boduroğlu

Posted on

Data Structures - Part 1: Everything You Need to Know About Arrays

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];
Enter fullscreen mode Exit fullscreen mode
int[] arr = {2, 3, 4, 5, 9};
Enter fullscreen mode Exit fullscreen mode

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];
Enter fullscreen mode Exit fullscreen mode

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};
Enter fullscreen mode Exit fullscreen mode

Array

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);
Enter fullscreen mode Exit fullscreen mode
// 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];
}
Enter fullscreen mode Exit fullscreen mode

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);
Enter fullscreen mode Exit fullscreen mode
// 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];
}
Enter fullscreen mode Exit fullscreen mode

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]);
}
Enter fullscreen mode Exit fullscreen mode
int[] arr = {1, 2, 3, 4, 5};
for (int i = 0; i < arr.length; i++) {
    System.out.println(arr[i]);
}
Enter fullscreen mode Exit fullscreen mode

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.

Merge Sort

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));
Enter fullscreen mode Exit fullscreen mode
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];
        }
    }
}
Enter fullscreen mode Exit fullscreen mode

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.

Quick Sort

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));
Enter fullscreen mode Exit fullscreen mode
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;
    }
}
Enter fullscreen mode Exit fullscreen mode

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));
Enter fullscreen mode Exit fullscreen mode
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;
    }
}
Enter fullscreen mode Exit fullscreen mode

References

Thanks for Reading :)

Follow me on GitHub for more.

My Other Interested Blog Posts

Top comments (1)

Collapse
 
prsaya profile image
Prasad Saya • Edited

Disadvantages
The size of the arrays is fixed: ...

This applies only to the Java programming language arrays.