1. What is a linear table?

linear list is a finite sequence of n data elements with the same characteristics. linear list is a data structure widely used in practice. Common linear lists include sequential list, linked list, stack, queue, string, etc
A linear table is logically a linear structure, that is, a continuous straight line. However, the physical structure is not necessarily continuous. When the linear table is stored physically, it is usually stored in the form of array and chain structure.

2. What is a sequence table?

Sequential table is a linear structure in which data elements are stored in sequence with a storage unit with continuous physical addresses. Generally, array storage is used. Complete the addition, deletion, query and modification of data on the array.
In java, dynamic sequence table is only stored in dynamic array
Advantages of dynamic sequence table: dynamic sequence table is more flexible and dynamically allocates space according to needs

Project detailed allocation:

• TestDemo.java implementation test method
• MyArrayList.java implementation of related sequence table functions

Define sequence table

TestDemo.java implementation test method:

 public class TestDemo {
    public static void main(String[] args) {
        MyArrayList myArrayList = new MyArrayList();
    }
}

    public int []elem;  //Underlying array
    public int useSize; //Valid length in array
    public int capacity = 10; //The array length is initialized to 10
    public MyArrayList(){  //Implement a construction method to specify the array length for the array
        this.useSize = 0;
        this.elem = new int[this.capacity];
    }

Sequence table function

♈ Printing sequence table of sequence table

📝 Algorithm idea:

• Before printing the sequence table, let's think about what conditions will be required to print the sequence table?
• Array cannot be empty
• Traverse each element in the array in turn and print it to the screen
  Then we must first implement a space determination method, namely isEmpty method

     public boolean isEmpty(){
        if(this.useSize == 0){  //If the effective length of the array is 0, the array is empty
            return true;
        }
        return false;
    }

Then the isEmpty method is invoked in the printing method to realize printing data.

     //Print sequence table
    public void display(){
        //Determine whether the array is empty
        if(isEmpty()){
            System.out.println("Array is empty");
            return;
        }
        for(int i = 0;i<this.useSize;i++){
            System.out.println(this.elem[i]);
        }
        System.out.println();
    }

♉ Adding data to a sequence table

📝 Algorithm idea:

• If the location of the inserted data is unreasonable, an exception is thrown

• If the length of the linear table is greater than or equal to the length of the array, an exception is thrown or the capacity is increased dynamically

• Move moves forward from the last element to the i-th element position, moving them all back one unit

• Insert the number to insert at i position

• Effective length + 1

• Before adding data, let's think again. Are there any restrictions? If you are going to, is the subscript of the data legal?
• Is the original array full?
• These aspects need to be considered. To be a rigorous programmer, hahaha 😀😀😀.

   //Determine whether the array is full
    public boolean isFull(){
        if(this.useSize == this.capacity){//When the effective array length is equal to the array length, it indicates that the array is full of data at this time
            return true;
        }else{
            return false;
        }
    }

//Add new element in pos position
    public void add(int pos,int value){
        //Determine whether the array is full
        //Judge whether pos is sum method
        if(pos < 0 || pos > this.useSize){ //When the passed subscript is less than 0 or greater than the effective array length, it is returned directly. pos is illegal
            return ;
        }
        if(isFull()){
            System.out.println("The array is full, start expanding");
        }
        this.elem = Arrays.copyOf(this.elem,2*this.capacity);
        this.capacity*=2; //When the total length of the original array is full, expand the length of the array by 2 times
        //Start insertion
        for(int i = this.useSize;i>=pos;i--){
            this.elem[i+1] = this.elem[i];
        }
        this.elem[pos] = value;
        this.useSize++;
    }

♊ Whether the sequence table contains an element

📝 Algorithm idea:

• First, empty the sequence table, because when the array is empty, you cannot judge whether it contains an element
• Traverse the sequence table step by step until a certain value is found. If you want to improve the efficiency of the algorithm, you can use the binary search method. In this way, the time complexity of the algorithm becomes O(logN), and the time complexity will be reduced

   //Determines whether an element is included
    public void isContains(int value){
        //Determine whether the array is empty
        if(isEmpty()){
            System.out.println("Array is empty");
            return;
        }
        for(int i = 0;i<this.useSize;i++){
            if(this.elem[i] == value){
                System.out.println("Found this number");
            }else{
                System.out.println("You can't find this number");
            }
        }
    }

♋ Find out the corresponding position of an element in the sequence table

📝 Algorithm idea:

• First, empty the sequence table, because when the array is empty, you cannot judge whether it contains an element
• Traverse each value in the sequence table in turn, find an element and return its subscript

    //Find the corresponding position of an element
    public int search(int value){
        if(isEmpty()){
            System.out.println("Array is empty");
            return -1;
        }
        for(int i = 0;i<this.useSize;i++){
            if(this.elem[i] == value){
             return i;
            }
        }
        return -1;
    }

♌ Returns the corresponding position element according to the subscript of the sequence table

📝 Algorithm idea:

• First, empty the sequence table, because when the array is empty, you cannot judge whether it contains an element

• Judge the legitimacy of pos subscript

• Return the corresponding location element

    //Get the element of pos position
    public int getPos(int pos){
        if(isEmpty()){
            System.out.println("Array is empty");
            return -1;
        }
        return this.elem[pos];
    }

