All the ArrayList knowledge you want to know is here

ArrayList And sequence table

The linear table

The linear table is n A finite sequence of data elements with the same properties , Common linear tables are ： The order sheet 、 Linked list 、 Stack 、 queue ……

A linear table is logically linear , That is, a continuous straight line , But it is not necessarily continuous in physical structure , When a linear table is physically stored , It is mainly stored in the form of array and chain structure .

Here we need to know what is physical and logical

Physically ： In fact, it's in memory

logically : Is thinking

Definition of sequence table

A sequence table is a linear structure in which data elements are stored once in a storage unit with continuous physical addresses , Generally, it is stored by an array , Add, delete, check and modify data on the array .

MyArrayList class

The knowledge of data structure is very rigorous , Therefore, we must consider carefully when implementing

// Write first MyArrayLis Class fields and constructors 
class MyArrayList {
    
    public int[] elem;
    public int usedSized;//usedSized Is the valid data stored in the current array 
    public static final int DEFAULT_CAPACITY=10;// Size of initial array 

    public  MyArrayList() {
       // Construction method  1、 no return value  2、 The method name is consistent with the class name 
        this.elem = new int[DEFAULT_CAPACITY];
    }
}

Print order table

//  Print order table -- Just print all the significant numbers 
public void display() {
    
    for (int i = 0; i < usedSized; i++) {
    
        System.out.print(this.elem[i]+" ");
    }
    System.out.println();
}

New data method (add)

To add data, you need to consider whether to expand , Then we will implement it in detail

//  New elements , Add at the end of the array by default -- We must consider whether the array will be full （ Capacity expansion ）
public void add(int data) {
    
    if(isFull()){
    
        elem= Arrays.copyOf(elem, elem.length * 2);//Arrays.copyOf The return value of is an array , So use elem Take over 
    }
    elem[usedSized]=data;
    usedSized++;
}

// Determine whether the array is full , Be sure to compare with the array length , Do not mix DEFAULT_CAPACITY Compare , Because it may be expanded later , You can't use it then DEFAULT_CAPACITY 了 , So here is elem.length
public boolean isFull() {
    
    return usedSized == elem.length;
}

add Method implementation in pos Add a new data at the subscript position

1、 Check whether the following table is legal

2、 Determine whether the array is full

3、 Concrete realization

To throw exceptions , It is better to customize exceptions

package sequence_table;
/*  Customize an exception ( Illegal subscript exception ) */
public class PosIndexNotLegalException extends RuntimeException {
    
    public PosIndexNotLegalException() {
    

    }

    public PosIndexNotLegalException(String message) {
    
        super(message);
    }
}

Specifically realize the new data

/* checkPosAdd To check whether the subscript to be added is legal , Set to private Because this method will not be removed outside the class , */
private void checkAddPosAdd(int pos) {
    
    if (pos < 0 || pos > usedSized) {
    
      throw new PosIndexNotLegalException("pos Illegal location ");// Throw exceptions 
    }
}
//  stay  pos  Location new element --add Method implements overloading  
public void add(int pos, int data) {
    
    try {
    
        checkAddPosAdd(pos);// Judge pos Is the following table reasonable 
        if (isFull()) {
      // Determine whether the array is full 
            elem= Arrays.copyOf(elem, elem.length * 2);
        }
        for (int i = usedSized-1; i >= pos ; i--) {
    
            elem[i + 1] = elem[i];
        }
        elem[pos]=data;
        usedSized++;
    } catch (PosIndexNotLegalException e) {
    
        e.printStackTrace();
    }
}

Determine whether to include an element

public boolean contains(int toFind) {
    
    for (int i = 0; i < usedSized; i++) {
    
        if (elem[i] == toFind) {
    
            return true;
        }
    }
    return false;
}

Find the corresponding position of an element

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

obtain pos The element of location

1、 Judge the validity of subscripts

2、 Concrete realization

