What is an array

Before we get to JS arrays, let’s review the definition of arrays in data structures:

In computer science, an array data structure, or array for short, is a data structure composed of a collection of elements of the same type, allocated a contiguous chunk of memory for storage. The index of an element can be used to calculate the corresponding storage address of the element. Quote from Wikipedia

According to the definition of arrays given by Wikipedia, arrays satisfy:

  1. All elements in an array are elements of the same type (elements of the same type require the same amount of storage space, so we can easily use the element index to calculate the location of the element);
  2. Allocate a contiguous block of memory storage (fixed length, continuous).

To understand how arrays are stored, we need to know that the data in memory is made up of many transistors, and each transistor can only store 0 or 1, which is the smallest unit of data (bit). Take an integer array as an example. The storage form of an array is as follows:

Each element in the array has its own index, except that the index starts at 0 and goes all the way to array length -1; Another feature of arrays is that they are sequentially stored in memory, which makes logical sequential tables a good choice.

Sequential storage of arrays in memory: Memory is made up of contiguous memory cells, each with its own address. Some of these memory units are occupied by other data, and some are idle; Each element in the array is stored in a small memory cell, and the elements are arranged so closely that they cannot be jumbled or skipped.

As shown in figure

  • Blue: Used memory space
  • Orange: indicates the memory space allocated by the current array
  • Gray: indicates free memory space

Different types of arrays have different numbers of bytes per element.

Basic operations on arrays

Read elements

JavaScript accesses the values of the elements specified in an array using an array with subscripts starting at 0. The ith element is subscript I -1, as shown below.

Where arR [0] corresponds to 1, ARR [1] corresponds to 5, ARR [2] corresponds to 2,…

When the program needs to read data in memory, it will provide the memory address of the data to be read. For an array, the variable stores the memory address of the first element of the array in memory. When we need to access the ith element of an array, the storage of the array is contiguous and of the same type (i.e., each element occupies a fixed amount of memory).

The formula can be used to directly calculate the memory address of the element with subscript I to access its value in memory

Memory address of an element with subscript I = first address of array + (length of a single element * I)

For example, the array ARR allocates memory space starting at position 5. Each element occupies one space, so its initial address is 4 (counting from 0). When you need to access an element of the array with subscript 5, follow the formula

4 plus 1 times 5 is 9

We can have memory go directly to the memory space at address 9 (the 10th space) and get a value of 3

So the value of arr[5] is 3.

let arr = [1.5.2.4.4.3.2.14]

console.log(arr[5]) / / 3
Copy the code

Update the element

The values of array elements are updated in the same way that they are accessed, by calculating the memory region to be updated and then modifying it.

In JavaScript, the value of a specified position in an array is modified by array [subscript] = value.

let arr = [1.5.2.4.4.3.2.14]

arr[5] = 100
console.log(arr[5]) / / 100
Copy the code

Insert elements

The actual number of elements in an array can be smaller than the length of the array, as in the following case:

let arr = new Array(8); // Define an array of length 8 that allocates space for 8 elements in memory

// Initialize: assigns values to the first six elements of the array
arr[0] = 1;
arr[1] = 5;
arr[2] = 2;
arr[3] = 4;
arr[4] = 4;
arr[5] = 3;

arr.size = 5 // Represents the actual used length of the current array

Copy the code

Therefore, there are three cases of inserting an array element:

  • Insert the tail
  • The middle insert
  • Out-of-range insertion

Insert the tail

Tail insert, the simplest case, simply places the inserted element in a free position at the end of the array, equivalent to updating the element

If you want to insert a 1 at the end of the array, you can simply assign to the last item of the current array, as shown below:

arr[6] = 1 // Assign to the sixth element

console.log(arr) // [ 1, 5, 2, 4, 4, 3, 1, <1 empty item> ]
Copy the code

The middle insert

Each element of the array has a fixed index, so you have to move the insertion position and the element after it back to make room, and then put the element to be inserted into the corresponding array position.