♍ Modifying an element of a sequence table

📝 Algorithm idea:

• Empty judgment processing
• Judge the legitimacy of pos subscript
• Modify original data

     //Set the element of pos position to value
    public void change(int pos,int value){
        if(isEmpty()){
            System.out.println("Array is empty");
            return;
        }
        if(pos<0 || pos > this.useSize){
            return;
        }
        this.elem[pos] = value;
    }

♎ Delete data of sequence table

📝 Algorithm idea:

• Empty judgment
• Find out whether there is data to be deleted in the sequence table
• If the deletion position is unreasonable, an exception is thrown
• Remove the deleted element
• Traverse from the deleted element position to the last element position, and move their positions forward one position respectively
• Effective length of sequence table - 1

     //Delete the keyword key that appears for the first time
    public void remove(int tomove){
        //Determine whether the array is empty
        if(isEmpty()){
            System.out.println("Array is empty");
            return;
        }
        //Determine whether there is this deleted number in the array
         int index = search(tomove);
        if(index == -1){
            System.out.println("There is no such number in the array");
        }
        //delete
        for(int i = index;i<this.useSize-1;i++){
            this.elem[i] = this.elem[i+1];
        }
        //When you want to delete the last data in the sequence table, you can delete it without entering the loop and the effective length of the array is - 1
        this.useSize--;
    }

♏ Empty data of sequence table

📝 Algorithm idea:

• Set each element in the sequence table to 0;
• Set the length of the valid sequence table to 0

  //Get sequence table length
    public int longth(){
        return this.useSize;
    }
    //Empty sequence table
    public void clear(){
        for(int i = 0;i<this.useSize;i++){
            this.elem[i] = 0;
        }
        this.useSize = 0;
    }

Summary:
💯 TestDemo.java file:

 public class TestDemo {
    public static void main(String[] args) {
        MyArrayList myArrayList = new MyArrayList();
    }
}

💯 MyArrayList file:

 public class MyArrayList {
    public int []elem;
    public int useSize;
    public static int capacity = 10;
    public MyArrayList(){
        this.useSize = 0;
        this.elem = new int[this.capacity];
    }
    //Determine whether the array is empty
    public boolean isEmpty(){
        if(this.useSize == 0){
            return true;
        }
        return false;
    }
    //Print sequence table
    public void display(){
        //Determine whether the array is empty
        if(isEmpty()){
            System.out.println("Array is empty");
            return;
        }
        for(int i = 0;i<this.useSize;i++){
            System.out.println(this.elem[i]);
        }
        System.out.println();
    }
    //Determine whether the array is full
    public boolean isFull(){
        if(this.useSize == this.capacity){
            return true;
        }else{
            return false;
        }
    }
    //Add new element in pos position
    public void add(int pos,int value){
        //Determine whether the array is full
        //Judge whether pos is sum method
        if(pos < 0 || pos > this.useSize){
            return ;
        }
        if(isFull()){
            System.out.println("The array is full, start expanding");
        }
        this.elem = Arrays.copyOf(this.elem,2*this.capacity);
        this.capacity*=2;
        //Start insertion
        for(int i = this.useSize;i>=pos;i--){
            this.elem[i+1] = this.elem[i];
        }
        this.elem[pos] = value;
        this.useSize++;
    }
    //Determines whether an element is included
    public void isContains(int value){
        //Determine whether the array is empty
        if(isEmpty()){
            System.out.println("Array is empty");
            return;
        }
        for(int i = 0;i<this.useSize;i++){
            if(this.elem[i] == value){
                System.out.println("Found this number");
            }else{
                System.out.println("You can't find this number");
            }
        }
    }
    //Find the corresponding position of an element
    public int search(int value){
        if(isEmpty()){
            System.out.println("Array is empty");
            return -1;
        }
        for(int i = 0;i<this.useSize;i++){
            if(this.elem[i] == value){
             return i;
            }
        }
        return -1;
    }

    //Get the element of pos position
    public int getPos(int pos){
        if(pos<0 || pos > this.useSize){
            return -1;
        }
        if(isEmpty()){
            System.out.println("Array is empty");
            return -1;
        }
        return this.elem[pos];
    }
    //Set the element of pos position to value
    public void change(int pos,int value){
        if(isEmpty()){
            System.out.println("Array is empty");
            return;
        }
        if(pos<0 || pos > this.useSize){
            return;
        }
        this.elem[pos] = value;
    }

    //Delete the keyword key that appears for the first time
    public void remove(int tomove){
        //Determine whether the array is empty
        if(isEmpty()){
            System.out.println("Array is empty");
            return;
        }
        //Determine whether there is this deleted number in the array
         int index = search(tomove);
        if(index == -1){
            System.out.println("There is no such number in the array");
        }
        //delete
        for(int i = index;i<this.useSize-1;i++){
            this.elem[i] = this.elem[i+1];
        }
        this.useSize--;
    }
    //Get sequence table length
    public int longth(){
        return this.useSize;
    }
    //Empty sequence table
    public void clear(){
        for(int i = 0;i<this.useSize;i++){
            this.elem[i] = 0;
        }
        this.useSize = 0;
    }
}