Today, I'll go on with the last one in detail and implement a sequence table in Java. The name is MyArray List, which is a bit casual. Last time, the implementation of sequential tables is implemented by using arrays, so we need a member array when we write sequential tables. But the array is fixed length, how to add or delete it? The idea of realization is as follows, which will be explained in detail later.

1. Define a variable size to represent the length of an array and take a reasonable initial value.

2, 1. First create an array of fixed length, size

3. Define a variable length to represent the length of MyArray List (note here, not the length of the array)

So how to do this? First, create the array when you create MyArrayList. At this point, the length of the array is size, while the length of MyArrayList is 0. In MyArray List, size and length are two different values. Size is the length of the actual array, and length is the length of the order table we tell others. Then the member variables of this class are as follows:

public class MyArrayList<T> {
    //Array for storing data
    private T[] data;
    //The length of the array
    private int size = 100;
    //Length of Sequence Table
    private int length = 0;

    /**
    *    Construction method
    */
    public MyArrayList(){
        //When creating MyArrayList, create an array
        data = (T[])new Object[size];
    }
｝

The above code is simple because generics are used to make the code generic. So let's implement a few other important methods, first add at the end of the team:

/**
* Insert data to the end
* @param value Inserted value
*/
public void add(T value){
    //If the length does not exceed size, add elements directly
    if(length < size){
        data[length] = value;
    }else{
        //The original array is not enough
        moreData();
        data[length] = value;
    }
    //Length increase
    length++;
}

When the length does not exceed size, you know, just add an element to the end of the array. However, if the size is larger than the size, the subscript will cross the boundary, which needs to be dealt with separately at this time. The custom moreData() method is used here, because it is also used to add data at a specified location later. Next, let's talk about adding data to a given location.

/**
* Specifies subscript insertion
* @param value Inserted value
* @param index Inserted Subscripts
*/
public void add(T value, int index){
    if(index >= size){
        System.out.println("Subscripts beyond bounds cannot be added");
    }else if(length + 1 > size){
        moreData();
        addDataByIndex(value, index);
    } else{
        addDataByIndex(value, index);
    }
}

The first step is to judge whether the array is beyond the bounds, and then to judge whether the array length is insufficient. Here's another custom method, addDataByIndex(), which is extracted because of duplication. Let's look at more Data () and addDataByIndex():

/**
* Call this method when the element group is not enough
*/
private void moreData(){
    //Remove the original data from the data array
    T[] temp = data.clone();
    //Create a longer array from scratch
    size += 50;
    data = (T[])new Object[size];
    //Copy back the data in temp and add new values
    for (int i = 0; i < temp.length; i++){
        data[i] = temp[i];
    }
}

Because the length of the array can not be changed, when the length is insufficient, only a new array can be created. But before you create it, you first record the original data of the array (temp array is used here), and then put the original data into the variable-length data array.

Next is the addDataByIndex() method:

/**
* Implementation of Adding Data by Subscription
* @param value Inserted value
* @param index Inserted Subscripts
*/
private void addDataByIndex(T value, int index){
    //Create an array to store the data after index
    T[] temp = (T[])new Object[length - index];
    for(int i = index, j = 0; i < length; i++, j++){
        temp[j] = data[i];
    }
    //insert data
    data[index] = value;
    //Complete the following data
    for(int i = index + 1, j = 0; i < length+1; i++, j++){
        data[i] = temp[j];
    }
    length++;
}

First save the data from index, then insert the data to be inserted into index, and then re-assign the data after index to the original. Actually, it's just moving backwards from the index elements.

The next step is to delete the data. In this case, I can simplify it without considering the size of size.

/**
* Delete the data at the end of the queue
*/
public void delete(){
    if(length > 0){
        length--;
        //Replicate data in an array
        T[] temp = data.clone();
        data = (T[])new Object[size];
        for(int i = 0; i < length; i++){
            data[i] = temp[i];
        }
    }else{
        System.out.println("There are no elements to delete.");
    }
}

Here is to copy the data into temp and recreate a data. Then assign the data except the end of the queue back to the data. There should be other ways, here for reference only.

Then delete by subscription:

/**
* Delete data from a specified location
* @param index subscript
*/
public void delete(int index){
    if(index < 0 || index > length - 1){
        System.out.println("Subscripts crossed the border");
    }else{
        length--;
        T[] temp = data.clone();
        data = (T[])new Object[size];
        for(int i = 0; i < length; i++){
            if(i < index){
                data[i] = temp[i];
            }else{
                data[i] = temp[i + 1];
            }
        }
    }
}

Here is to take index as the boundary, the first is the normal assignment, and the second (i + 1) is the assignment. There are some other approaches, which are not implemented in detail here.

The following two problems are solved:

(1) Why do sequential tables query quickly?

We don't implement the query method here, but we know that the underlying implementation of the sequential table is through arrays. It can be said that the query of sequential table is the query of array, and the data is stored in adjacent memory, so the query time is fast.

(2) Why is the insertion of sequential tables slow?

We have implemented insertion and deletion methods and multiple replications will be found. We're inserting in the middle, which is probably a step: save index to the end of the queue - > insert data - > assign the saved data back. Deleting is probably a similar process. This consumes a lot of resources, so it's slower. When there is little data, you can't feel anything. When there is a large amount of data, there is a big difference. So it is very necessary to learn the data structure, so let's start here today.