/*  Judge get Methodical pos Is it legal , Judging from the above add Of pos The difference between whether it is legal or not is that you can't get usedSize */
private void checkGetPosAdd(int pos) {
    
    if (pos < 0 || pos >= usedSized) {
    
        throw new PosIndexNotLegalException("get Methodical pos Illegal location ");
    }
}

public int get(int pos) {
    
    try {
    
        checkGetPosAdd(pos);
        return elem[pos];
    } catch (PosIndexNotLegalException e) {
    
        // If it's really illegal , We have to deal with it here pos Illegal issues 
        e.printStackTrace();
    }
    return -1;
}

take pos The element of the position is set to value -- to update

public void set(int pos, int value) {
    
    try{
    
        checkGetPosAdd(pos);// Judge the legitimacy of subscripts 
        elem[pos] = value;
    }catch(PosIndexNotLegalException e){
    
        e.printStackTrace();
    }
}

Delete the first keyword key

public void remove(int toRemove) {
    
    int pos=indexOf(toRemove);//index If not found in the method toRemove Just go back to -1
    if (pos == -1) {
    
        System.out.println(" There is no such number ");
        return;
    }
    for (int i = pos; i <usedSized-1; i++) {
    
        elem[i] = elem[i + 1];
    }
    usedSized--;
}

Get the length of the order table

public int size() {
    
    return usedSized;
}

Clear the sequence table

public void clear() {
    
    // Because this is not a reference type , Not all for Circulated , Direct will usedSize Set as 0 that will do 
    /*for (int i = 0; i < usedSized; i++) { elem[i] = null; }*/
    usedSized=0;
}

The above is the implementation of the sequence table method

Actually Java We have been provided with the code of the sequence table , That's what it is ArrayList class

ArrayList class

public class Test {
    
    public static void main(String[] args) {
    
        ArrayList<Integer> arrayList1 = new ArrayList<>();
        arrayList1.add(0);
        arrayList1.add(1);
        arrayList1.add(2, 78);
        System.out.println(arrayList1);// Print 
    }
}

Intercept data

public static void main(String[] args) {
    
    ArrayList<String> list = new ArrayList<>();
    list.add("JavaSE");
    list.add("JavaWeb");
    list.add("JavaEE");
    list.add("JVM");
    list.add(" Test course ");
    List<String> ret = list.subList(1, 3);// Intercept , Left closed right away 
    System.out.println(ret);
}

In sequence 3 Ergodic methods

public static void main(String[] args) {
    
    ArrayList<String> list = new ArrayList<>();
    list.add("JavaSE");
    list.add("JavaWeb");
    list.add("JavaEE");
    list.add("JVM");
    list.add(" Test course ");
    List<String> ret = list.subList(1, 3);// Intercept , Left closed right away 
    //1、 Print directly 
    System.out.println(ret);
    System.out.println("==============");
    //2、for loop 
    for (int i = 0; i < list.size(); i++) {
    
        System.out.println(list.get(i));
    }
    System.out.println("==============");
    //3、foreach
    for (String x:list) {
    
        System.out.println(x);
    }
}
// The result is ：
[JavaWeb, JavaEE]
==============
JavaSE
JavaWeb
JavaEE
JVM
 Test course 
==============
JavaSE
JavaWeb
JavaEE
JVM
 Test course 

In fact, there is another The method of iterator To print the data in the sequence table

public static void main(String[] args) {
    
	Iterator<String> it = list.iterator();
        while (it.hasNext()) {
    
            System.out.println(it.next());
        }
}

Advantages and disadvantages of sequence table

advantage ： Because the sequence table stores data in a continuous memory space , So the space utilization rate is high

​ Because the sequence table stores data directly through subscripts , So the reading speed is fast

shortcoming ：

​ The insertion and deletion of the sequence table need to traverse all the data to move the data

​ Memory allocation is not flexible , When the data to be read is more than that of the sequence table , Will appear ” overflow “, conversely , There will be a waste of memory space

If you want to solve the above problems , We need to learn another data structure — Linked list .

The above is the theoretical knowledge of the sequence table and the simple method to realize , Then I will give some examples about the sequence table , I hope you can correct me more .