1, Linear table

A linear list is a finite sequence of n data elements with the same characteristics. Linear table is a data structure widely used in practice. Common linear tables: sequential table, linked list, stack, queue, string

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?

First, the bottom of the order table is an array

Why not use arrays directly??

Let's draw a diagram: (how much valid data is there in this array?)

Some people will say: not three???

I said: don't count yourself, let the program know??

Others say: jump out when it is equal to 0, count!!!

This is not feasible:

What if 0 is also data? Right, there's a problem here.

Then we can define a variable: this variable is called useSide (representing how much valid data is currently in it)

Here are four data:

Here are four valid data:

Therefore, this is the export of sequence table: a sequence table can be implemented with more than one array, and other variables (such as (usedSize) are required

Code implementation:
First, we find that this object is a sequence table, which contains arrays, valid array variables and an array capacity:

See a layout of instantiated objects in main in memory:

Implementation sequence table:

Basic composition Code:

Array, valid array, usable capacity

public class MyArrayList {
    public int[] elem;  //array
    public int useSize; //Valid array
    public static int capacity = 10; //Available capacity

    public MyArrayList() {   //Initial capacity using construction method
        this.elem = new int[capacity];
    }
}

3, Common operation implementation of sequence table:

Functions to be realized: look at them one by one

// Print sequence table
     public void display() {   }
     // Add new element in pos position
     public void add(int pos, int data) { }
     // Determines whether an element is included
     public boolean contains(int toFind) { return true; }
     // Find the location of an element
     public int search(int toFind) { return -1; }
     // Gets the element of the pos location
     public int getPos(int pos) { return -1; }
     // Set the element of pos position to value
     public void setPos(int pos, int value) {   }
     //Delete the keyword key that appears for the first time
     public void remove(int toRemove) {   }
     // Get sequence table length
     public int size() { return 0; }
     // Empty sequence table
     public void clear() {   }

(1) Add new element in pos position

Put the specified data in the specified location:

Let's talk about the idea first:

1. Determine whether the array is full
2. Judge whether the stored location subscript is legal (whether the array is out of bounds)
3. If it is full, it can be expanded
4. If you want to store data in an array, you must first put the following array one step behind, so that there will be a place in front
5. Store the data and remember useSize + +; (add 1 to the valid data)

Let's take a look at image parsing: it also moves the last element of the array one bit back

The above is the code idea. Let's see how the code is implemented!

 public boolean isFull(){
            //1. Full
            return this.useSize==capacity; //Judge whether the useSize is the same as the maximum capacity. If it is the same, it will be full
        }

// Add new element in pos position
        public void add(int pos, int data) {
            if(pos<0 || pos>this.useSize){ //Judge whether the subscript is legal
                System.out.println("Illegal subscript position");
                return;
            }
            if(isFull()){                //Expansion array size
                this.elem = Arrays.copyOf(this.elem,2*capacity); //A new copy is required for capacity expansion
                capacity *=2;       //The capacity should also become larger
            }

            for (int i = useSize-1; i >=pos ; i--) {
                this.elem[i+1] = this.elem[i];  //The current element moves to the position after i+1
            }
            this.elem[pos] = data;
            this.useSize++;
        }

(2) Print sequence table

Idea: just traverse the array

Code: note that the length of the traversal is useSize

// Print sequence table
        public void display() {

            for (int i = 0; i < this.useSize; i++) {
                System.out.print(elem[i] + " ");
            }
            System.out.println();

        }

(4) Determines whether an element is included

Idea: just traverse the array

Code: note that the length of the traversal is useSize

public boolean isEmpty(){
            return useSize==0;
}

 public boolean contains(int toFind) {
        if (isEmpty()){
            return false;
        }

            for (int i = 0; i < this.useSize; i++) {
                if (elem[i]==toFind){
                    return true;
                }
            }
        return false;
    }

(4) Find the location of an element

Idea: traverse the array to find the return subscript

Code: note that the length of the traversal is useSize

public int search(int toFind) {
            for (int i = 0; i < elem.length; i++) {
                if (elem[i]==toFind){
                    return i;
                }
            }
        return -1;
    }

(5) Gets the element of the pos location

Idea: directly return the array of pos subscripts

code:

public int getPos(int pos) {
            if (pos<0||pos >=useSize){    
                throw new RuntimeException("Illegal current subscript");  //Throw exception manually
            }
            if (isEmpty()){
                throw new RuntimeException("The current sequence table is empty");  //Throw exception manually
            }
            return this.elem[pos];
        }

(5) Get sequence table length

Idea: just return to useSize directly

public int size() {
   return this.useSize;
}

(5) Set the element of pos position to value

Idea: just assign the value directly, and pay attention to the legitimacy of the subscript

public void setPos(int pos, int value) {
                if(pos<0 || pos>= this.useSize){
                    System.out.println("pos wrongful");
                }
                if(isEmpty()){
                    System.out.println("Sequence table");
                }
                this.elem[pos] =value;
        
        }

(6) Delete the keyword key that appears for the first time

Idea: the code is a bit like add. The general principle is to find the element to be deleted, and then let the next element to the current element. Finally, useSize –;

Picture presentation:

code:

 //Delete the keyword key that appears for the first time
        public void remove(int toRemove) {
        
            if (isEmpty()){  //Judge whether it is empty
                return;
            }
            int index =search(toRemove);  //Find the subscript to delete
            if (index==-1){
                return;
            }

            for (int i = index; i <useSize-1; i++) {
                elem[i] = elem[i+1];   //Let the next value override the previous one
            }
            useSize--;   //Effective number--
        }

Think about a question: why use size-1
Because the following is i+1, if I goes to the last grid, you will report a null pointer exception in elem[i] = elem[i+1]:

(7) Empty sequence table

Idea: traverse to make each element become 0, and finally useSize is equal to 0;
code:

 public void clear() {
            for (int i = 0; i <useSize; i++) {
                 this.elem[i]=0;
            }
            useSize=0;
        }