列表是一个抽象的数据结构概念，它表示元素的有序集合，并且支持增删改查，无须考虑容量。链表、数组都可以看作列表。长度不可变的列表实用性会变低，因此很多编程语言的列表都是基于动态数组实现。

列表常用操作

初始化列表

vector<int> nums1;
vector<int> nums = {1, 2, 3, 4, 5};

访问元素和更新元素

int num = nums[1];
nums[1] = 0;

插入与删除元素

nums.clear();
nums.push_back(1);
nums.push_back(2);
nums.push_back(3);
nums.push_back(4);
nums.push_back(5);

nums.insert(nums.begin() + 3, 6);

nums.erase(nums.begin() + 3);

遍历列表

int count = 0;
for (int i = 0; i < nums.size(); ++i) {
  count += nums[i];
}

count = 0;
for (int num : nums) {
  count += num;
}

拼接列表

vector<int> nums1 = {6, 7, 8, 9, 10};
nums.insert(nums.end(), nms1.begin(), nums2.begin());

排序列表

sort(nums.begin(), nums.end());

列表实现

列表主要有三个重点设计：

• 初始容量。数组根据初始的最大元素数量申请对应的内存空间。
• 元素数量。使用变量size记录当前元素数量。
• 扩容机制。插入元素时容量已满，则需要扩容。

class MyList {
private:
  int* arr;
  int arrCapacity = 10;
  int arrSize = 0;
  int extendRatio = 2; // 扩容因子
  
public:
  MyList() {
    arr = new int[arrCapactiy];
  }
  
  ~MyList() {
    delete[] arr;
  }
  
  int size() {
    return arrSize;
  }
  
  int capacity() {
    return arrCapacity;
  }
  
  int get(int index) {
    if (index < 0 || index >= size()) throw out_of_range("索引越界");
    return arr[index];
  }
  
  int set(int index, int num) {
    if (index < 0 || index >= size()) throw out_of_range("索引越界");
    arr[index] = num;
  }
  
  void add(int num) {
    if (size() == capacity())
      extentdCapacity();
    arr[size()] = num; 
    ++arrSize;
  }
  
  int remove(int index) {
    if (index < 0 || index >= size()) throw out_of_range("索引越界");
    int num = arr[index];
    
    for(int i = index; i < size(); ++i) {
      arr[i] = arr[i + 1];
    }
    
    --arrSize;
    return num;
  }
  
  void extendCapacity() {
    int newCapacity = capacity()*extendratio;
    int* tmp = arr;
    arr = new int[newCapacity];
    
    for (int i = 0; i < size(); ++i) {
      arr[i] = tmp[i];
    }
    
    delete[] tmp;
    arrCapacity = newCapacity;
  }
  
  vector<int> toVector() {
    vector<int> vec(size());
    for(int i = 0; i < size(); ++i) {
      vec[i] = arr[i];
    }
    
    return vec;
  }
}