If you want to insert a 1 after the third position in the array, you want to move the third position and all subsequent elements back one bit, leaving a free position before you modify it. The situation is as follows:

Arr [3], ARR [4], ARR [5] move backwards, then modify ARR [3] = 1

Code implementation:

// Insert an item value into the array at index
function arrayAddItem(arr, index, item) {
    // Move all elements after item one bit back
    for(let i = arr.size; i > index; i--){
        / / move
        arr[i] = arr[i-1]}// Assign the value to be inserted to the specified position
    arr[index] = item
    arr.size++
    
    return arr
}

arr = arrayAddItem(arr, 3.1)
console.log(arr); // [ 1, 5, 2, 1, 4, 4, 3, <1 empty item> ]
Copy the code

Out-of-range insertion

Since the length of an array is immutable, the amount of memory allocated to an array is also fixed. In the previous cases, the number of elements in the array is less than the length of the array. So how do you insert data when the number of elements in the array is equal to the length?

For example:

  • Orange: Memory allocated by the array
  • Blue: Memory space that is being used by other variables
  • Gray: free memory space

When we insert an element, the last element cannot be moved back or we will run out of memory. In this case, you need to create a new memory space with enough space, copy the values in the original space to the new space, and then insert the values.

Here the new array is only one bit larger, but the actual size may be more than one and a half times larger, or two times larger, etc. This can effectively reduce frequent capacity expansion operations (reallocate memory)

let arr = [1.2.3.4.5]
arr.size = 5 // The current array is length

// Insert an item value into the array at index
function arrayAddItem(arr, index, item) {
    if(arr[arr.length-1]) {// The number of elements in the array is already full
        arr = expandArray(arr)
    }

    // Move all elements after item one bit back
    for(let i = arr.size; i > index; i--){
        / / move
        arr[i] = arr[i-1]}// Assign the value to be inserted to the specified position
    arr[index] = item
    arr.size++

    return arr
}

// Double the size of the array
function expandArray(arr){
    // Create an array twice as long
    let newArray = new Array(arr.size * 2)

    // Copy the original array into the new array
    for (let i = 0; i < arr.size; i++) {
        newArray[i] = arr[i]
    }
    newArray.size = arr.size

    return newArray
}


arr = arrayAddItem(arr, 3.1)
console.log(arr); [ 1.2.3.1.4.5.<4 empty items>]
Copy the code

Remove elements

If the deleted element is in the middle of the array, all subsequent elements move forward one bit:

function arrayRemoveItem(arr, index){
    for (let i = index; i < arr.size-1; i++) {
        // The next term moves forward
        arr[i] = arr[i+1]}// The current algorithm is the last one
    delete arr[arr.size-1]
    arr.size--
    return arr
}
Copy the code

Delete operation, which involves only element movement, order n time.

If there is no order required for the elements of the array, there is another trick to deleting:

As shown in the figure below, you need to delete element 2 in the array. You can copy the last element to its location and then delete the last element

As a result, there is no need to do a lot of element movement and the time complexity is reduced to O(1).

function arrayRemoveItem(arr, index){
    // The last item is moved to the deleted position
    arr[index] = arr[size-1]
    // Remove the last item
    delete arr[size-1]
    size--
    return arr
}
Copy the code

The advantages and disadvantages of arrays

Advantages: Arrays have very efficient random access, as long as the subscript is given, you can find the corresponding element in constant time. An efficient algorithm for finding elements is called binary lookup, which takes advantage of arrays.

Disadvantages: The disadvantages of arrays are in inserting and deleting elements. Since array elements are stored in contiguous and close memory, inserting and deleting elements will cause a large number of elements to be moved, affecting efficiency.

Bottom line: Arrays are best suited for scenarios with lots of reads and few writes!

The array in JS does not completely conform to the definition of the array in the data structure. The array in JS can be different data types or non-linear sequential. How is memory allocated for v8-JS arrays