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

1. Judge whether the sequence table is full

   public boolean isFull(){
       return this.usedSize == capacity;
   }
   

2. 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[i-1];
       }
       this.elem[pos]=data;
       this.usedSize++;
   }
   

3. Print sequence table

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

4. Judge whether the sequence table is empty

   public boolean isEmpty(){
       return this.usedSize==0;
   }
   

5. 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;
   }
   

6. 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;
   }
   

7. 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

8. Get sequence table length

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

9. 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;
   }
   

10. 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.usedSize-1;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

11. 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