线性表 - 无序表
    getItem O(1)
    setItem O(1)
    push O(n)
    insert O(n)
    delect O(n)
    search O(n)

    基本操作

    1. class List {
    2.     // 1.创建空的数组 指定size
    3.     constructor() {
    4.       this.arr = new Array(10);
    5.       this.size = 10;
    6.       this.length = 0;
    7.       this.realloc = () => {
    8.         let new_arr = null;
    9.         // 扩大
    10.         if(this.length === this.size) {
    11.           // 增加空间 原来数据拷贝到新数据
    12.           this.size = this.size*2;
    13.           new_arr = new Array(this.size);
    14.         } else if(this.length < (this.size/4)) {
    15.           // 判断是否需要缩小
    16.           this.size = Math.floor(this.size/2);
    17.           new_arr = new Array(this.size);
    18.         }
    19.         if(new_arr) {
    20.           for(let i = 0; i < this.length; i++){
    21.             new_arr[i] = this.arr[i]
    22.           }
    23.           delete this.arr;
    24.           this.arr = new_arr;
    25.         }
    26.       };
    27.       this.checkRange= (index) => {
    28.         if(typeof index !== 'number' || index < 0 || index >= this.length) {
    29.           throw new RangeError();
    30.         }
    31.       }
    32.     }
    34.     getItem(index){
    35.       this.checkRange(index);
    36.       return this.arr[index];
    37.     }
    39.     setItem(index, value) {
    40.       this.checkRange(index);
    41.       return this.arr[index] = value;
    42.     }
    43.     // 添加
    44.     append(value){
    45.       this.arr[this.length] = value;
    46.       this.length++;
    47.       // 如果超出 扩展空间
    48.       this.realloc();
    49.     }
    51.     // 插入
    52.     insert(value, pointIndex) {
    53.       if(pointIndex < 0 || pointIndex > this.length) {
    54.         throw new RangeError();
    55.       } else if (pointIndex === this.length) {
    56.         append(value);
    57.       } else {
    58.         // 1.index的数据都向后移动一位
    59.         for(let j = this.length; j > pointIndex; j --) {
    60.           this.arr[j] = this.arr[j-1];
    61.         }
    62.         // 2.新的数据放到 index 位置上
    63.         this.arr[pointIndex] = value;
    64.         this.length++;
    65.         // 如果超出 扩展空间
    66.         this.realloc();
    67.       }
    68.     }
    70.     // 删除某一项
    71.     delete(index) {
    72.       this.checkRange(index);
    73.       // 1.index的数据都向前移动一位
    74.       for(let j = index; j < this.length -1; j ++) {
    75.         this.arr[j] = this.arr[j+1];
    76.       }
    77.       this.length--;
    78.       this.realloc();
    79.     }
    81.     // 有序的数组 二分法查找 适用于搜索性能更高
    82.     search(value) {
    83.       let s = 0;
    84.       let e = this.arr.length - 1;
    86.       while(s <= e) {
    87.         let center = Math.floor((s+e)/2);
    88.         if(value === this.arr[center]) {
    89.           return center;
    90.         } else if(value < this.arr[center]) {
    91.           e = center - 1;
    92.         } else(value > this.arr[center]) {
    93.           s = center + 1;
    94.         }
    95.       }
    96.       return -1;
    97.     }
    99.   }
    101.   const list = new List();
    102.   list.append(1);
    103.   list.append(2);
    104.   list.append(3);
    105.   list.append(4);
    106.   list.append(5);
    107.   list.append(6);
    108.   list.append(7);
    109.   list.append(8);
    110.   list.append(9);
    111.   list.append(10);
    112.   list.append(6);
    113.   list.append(7);
    114.   list.append(8);
    115.   list.append(9);
    116.   list.append(10);
    117.   list.append(11);
    119.   console.log(list);