Arrays: A very basic and important data structure

preface

Array is a very basic and important data structure. Many complex data structures are implemented based on array. In-depth understanding of data storage principles and characteristics is conducive to our actual development work, give full play to the advantages of data.

What is an array

An Array is a linear table data structure. It uses a set of contiguous memory space to store a set of data of the same type.

By adding a black description to the above definition, we can find several characteristics of arrays, namely: linear table, contiguous memory space, the same type of data. As shown below:

Arrays have very efficient “random access” because of their contiguous memory space, but also because of the need to maintain this contiguous memory space, the array is very inefficient in deleting or inserting operations. Because arrays that maintain continuity necessarily involve moving a lot of data around, this can be very time consuming.

Consider: Here you might wonder: What is contiguous memory space?

First, let’s talk about 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.

However, each element of the data is stored in a small memory cell, and the elements are closely arranged, neither to disrupt the order of the elements, nor to skip a memory cell for storage.

Random access to an array

An array of random access is a formula for addressing, ask we mentioned in the array is used on a set of contiguous memory space to store the data elements, however, each unit has its own memory address (is through this address to access the data in the inside of the computer), adding in each memory cell size is the same, so it is easy to get a formula, as shown below:

a[i]_address=base_address+i*data_type_size
Copy the code

To explain the above formula, data_type_size represents the size of each element in the array, base_address represents the beginning address of the memory block, and I represents the array subscript.

Basic operations on arrays

Before we begin, let’s create an array class that mimics the operations associated with array manipulation. The code is as follows:

public class MyArray {

    private int[] array;
    // Array size
    private int size;
     
    public MyArray(int capacity) {
        this.size = 0;
        this.array = new int[capacity]; }}Copy the code

1. Read elements

We know that arrays are stored consecutively in memory, so we know from the above addressing formula that we can quickly locate the corresponding elements according to the array subscript I.

For a simple example, the code is as follows:

int[] array={1.2.3.4.5.6};
System.out.println(array[1]); // The output is 2 because the index of the array starts at 0.
Copy the code

2. Update elements

We can quickly find the element based on the index of the array. In the same way, we can quickly update elements according to array subscript I. There are two processes involved in this process. The first is to find the data element A corresponding to array subscript I, and then assign the new data element B to A to complete the update.

For a simple example, the code is as follows:

int[] array={1.2.3.4.5.6};
System.out.println(array[1]);  // Output is 2

// Update the array element with subscript 1
array[1] =22;
System.out.println(array[1]); // The output is 22
Copy the code

3. Insert elements

Insert elements are slightly more complex than read and update operations, and can be divided into the following two cases:

Tail-insert: First, let’s look at tail-insert. This case is very simple, adding a new element to the end of the array, which has no effect on the original array, and the time complexity is 0(1). As shown below:

Intermediate insertion: Inserting elements in the middle of the array affects the elements after the insertion position, which means that the data needs to be moved one position back. As shown below:

The code inserted in the middle is as follows:

/** * insert element *@paramIndex Position to be inserted *@paramElement The element to be inserted */
public void insert(int index,int element){
    if(index<0 || index>size){
       throw new IndexOutOfBoundsException("Over array size! Insert failed!");
     }
    // Move the element one bit to the right from left to right
    for (int i=size-1 ; i>index ; i--){
       array[i+1]=array[i];
    }
    // The index position is already empty and can be put into the element
    array[index]=element;
    // Number of elements in array +1
    size++;
}
Copy the code

3.1 Array Expansion

Since the size of the array is set at creation time, it is impossible to insert elements if the array is full. This is the time to consider the problem of array expansion, so how to achieve expansion?

So we could do this, let’s say we have array A, and array A is full, and we create array B that’s twice as long as array A, and then we put all the elements of array A into array B, and we’re done expanding the array.

The code for array expansion is as follows:

/** * double the size of the original array */
public void resize(a){
 int[] newArray=new int[array.length*2];
 System.arraycopy(array,0,newArray,0,array.length);
 array=newArray;
}
Copy the code

4. Delete elements

Deleting an element is similar to inserting an element. If we delete the KTH position, it also involves moving the data for the sake of memory continuity. As shown below:

The code for deleting elements is as follows:

    /** * removes the element ** based on the array subscript@paramIndex array subscript *@return* /
    public int delete(int index) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("Array capacity has been exceeded! Insert failed!");
        }
        int deleteElement = array[index];
        // Move the element one bit to the left from left to right
        for (int i = index; i < size - 1; i++) {
            array[i] = array[i + 1];
        }
        size--;
        return deleteElement;
    }
Copy the code

conclusion

An array uses a contiguous memory space to store a group of data of the same type. Its biggest advantage is that the array supports random access, because the array can access the corresponding elements quickly through the array subscript (addressing formula), and the time complexity is O(1).

The two operations of deleting and inserting elements in an array are relatively inefficient, because in order to maintain the continuity of data, the array will involve data moving, and the average time complexity is O(N).

Therefore, arrays are suitable for “read more and write less” scenarios.