Realization of basic function of sequence table

️ The concept of linear tables

The linear table （linear list） yes n A finite sequence of data elements with the same characteristics . Linear table is a data structure widely used in practice , often
See the linear table of ： The order sheet 、 Linked list 、 Stack 、 queue 、 character string …
A linear table is logically a linear structure , That is to say, it is a continuous straight line . But it is not necessarily continuous in physical structure （ For example, linked list ）, When a linear table is physically stored , It is usually stored in the form of array and chain structure

️ The order sheet

The concept of sequential table ：
A sequence table is a linear structure in which data elements are sequentially stored in a section of storage cells with continuous physical addresses , In general, array storage is used . Add, delete, check and modify the data on the array .

Implementation of dynamic sequence table

First of all, let's think about a question , The data structure at the bottom of the sequence table is an array , Then you can replace the sequence table with this array , Why is there such a sequence table ？？ Why should there be a sequence table ？

We can simply think like this , A sequence table is a data structure , A way to describe and organize data , There are many kinds of data stored in memory , In order to process data , Realize different functions , There are different data structures , for instance , When calculating the number of elements in the array , If we traverse the array , Define a counter , Encounter non 0 The counter is just +1, encounter 0 End the program , If the data encountered is 0 He Fei 0 The numbers cross , Or the data we store is itself 0, This algorithm is problematic , Arrays are chicken ribs , Therefore, we realize this function through the sequence table , Put a number and record it once .

Diagram sequence table

Next, we implement the sequence table through the object-oriented idea ,1. Find object to , This sequence table has only one object, which is this sequence table ,2. Create objects , The member properties of the order table object include an array , A tag that records the number of array elements usedsize, A member that identifies the capacity of the array , Then use the object .

Create member properties , Call the constructor to initialize the object

public class MyArrayList {
    
    public int[] elem;//elem=null
    public int usedSize;// Element number 
    public static  int capacity = 10;// The capacity of the array is more than the number of elements , Otherwise, it will be expanded 

    public MyArrayList() {
    
        this.elem = new int[capacity];
        //this.usedSize = 0;
    }

After we initialize the object , object , The relationship between member attributes and memory layout are roughly as follows ：

Add an element at a certain position in the sequence table , There are roughly two situations , As shown in the figure below

 public boolean isFull() {
    // Determine whether the array elements are full , Full return ture, Otherwise return to false
        /*if(this.usedSize == capacity) { return true; } return false;*/
        return this.usedSize == capacity;
    }

    //  stay  pos  Location new element 
    public void add(int pos, int data) {
    
        if(pos < 0 || pos > this.usedSize) {
    
            System.out.println("pos Illegal location ！");
            return;
        }
        //1、 Full condition  2、pos The legal situation of 
        if(isFull()) {
    
            // Capacity expansion 
            this.elem =Arrays.copyOf(this.elem,2*capacity);// Expand at least twice the capacity 
            capacity *= 2;// New capacity 
        }
        for(int i = this.usedSize-1; i >= pos;i--) {
    
            this.elem[i+1] = this.elem[i];// The number of elements does not reach the capacity of the array ,i+1 It will not cross the boundary 
        }
        this.elem[pos] = data;// Add a new element when there is no element for the first time or in pos Position the element to be added 
        this.usedSize++;
    }

Situation 1

Situation two

Print order table , Just traverse the array

 //  Print order table 
    public void display() {
    
        for (int i = 0; i < this.usedSize; i++) {
    
            System.out.print(this.elem[i] +" ");
        }
        System.out.println();
    }

Determine whether to include an element
It's easy to determine whether an element is included . Just traverse the array , Function return value boolean type , Return if it is found to be true true, False return if not found false

public boolean isEmpty() {
    
        return this.usedSize == 0;
    }
    //  Determine whether to include an element 
    public boolean contains(int toFind) {
    
        if(isEmpty()) return false;// Return directly if it is empty 
        for (int i = 0; i < this.usedSize; i++) {
    
            if(this.elem[i] == toFind) {
    
                return true;
            }
        }
        return false;
    }

Find the corresponding position of an element , Return the corresponding element subscript , If the sequence table is empty , No return found -1

//  Find the corresponding position of an element 
    public int search(int toFind) {
    
        if(isEmpty()) return -1;// Just go back to -1 I just can't find 
        for (int i = 0; i < this.usedSize; i++) {
    
            if(this.elem[i] == toFind) {
    
                return i;
            }
        }
        return -1;
    }

obtain pos The element of location
because pos Is used as an array subscript , Returns the of the element at the corresponding position , the pos The values for 0~usedSize-1( It includes two endpoints ）

//  obtain  pos  The element of location 
    public int getPos(int pos) {
    
        if(isEmpty()) {
    
            //return -1;  Business processing , return -1 We should know that the sequence table is empty at this time 
            throw new RuntimeException(" The order table is empty ");// Manually throw an error ( abnormal )
        }
        if(pos < 0 || pos >= this.usedSize) {
    // Judge the legitimacy of the location 
            throw new RuntimeException("pos illegal ");// Manually throw an error ( abnormal )
        }

        return this.elem[pos];
    }

Get the length of the order table , Directly return the member attribute udedSize Value

 //  Get the length of the order table 
    public int size() {
    
        return this.usedSize;
    }

to pos The element of the position is set to value,pos Also as an array subscript ,pos by 0 Said to 0 The element of location , The first element is set to value value , And so on , So the judge pos When it comes to legitimacy ,pos To be less than usedSize.

 //  to  pos  The element of the position is set to  value
    public void setPos(int pos, int value) {
    
        if(pos < 0 || pos >= this.usedSize) {
    
            System.out.println("pos illegal ！");
            return;
        }
        if(isEmpty()) {
    
            System.out.println(" Sequence table is empty ！");// It's OK not to judge whether it is empty , If it is empty ,usedsize  by 0 The length of the array is 0, Judging from above pos Legitimacy , No matter what you type , It's all illegal 
            return;
        }
        this.elem[pos] = value;
    }

Delete the first keyword key

 // Delete the first keyword key
    public void remove(int toRemove) {
    
        if(isEmpty()) return;
        int index = search(toRemove);
        if(index == -1) {
    
            System.out.println(" There are no numbers you want to delete ");
            return;
        }
        for (int i = index; i < this.usedSize-1; i++) {
    //usedsize Need to get 1, Prevent cross-border 
            this.elem[i] = this.elem[i+1];// When deleting, move to the position where the subscript of the array is small 
        }
        this.usedSize--;// The last element that has not been moved can also be deleted by the print function 
    }

️ Clear the sequence table , Set all elements to 0, Element number usedSize Also set to 0 that will do .

 //  Clear the sequence table 
    public void clear() {
    
        for (int i = 0; i < this.usedSize; i++) {
    
            this.elem[i] = 0;
        }
        this.usedSize = 0;
    }
}

️ Copy all the above code to MyArrayList Class is the complete code , Here's a test class , Test the function of the sequence table .

public class TestDemo {
    

    public static void main(String[] args) {
    
        MyArrayList myArrayList = new MyArrayList();
        //myArrayList.add(-1, 1);
        myArrayList.add(0, 2);
        myArrayList.add(1, 3);
        myArrayList.add(2, 4);
        myArrayList.add(3, 4);
        myArrayList.remove(4);
    // myArrayList.add(5, 4);
        myArrayList.display();
        }
        }

︿(￣︶￣)︿ (^▽) ( ＾∀＾）／ welcome ＼( ＾∀＾）
Remember to hold