列表与动态数组

列表与数组有什么区别？

• 列表: 在数组之上封装长度可变能力的结构;
• 关键差别: 数组容量固定, 列表在容量不足时自动扩容;

列表如何扩容？

• 触发条件: 元素数量超过当前容量;
• 策略: 容量扩充为当前容量的 2 倍;
• 代价: 扩容时需要整体复制, 单次操作 O(n); 摊销到每次添加仍为 O(1);

列表各操作的时间复杂度是多少？

操作	复杂度	原因
访问	O(1)	连续存储, 按下标定位
插入	O(n)	需要搬移后续元素
删除	O(n)	需要搬移后续元素
添加	O(1)	直接写入尾部; 触发扩容时为 O(n)

如何用数组实现列表？

export class List<T> {
  capacity: number;
  size: number;
  array: T[];

  constructor(capacity: number) {
    this.capacity = capacity;
    this.size = 0;
    this.array = new Array(capacity);
  }

  get(index: number): T {
    if (index >= this.size || index < 0) throw new Error("exceed");
    return this.array[index];
  }

  append(value: T): boolean {
    if (this.size === this.capacity) {
      const array = new Array(2 * this.capacity);
      this.capacity *= 2;
      for (let index = 0; index < this.array.length; index++) {
        array[index] = this.array[index];
      }
      array[this.size] = value;
      this.size++;
      this.array = array;
      return true;
    }
    this.array[this.size] = value;
    this.size++;
    return true;
  }

  insert(position: number, value: T): boolean {
    if (position >= this.size || position < 0) throw new Error("exceed");
    if (this.size === this.capacity) {
      const array = new Array(2 * this.capacity);
      this.capacity *= 2;
      for (let index = 0; index < position; index++) array[index] = this.array[index];
      array[position] = value;
      for (let index = position; index < this.array.length; index++) {
        array[index + 1] = this.array[index];
      }
      this.size++;
      this.array = array;
      return true;
    }
    for (let index = this.size - 1; index >= position; index--) {
      this.array[index + 1] = this.array[index];
    }
    this.array[position] = value;
    this.size++;
    return true;
  }

  delete(position: number): T {
    if (position >= this.size || position < 0) throw new Error("exceed");
    const deleted = this.array[position];
    for (let index = position + 1; index < this.array.length; index++) {
      this.array[index - 1] = this.array[index];
    }
    this.size--;
    return deleted;
  }
}