C++列表

數(shù)組長度不可變導(dǎo)致實用性降低。在實際中，我們可能事先無法確定需要存儲多少數(shù)據(jù)，這使數(shù)組長度的選擇變得困難。若長度過小，需要在持續(xù)添加數(shù)據(jù)時頻繁擴(kuò)容數(shù)組；若長度過大，則會造成內(nèi)存空間的浪費。

為解決此問題，出現(xiàn)了一種被稱為「動態(tài)數(shù)組 dynamic array」的數(shù)據(jù)結(jié)構(gòu)，即長度可變的數(shù)組，也常被稱為「列表 list」。列表基于數(shù)組實現(xiàn)，繼承了數(shù)組的優(yōu)點，并且可以在程序運行過程中動態(tài)擴(kuò)容。我們可以在列表中自由地添加元素，而無須擔(dān)心超過容量限制。

列表常用操作

1.   初始化列表

我們通常使用“無初始值”和“有初始值”這兩種初始化方法。

list.cpp

/* 初始化列表 */
// 需注意，C++ 中 vector 即是本文描述的 list
// 無初始值
vector<int> list1;
// 有初始值
vector<int> list = { 1, 3, 2, 5, 4 };

2.   訪問元素

列表本質(zhì)上是數(shù)組，因此可以在 O(1) 時間內(nèi)訪問和更新元素，效率很高。

list.cpp

/* 訪問元素 */
int num = list[1];  // 訪問索引 1 處的元素

/* 更新元素 */
list[1] = 0;  // 將索引 1 處的元素更新為 0

3.   插入與刪除元素

相較于數(shù)組，列表可以自由地添加與刪除元素。在列表尾部添加元素的時間復(fù)雜度為 $O\left(1\right)$ ，但插入和刪除元素的效率仍與數(shù)組相同，時間復(fù)雜度為 O$\left(n\right)$ 。

list.cpp

/* 清空列表 */
list.clear();

/* 尾部添加元素 */
list.push_back(1);
list.push_back(3);
list.push_back(2);
list.push_back(5);
list.push_back(4);

/* 中間插入元素 */
list.insert(list.begin() + 3, 6);  // 在索引 3 處插入數(shù)字 6

/* 刪除元素 */
list.erase(list.begin() + 3);      // 刪除索引 3 處的元素

4.   遍歷列表

與數(shù)組一樣，列表可以根據(jù)索引遍歷，也可以直接遍歷各元素。

list.cpp

/* 通過索引遍歷列表 */
int count = 0;
for (int i = 0; i < list.size(); i++) {
    count++;
}

/* 直接遍歷列表元素 */
count = 0;
for (int n : list) {
    count++;
}

5.   拼接列表

給定一個新列表 list1 ，我們可以將該列表拼接到原列表的尾部。

list.cpp

/* 拼接兩個列表 */
vector<int> list1 = { 6, 8, 7, 10, 9 };
// 將列表 list1 拼接到 list 之后
list.insert(list.end(), list1.begin(), list1.end());

6.   排序列表

完成列表排序后，我們便可以使用在數(shù)組類算法題中經(jīng)常考察的“二分查找”和“雙指針”算法。

list.cpp

/* 排序列表 */
sort(list.begin(), list.end());  // 排序后，列表元素從小到大排列

列表實現(xiàn)

許多編程語言都提供內(nèi)置的列表，例如 Java、C++、Python 等。它們的實現(xiàn)比較復(fù)雜，各個參數(shù)的設(shè)定也非常有考究，例如初始容量、擴(kuò)容倍數(shù)等。感興趣的讀者可以查閱源碼進(jìn)行學(xué)習(xí)。

為了加深對列表工作原理的理解，我們嘗試實現(xiàn)一個簡易版列表，包括以下三個重點設(shè)計。

