1, Linear table
A linear table is a finite sequence of n data elements with the same characteristics.
Common linear tables are:
Sequential list, linked list, stack, queue, string
The logic of a linear table is a linear structure, that is, a continuous line. However, the physical structure is not necessarily continuous. When a linear table is stored physically, it is usually stored in the form of array and chain structure, such as
2, Sequence table
1. Concept and structure
A sequential table is a linear structure in which data elements are sequentially stored in a storage unit with a continuous physical address. Generally, it is stored in an array
Since the sequence table is stored in array, why not use array directly? Are sequential tables and arrays the same thing? We can think about how to find the actual size of an array and a sequential table?
 For arrays: it seems a bit troublesome, because it is difficult for us to determine the position of the last actually used array under any conditions
 For the sequence table: we can save one count, hahaha. In this way, the array is different from the sequence table
So how does a simple sequence form?
We should have an array to store, the total capacity of the array and the actual values used in the array
Code is
publuc class MyArrayList{ // An array that stores data public int[] elem; // Total capacity of the array public static int capacity = 10; // Actual size of array public int usedSize; public MyArrayList(){ this.elem = new int[capacity]; } }
2. Interface implementation
After understanding the structure of the sequence table, we should implement the following interfaces to realize some contents more conveniently

Judge whether the sequence table is full
public boolean isFull(){ return this.usedSize == capacity; }

Add new element in pos position
public void add(int pos, int data){ if(pos<0  pos>this.usedSize){ System.out.println("pos Illegal location"); return; } if(isFull()){ // Capacity expansion this.elem=Arrays.copyOf(this.elem, 2*capacity); capacity*=2; } for(int i = this.usedSize;i>pos;i){ this.elem[i]=this.elem[i1]; } this.elem[pos]=data; this.usedSize++; }

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

Judge whether the sequence table is empty
public boolean isEmpty(){ return this.usedSize==0; }

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

Find the first occurrence of an element
public int search(int toFind){ if(isEmpty()){ return 1; } for(int i=0;i<this.usedSize;i++){ if(this.elem[i]==toFind){ return i; } } return 1; }

Gets the element of the pos location
public int getPos(int pos){ if(isEmpty()){ return 1; // throw new RuntimeException("the sequence table is empty"); } if(pos<0  pos>=this.usedSize){ throw new RuntimeException("Illegal order"); } return this.elem[pos]; }
 In fact, it is not necessary that the above code returns  1, because we can handle this when we know that the array cannot be equal to  1, but if it can be equal to  1 If it is wrong, you need to change other values (this is equivalent to processing the business in specific circumstances)
 You can also use throw new RuntimeException("the sequence table is empty") in the comment, This is actually an error (exception) thrown by hand

Get sequence table length
public int size(){ return this.usedSize; }

Set the element of the position of pos to value
public void setPos(int pos, int value){ if(pos<0  pos>=this.usedSize){ throw new RuntimeException("pos wrongful") } this.elem[pos]=value; }

Delete the keyword key that appears for the first time
public void remove(int toRemove){ if(isEmpty()){ System.out.println("Array is empty"); return; } int index=search(toRemove); if(indfex==1){ System.out.println("The number you want to delete is useless"); return; } for(int i =index;i<this.usedSize1;i++){ this.elem[i]=this.elem[i+1]; } this.usedSize; }
In fact, the last element cannot be deleted in the loop, because I < this usedSize, but the above code can directly delete the last element, because after the usedSize is reduced, it is equivalent to deleting the last element

Empty sequence table
public void clear(){ for(int i=0;i<this.usedSize;i++){ this.elem[i]=0; } this.usedSize=0; }
3. Time complexity of addition, deletion, modification and query
Now that we have implemented the above interfaces, we can think about the time complexity of adding, deleting, modifying and querying in the sequence table according to the above code
 Increase: time complexity: O(N)
 Delete: time complexity: O(N)
 Query: the time complexity for finding keywords is: O(N), and the time complexity for finding a given subscript is: O(1)
 Change: time complexity to: O(1)
By observing the time complexity of adding, deleting, checking and modifying, we find that the sequence table is more suitable for checking and modifying than adding and deleting
3, Summary
The sequence table introduced today should also be relatively easy. In fact, its essence is array. However, when we implement the above interface, we can find that
 Sequence table is more suitable for query and modification than addition and deletion
 Each capacity increase requires the application of new space to release the old space, which will lead to considerable consumption of space
 The capacity is increased by multiple, which is easy to cause a waste of space
Therefore, in the next chapter, I will introduce the linked list, which will solve some problems in the above sequence list
Complexity we find that the sequence table is more suitable for query and modification than for addition and deletion
3, Summary
The sequence table introduced today should also be relatively easy. In fact, its essence is array. However, when we implement the above interface, we can find that
 Sequence table is more suitable for query and modification than addition and deletion
 Each capacity increase requires the application of new space to release the old space, which will lead to considerable consumption of space
 The capacity is increased by multiple, which is easy to cause a waste of space
Therefore, in the next chapter, I will introduce the linked list, which will solve some problems in the above sequence list