順序表

順序表是用一段物理地址連續的存儲單元依次存儲數據元素的線性結構,一般情況下采用數組存儲。在數組上完成數據的增刪查改。
順序表一般可以分為:
1、靜態順序表:使用定長數組存儲。
2、動態順序表:使用動態開闢的數組存儲。
注意事項:
1、靜態順序表適用於確定知道需要存多少數據的場景.
2、靜態順序表的定長數組導致N定大了,空間開多了浪費,開少了不夠用

import java.util.Arrays;

/**
 * @ Created with IntelliJ IDEA.
 * @ClassName MyArrayList
 * @Description
 * @Author byJosvin
 * @Date 2020/3/22 16:05
 */
public class MyArrayList {
    public int[] elem;//null
    public int usedSize;//0

    //設置默認容量
    public static final int DEFAULT_SIZE = 2;
   
    public MyArrayList() {
        this.elem = new int[DEFAULT_SIZE];
        this.usedSize = 0;
    }
    // 打印順序表
    public void display() {
        for(int i=0;i<this.usedSize;i++) {
            System.out.print(this.elem[i]+" ");
        }
        System.out.println();

    }
    // 在 pos 位置新增元素
    public void add(int pos,int date) {
        if(isFull()) {
            grow();
        }
        //
        for(int i=this.usedSize-1;i>=pos;i--) {
            this.elem[i+1]=this.elem[i];
        }
        this.elem[pos]=date;
        this.usedSize++;
    }
    // 判定是否包含某個元素
    public boolean contains(int toFind) {
        if(isNull()) {
            return false;
        }
        for(int i=0;i<this.usedSize;i++) {
            if(this.elem[i]==toFind) {
                return true;
            }
        }
        return  false;
    }
    // 查找某個元素對應的位置
    public int search(int toFind) {
        if(isNull()) {
            return -1;
        }
        for(int i=0;i<this.usedSize;i++) {
            if(this.elem[i]==toFind) {
                return i;
            }
        }
        return -1;
    }
    // 獲取 pos 位置的元素
    public int getPos(int pos) {
        if(isNull()) {
            return -1;
        }
        if(pos<0||pos>=this.usedSize) {
            return -1;
        }
        return this.elem[pos];
    }
    // 給 pos 位置的元素設為 value
    public void setPos(int pos, int value) {
        if(pos<0||pos>this.usedSize-1) {
            return;
        }
        this.elem[pos]=value;
    }
    // 獲取順序表長度
    public int size() {
        if(isNull()) {
            return 0;
        }
        else {
            return usedSize;
        }
    }
    // 清空順序表
    public void clear() {
        if(isNull()) {
            return;
        }
        usedSize=0;
    }
    //刪除順序表pos位置
    public void removeNum(int pos) {

        for(int i=pos;i<usedSize;i++) {
            this.elem[i]=this.elem[i+1];
        }
        this.usedSize--;
    }
    //刪除第一次出現的關鍵字key
    public void remove(int key) {
        int index=this.search(key);
        if(index<0||index>=this.usedSize) {
            return ;
        }
        this.removeNum(index);
    }
    //擴表,拷貝一個大的數組
    private  void grow() {
        this.elem= Arrays.copyOf(this.elem,this.elem.length*2);
    }
    //判滿
    public boolean isFull() {
       if(this.usedSize == this.elem.length) {
            return true;
        }
        return false;
    }
    //判空
    public boolean isNull() {
        if(this.usedSize == 0) {
            return true;
        }
        return false;
    }

}

思考

  1. 順序表中間/頭部的插入刪除,時間複雜度為O(N)
  2. 增容需要申請新空間,拷貝數據,釋放舊空間。會有不小的消耗。
  3. 增容一般是呈2倍的增長,勢必會有一定的空間浪費。例如當前容量為100,滿了以後增容到200,我們再繼續插入了5個數據,後面沒有數據插入了,那麼就浪費了95個數據空間。