陣列是一種儲存相同資料型態元素的串列，通常占用連續的記憶體位置。
可以透過索引(Index)的計算可以取得陣列元素記憶體位置(Address)，所以存取的時間複雜度為O(1)。
陣列的插入和刪除
- 陣列若需要插入或刪除元素必須要搬移其他元素位置，所以複雜度為O(n)。
- 插入或刪除與Linked List相比效率較差
陣列維度(C#)
1.一維陣列 (One-dimensional Array)
//a1 陣列包含 10 個元素
int[] a1 = new int[10];
int[] a1 = new int[] {};
2.二維陣列 (Two-dimensional Array)
//a2陣列包含 50 (10 × 5) 個元素
int[,] a2 = new int[10, 5];
// Two-dimensional array.
int[,] array2D = new int[,] { { 1, 2 }, { 3, 4 }, { 5, 6 }, { 7, 8 } };
// The same array with dimensions specified.
int[,] array2Da = new int[4, 2] { { 1, 2 }, { 3, 4 }, { 5, 6 }, { 7, 8 } };
// A similar array with string elements.
string[,] array2Db = new string[3, 2] { { "one", "two" }, { "three", "four" },
{ "five", "six" } };
3.三維陣列 (Two-dimensional Array)
//a3 陣列包含 100 (10 × 5 × 2) 個元素
int[,,] a3 = new int[10, 5, 2];
// Three-dimensional array.
int[, ,] array3D = new int[,,] { { { 1, 2, 3 }, { 4, 5, 6 } },
{ { 7, 8, 9 }, { 10, 11, 12 } } };
// The same array with dimensions specified.
int[, ,] array3Da = new int[2, 2, 3] { { { 1, 2, 3 }, { 4, 5, 6 } },
{ { 7, 8, 9 }, { 10, 11, 12 } } };
C#陣列種類
double[] doubleArray = new double[5];
char[] charArray = new char[5];
bool[] boolArray = new bool[2];
string[] stringArray = new string[10];
陣列與Linked List比較
陣列
- 優點
- 利用索引即可存取資料，時間複雜度為O(1)
- 不須存point所以比Linked List節省記憶體
- 缺點
- 記憶體空間為連續儲存，所以當新增或刪除資料時必須移動其他元素，時間複雜度為O(n)
- 若資料常常新增或刪除比比Linked List差
- 使用時機
- 快速查詢資料，時間複雜度為O(1)
- 要求較少的記憶體空間
Linked List
- 優點
- 新增或刪除資料
- 若是在Linked List 的head新增node，只需O(1)的時間複雜度。
- 若是在特定位置新增或刪除node，需先作O(N)搜尋到特定node後，再作新增或刪除node的動作。
- Linked List 的資料數量可以是動態的，不像陣列會有預先宣告size的問題。
- 新增或刪除資料
- 缺點
- Linked List 沒有索引所以查詢特定資料，需要從頭開始找，故搜尋時間複雜度為O(N)。
- 需要額外的記憶體空間來儲存pointer。
- 使用時機
- 無法預期資料數量時，使用Linked List就沒有resize的問題。
- 需要頻繁地新增/刪除資料時。
- 不需要快速存取查詢資料時。
各種常見的資料結構複雜度分析表
Ref:
https://notfalse.net/15/array-intro
Ben Huang's Notes 
Leave a comment