學習資源

https://labuladong.online/algo/data-structure-basic/array-basic/

學習記錄

今天是學習的第 2 天，主要學習了陣列（順序儲存）基本原理：

可以將陣列分為兩大類，分別是 「靜態陣列」 和 「動態陣列」。

• 靜態陣列：是一塊連續的記憶體空間，可以透過索引來存取這塊記憶體空間中的元素，是陣列的原始形態
• 動態陣列：是程式語言為了方便我們使用，在靜態陣列的基礎上幫我們添加了一些常用的 API，例如 push、insert、remove 等方法

靜態陣列

JavaScript 並沒有提供靜態陣列的定義方式，因此下面是模擬靜態陣列的程式碼。

// 模擬：定義一個大小為 10 的靜態陣列
let arr = new Array(10);

// 使用索引賦值
arr[0] = 1;
arr[1] = 2;

// 使用索引取值
let a = arr[0];

因為陣列的記憶體空間是連續的，所以它有一個 「隨機訪問」 的能力，也就是說，只要給定一個陣列的索引，就可以在 O(1) 的時間內直接獲取對應元素的值。

增加元素

如果想要給靜態陣列增加元素，有分為幾種情況：

情況一：在陣列的末尾增加元素

由於是對索引賦值，所以在陣列結尾追加元素的時間複雜度是 O(1)。

// 大小為 10 的陣列已經裝了 4 個元素
// [0, 1, 2, 3, empty x 6]
var arr = new Array(10);
for (var i = 0; i < 4; i++) {
    arr[i] = i;
}

// 現在想在陣列末尾增加一個元素 4
// [0, 1, 2, 3, 4, empty x 5]
arr[4] = 4;

// 再在陣列末尾增加一個元素 5
// [0, 1, 2, 3, 4, 5, empty x 4]
arr[5] = 5;

情況二：在陣列的中間插入元素

需要給新元素騰出空位，才能插入新元素，這會涉及 「資料搬移」，因此在陣列中間插入元素的時間複雜度是 O(n)。

// 大小為 10 的陣列已經裝了 4 個元素
// [0, 1, 2, 3, empty x 6]
var arr = new Array(10);
for (var i = 0; i < 4; i++) {
    arr[i] = i;
}

// 在索引 2 的位置插入元素 666
// 需要把索引 2 以及之後的元素都往後移動一位，也就涉及了「資料搬移」
// [0, 1, 2, 2, 3, empty x 5]
for (var i = 4; i > 2; i--) {
    arr[i] = arr[i - 1];
}

// 現在第 3 個位置空出來了，可以插入新元素
// [0, 1, 666, 2, 3, empty x 5]
arr[2] = 666;

情況三：陣列的空間已滿

需要重新申請一塊更大的記憶體空間，把原來的資料複製過去，再插入新的元素，這就是陣列的 「擴容」 操作，陣列的擴容操作會涉及到新陣列的開闢和資料的複製，因此時間複雜度是 O(n)。

// 大小為 10 的陣列已經裝滿了
// [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
var arr = new Array(10);
for (var i = 0; i < 10; i++) {
    arr[i] = i;
}

// 現在想在陣列的末尾追加一個元素 10
// 需要先擴容陣列
// [empty × 20]
var newArr = new Array(20);
// 把原來的 10 個元素複製過去
// [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, empty × 10]
for (var i = 0; i < 10; i++) {
    newArr[i] = arr[i];
}

// 釋放舊陣列的記憶體空間
// ...

// 在新的陣列中追加新元素
// [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, empty × 9]
newArr[10] = 10;

刪除元素

這邊和新增元素一樣，也需要分為幾種情況：

情況一：刪除末尾元素

刪除陣列尾部元素的本質就是進行一次隨機訪問，時間複雜度是 O(1)。

// 大小為 10 的陣列已經裝了 5 個元素
// [0, 1, 2, 3, 4, empty × 5]
var arr = new Array(10);
for (var i = 0; i < 5; i++) {
    arr[i] = i;
}

// 刪除末尾元素，暫時用 -1 代表元素已刪除
// [0, 1, 2, 3, -1, empty × 5]
arr[4] = -1;

情況二：刪除中間元素

因為涉及到「資料搬移」，因此在陣列中間刪除元素的時間複雜度是 O(n)。

// 大小為 10 的陣列已經裝了 5 個元素
// [0, 1, 2, 3, 4, empty × 5]
var arr = new Array(10);
for (var i = 0; i < 5; i++) {
    arr[i] = i;
}

// 刪除 arr[1]
// 需要把 arr[1] 之後的元素都往前移動一位，也就涉及了「資料搬移」
// [0, 2, 3, 4, 4, empty × 5]
for (var i = 1; i < 4; i++) {
    arr[i] = arr[i + 1];
}

// 最後一個元素設為 -1 代表已刪除
// [0, 2, 3, 4, -1, empty × 5]
arr[4] = -1;

總結

靜態陣列的增刪查改操作的時間複雜度是：

增加元素：

• 在末尾增加元素：O(1)
• 在中間插入元素：O(n)

刪除元素：

• 刪除末尾元素：O(1)
• 刪除中間元素：O(n)

查詢元素：

• 給定指定索引，查詢索引對應的元素的值，時間複雜度 O(1)

修改元素：

• 給定指定索引，修改索引對應的元素的值，時間複雜度 O(1)

動態陣列

動態陣列是靜態陣列的強化版，但無法解決在中間增刪元素效率差的問題。

因為陣列隨機存取的能力源自於連續的記憶體空間，而連續的記憶體空間就不可避免地面對資料搬移和擴縮容的問題。

// 建立動態陣列
// 不用顯示指定陣列大小，它會根據實際儲存的元素數量自動縮擴容
var arr = [];

// [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
for (var i = 0; i < 10; i++) {
    // 在末尾增加元素，時間複雜度 O(1)
    arr.push(i);
}

// 在中間插入元素，時間複雜度 O(n)
// [0, 1, 666, 2, 3, 4, 5, 6, 7, 8, 9]
arr.splice(2, 0, 666);

// 在頭部插入元素，時間複雜度 O(n)
// [-1, 0, 1, 666, 2, 3, 4, 5, 6, 7, 8, 9]
arr.unshift(-1);

// 刪除末尾元素，時間複雜度 O(1)
// [-1, 0, 1, 666, 2, 3, 4, 5, 6, 7, 8]
arr.pop();

// 刪除中間元素，時間複雜度 O(n)
// [-1, 0, 666, 2, 3, 4, 5, 6, 7, 8]
arr.splice(2, 1);

// 根據索引查詢元素，時間複雜度 O(1)
var a = arr[0];

// 根據索引修改元素，時間複雜度 O(1)
arr[0] = 100;

// 根據元素值查找索引，時間複雜度 O(n)
var index = arr.indexOf(666);

學習總結

• 陣列是一塊連續的記憶體空間，可以透過索引來存取這塊記憶體空間中的元素
• 陣列有一個 「隨機訪問」 的能力，給定一個陣列的索引，就可以在 O(1) 的時間內獲取對應元素的值
• 若操作資料涉及到 「資料搬移」 和擴縮容，時間複雜度會是 O(n)