• 初始容量：選取一個合理的數(shù)組初始容量。在本示例中，我們選擇 10 作為初始容量。
• 數(shù)量記錄：聲明一個變量 size，用于記錄列表當(dāng)前元素數(shù)量，并隨著元素插入和刪除實時更新。根據(jù)此變量，我們可以定位列表尾部，以及判斷是否需要擴(kuò)容。
• 擴(kuò)容機(jī)制：若插入元素時列表容量已滿，則需要進(jìn)行擴(kuò)容。首先根據(jù)擴(kuò)容倍數(shù)創(chuàng)建一個更大的數(shù)組，再將當(dāng)前數(shù)組的所有元素依次移動至新數(shù)組。在本示例中，我們規(guī)定每次將數(shù)組擴(kuò)容至之前的 2 倍。

/* 列表類簡易實現(xiàn) */
class MyList {
  private:
    int *nums;             // 數(shù)組（存儲列表元素）
    int numsCapacity = 10; // 列表容量
    int numsSize = 0;      // 列表長度（即當(dāng)前元素數(shù)量）
    int extendRatio = 2;   // 每次列表擴(kuò)容的倍數(shù)

  public:
    /* 構(gòu)造方法 */
    MyList() {
        nums = new int[numsCapacity];
    }

    /* 析構(gòu)方法 */
    ~MyList() {
        delete[] nums;
    }

    /* 獲取列表長度（即當(dāng)前元素數(shù)量）*/
    int size() {
        return numsSize;
    }

    /* 獲取列表容量 */
    int capacity() {
        return numsCapacity;
    }

    /* 訪問元素 */
    int get(int index) {
        // 索引如果越界則拋出異常，下同
        if (index < 0 || index >= size())
            throw out_of_range("索引越界");
        return nums[index];
    }

    /* 更新元素 */
    void set(int index, int num) {
        if (index < 0 || index >= size())
            throw out_of_range("索引越界");
        nums[index] = num;
    }

    /* 尾部添加元素 */
    void add(int num) {
        // 元素數(shù)量超出容量時，觸發(fā)擴(kuò)容機(jī)制
        if (size() == capacity())
            extendCapacity();
        nums[size()] = num;
        // 更新元素數(shù)量
        numsSize++;
    }

    /* 中間插入元素 */
    void insert(int index, int num) {
        if (index < 0 || index >= size())
            throw out_of_range("索引越界");
        // 元素數(shù)量超出容量時，觸發(fā)擴(kuò)容機(jī)制
        if (size() == capacity())
            extendCapacity();
        // 將索引 index 以及之后的元素都向后移動一位
        for (int j = size() - 1; j >= index; j--) {
            nums[j + 1] = nums[j];
        }
        nums[index] = num;
        // 更新元素數(shù)量
        numsSize++;
    }

    /* 刪除元素 */
    int remove(int index) {
        if (index < 0 || index >= size())
            throw out_of_range("索引越界");
        int num = nums[index];
        // 索引 i 之后的元素都向前移動一位
        for (int j = index; j < size() - 1; j++) {
            nums[j] = nums[j + 1];
        }
        // 更新元素數(shù)量
        numsSize--;
        // 返回被刪除元素
        return num;
    }

    /* 列表擴(kuò)容 */
    void extendCapacity() {
        // 新建一個長度為原數(shù)組 extendRatio 倍的新數(shù)組
        int newCapacity = capacity() * extendRatio;
        int *tmp = nums;
        nums = new int[newCapacity];
        // 將原數(shù)組中的所有元素復(fù)制到新數(shù)組
        for (int i = 0; i < size(); i++) {
            nums[i] = tmp[i];
        }
        // 釋放內(nèi)存
        delete[] tmp;
        numsCapacity = newCapacity;
    }

    /* 將列表轉(zhuǎn)換為 Vector 用于打印 */
    vector<int> toVector() {
        // 僅轉(zhuǎn)換有效長度范圍內(nèi)的列表元素
        vector<int> vec(size());
        for (int i = 0; i < size(); i++) {
            vec[i] = nums[i];
        }
        return vec;
    }
};