Hello 算法陣列Array資料結構完全指南 —— 連續記憶體、隨機訪問與 O(n) 增刪的取捨之道【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo陣列是《Hello 算法》中第一種正式登場的線性資料結構它將相同型別的元素存放在連續的記憶體空間中用「索引index」定位元素是理解後續堆疊、佇列、雜湊表、圖等所有複雜資料結構的基石。本文以 zh-hant/docs/chapter_array_and_linkedlist/array.md 為主體結合倉庫內 Python、C、Java、Go 等多語言實作原始碼完整講解陣列的初始化、O(1) 隨機訪問、O(n) 插入刪除、走訪、線性查找與擴容機制並剖析其空間效率、快取區域性等優勢與長度不可變的局限最後總結陣列在演算法與真實系統中的典型應用。讀完本文你將掌握陣列從底層記憶體佈局到高階應用的完整知識鏈並能直接閱讀 zh-hant/codes 下的可執行範例親手驗證。陣列是什麼定義與儲存方式陣列array是一種線性資料結構其將相同型別的元素儲存在連續的記憶體空間中。我們將元素在陣列中的位置稱為該元素的索引index如上圖所示陣列[1, 3, 2, 5, 4]的 5 個元素被依序存放在記憶體位址00、04、08、12、16的連續空間中索引從0到4。兩個關鍵特性構成了陣列的「先驗資訊」元素型別相同每個元素佔用的位元組數一致這是記憶體位址可以透過公式直接推算的前提儲存空間連續相鄰元素在記憶體中「緊挨著」中間沒有任何空隙這也是插入、刪除需要搬移大量資料的根本原因。這兩個特性是後面所有操作隨機訪問、插入、刪除、擴容效率分析的出發點。初始化陣列兩種方式與 13 種語言寫法初始化陣列有兩種方式無初始值與給定初始值。在未指定初始值的情況下大多數程式語言會將陣列元素初始化為0。以下完整整理自《Hello 算法》倉庫中各語言對應的 array.py、array.cpp、array.java、array.cs、array.go、array.swift、array.js、array.ts、array.dart、array.rs、array.c、array.kt 與 array.rb 的初始化程式碼 Pythonpython titlearray.py # 初始化陣列 arr: list[int] [0] * 5 # [ 0, 0, 0, 0, 0 ] nums: list[int] [1, 3, 2, 5, 4] Ccpp titlearray.cpp /* 初始化陣列 */ // 儲存在堆疊上 int arr[5]; int nums[5] { 1, 3, 2, 5, 4 }; // 儲存在堆積上需要手動釋放空間 int* arr1 new int[5]; int* nums1 new int[5] { 1, 3, 2, 5, 4 }; Javajava titlearray.java /* 初始化陣列 */ int[] arr new int[5]; // { 0, 0, 0, 0, 0 } int[] nums { 1, 3, 2, 5, 4 }; C#csharp titlearray.cs /* 初始化陣列 */ int[] arr new int[5]; // [ 0, 0, 0, 0, 0 ] int[] nums [1, 3, 2, 5, 4]; Gogo titlearray.go /* 初始化陣列 */ var arr [5]int // 在 Go 中指定長度時[5]int為陣列不指定長度時[]int為切片 // 由於 Go 的陣列被設計為在編譯期確定長度因此只能使用常數來指定長度 // 為了方便實作擴容 extend() 方法以下將切片Slice看作陣列Array nums : []int{1, 3, 2, 5, 4} Swiftswift titlearray.swift /* 初始化陣列 */ let arr Array(repeating: 0, count: 5) // [0, 0, 0, 0, 0] let nums [1, 3, 2, 5, 4] JSjavascript titlearray.js /* 初始化陣列 */ var arr new Array(5).fill(0); var nums [1, 3, 2, 5, 4]; TStypescript titlearray.ts /* 初始化陣列 */ let arr: number[] new Array(5).fill(0); let nums: number[] [1, 3, 2, 5, 4]; Dartdart titlearray.dart /* 初始化陣列 */ Listint arr List.filled(5, 0); // [0, 0, 0, 0, 0] Listint nums [1, 3, 2, 5, 4]; Rustrust titlearray.rs /* 初始化陣列 */ let arr: [i32; 5] [0; 5]; // [0, 0, 0, 0, 0] let slice: [i32] [0; 5]; // 在 Rust 中指定長度時[i32; 5]為陣列不指定長度時[i32]為切片 // 由於 Rust 的陣列被設計為在編譯期確定長度因此只能使用常數來指定長度 // Vector 是 Rust 一般情況下用作動態陣列的型別 // 為了方便實作擴容 extend() 方法以下將 vector 看作陣列array let nums: Veci32 vec![1, 3, 2, 5, 4]; Cc titlearray.c /* 初始化陣列 */ int arr[5] { 0 }; // { 0, 0, 0, 0, 0 } int nums[5] { 1, 3, 2, 5, 4 }; Kotlinkotlin titlearray.kt /* 初始化陣列 */ var arr IntArray(5) // { 0, 0, 0, 0, 0 } var nums intArrayOf(1, 3, 2, 5, 4) Rubyruby titlearray.rb # 初始化陣列 arr Array.new(5, 0) nums [1, 3, 2, 5, 4] 從以上對比可以歸納出三個實務要點靜態語言C、C、Rust、Go區分「固定長度陣列」與「動態容器」C 語言透過new int[5]在堆積上配置記憶體時必須手動free釋放見 array.c 的main末尾Rust 以[i32; 5]表示陣列、Veci32表示動態陣列、[i32]表示切片Go 則以[5]int與[]int區分陣列與切片且陣列長度須為編譯期常數。動態語言Python、JavaScript、Ruby、Dart的「陣列」本質上是可擴容的容器例如 Python 的list與 JS 的Array都是動態陣列但為了教學清晰array.py 的extend()函式仍刻意將list視為長度不可變的陣列來示範擴容原理。初始化為0是通用預設Java、C#、Kotlin、C、Go 等語言的「無初始值」陣列元素自動為 0這在數值統計、DP 表格等場景中非常方便。訪問元素O(1) 隨機訪問與記憶體位址公式陣列元素被儲存在連續的記憶體空間中這意味著計算陣列元素的記憶體位址非常容易。給定陣列記憶體位址首元素記憶體位址和某個元素的索引可以使用下圖所示的公式計算得到該元素的記憶體位址從而直接訪問該元素以上圖為例陣列首元素位址為00元素長度為4位元組計算索引3處元素的位址00 4 × 3 12正好對應值為5的元素。觀察上圖可以發現陣列首個元素的索引為0這看似反直覺從1開始計數更自然但從位址計算公式的角度看索引本質上是記憶體位址的偏移量——首個元素的位址偏移量是0因此它的索引為0是合理的。在陣列中訪問元素非常高效我們可以在 $O(1)$ 時間內隨機訪問陣列中的任意一個元素。對應的randomAccess函式實作如下Python 版見 array.pydef random_access(nums: list[int]) - int: 隨機訪問元素 # 在區間 [0, len(nums)-1] 中隨機抽取一個數字 random_index random.randint(0, len(nums) - 1) # 獲取並返回隨機元素 random_num nums[random_index] return random_numC 語言版array.c則透過rand() % size產生隨機索引Java 版array.java使用ThreadLocalRandom.current().nextInt(0, nums.length)產生半開區間[0, nums.length)內的隨機索引。無論哪種語言訪問操作本身只需一次記憶體位址計算加一次取值與陣列長度無關這就是 $O(1)$ 的由來。插入元素尾部元素必然「丟失」陣列元素在記憶體中是「緊挨著的」它們之間沒有空間再存放任何資料。如下圖所示如果想在陣列中間插入一個元素則需要將該元素之後的所有元素都向後移動一位之後再把元素賦值給該索引值得注意的是由於陣列的長度是固定的因此插入一個元素必定會導致陣列尾部元素「丟失」上圖中末尾的佔位0被擠出。這個問題的解決方案動態擴容在「串列」章節中討論對應文件為 zh-hant/docs/chapter_array_and_linkedlist/list.md。insert函式的實作Python 版見 array.pydef insert(nums: list[int], num: int, index: int): 在陣列的索引 index 處插入元素 num # 把索引 index 以及之後的所有元素向後移動一位 for i in range(len(nums) - 1, index, -1): nums[i] nums[i - 1] # 將 num 賦給 index 處的元素 nums[index] num注意迴圈方向是從尾部向前移動len(nums)-1遞減到index1這樣才能避免前面的元素覆蓋尚未搬移的後方元素。C 語言版array.c需要額外傳入陣列長度size參數因為 C 陣列不攜帶長度資訊Go 版array.go的寫法與 Python 幾乎一致可見這個「由後往前搬移」的模式是跨語言通用的。刪除元素末尾元素變「無意義」同理若想刪除索引i處的元素則需要把索引i之後的元素都向前移動一位請注意刪除元素完成後原先末尾的元素變得「無意義」了所以我們無須特意去修改它上圖中末尾殘留的4就是無意義佔位。remove函式實作Python 版見 array.pydef remove(nums: list[int], index: int): 刪除索引 index 處的元素 # 把索引 index 之後的所有元素向前移動一位 for i in range(index, len(nums) - 1): nums[i] nums[i 1]這裡的迴圈方向與插入相反是從前往後搬移index遞增到len(nums)-2。一個有趣的實作細節C 語言版array.c將函式命名為removeItem因為stdio.h已佔用了remove這個關鍵字這是閱讀 C 原始碼時需要留意的命名差異。陣列常用操作的總體複雜度綜合以上分析陣列的插入與刪除操作有以下缺點時間複雜度高陣列的插入和刪除的平均時間複雜度均為 $O(n)$其中 $n$ 為陣列長度丟失元素由於陣列的長度不可變因此在插入元素後超出陣列長度範圍的元素會丟失記憶體浪費我們可以初始化一個比較長的陣列只用前面一部分這樣在插入資料時丟失的末尾元素都是「無意義」的但這樣做會造成部分記憶體空間浪費。將陣列六大基本操作的複雜度匯總如下這是面試與工程選型時最常被引用的結論操作平均時間複雜度是否依賴陣列長度隨機訪問random_access$O(1)$否固定時間插入元素insert$O(n)$是需搬移後續元素刪除元素remove$O(n)$是需搬移後續元素走訪陣列traverse$O(n)$是需逐個訪問查詢元素find$O(n)$是線性查找擴容陣列extend$O(n)$是需複製全部元素走訪陣列三種走訪方式在大多數程式語言中我們既可以透過索引走訪陣列也可以直接走訪獲取陣列中的每個元素。traverse函式實作Python 版見 array.pydef traverse(nums: list[int]): 走訪陣列 count 0 # 透過索引走訪陣列 for i in range(len(nums)): count nums[i] # 直接走訪陣列元素 for num in nums: count num # 同時走訪資料索引和元素 for i, num in enumerate(nums): count nums[i] count num三種方式各有適用場景索引走訪需要知道陣列長度且能拿到下標適合需要同時操作多個位置如雙指標、快慢指標的演算法直接走訪語法最簡潔適合只讀取每個元素的場合同時走訪索引與元素Python 的enumerate、Go 的for i, num : range見 array.go則兼顧兩者在需要同時知道下標與值時最方便。三種方式的時間複雜度均為 $O(n)$。查詢元素線性查找在陣列中查詢指定元素需要走訪陣列每輪判斷元素值是否匹配若匹配則輸出對應索引。因為陣列是線性資料結構所以上述查詢操作被稱為「線性查找」。find函式實作Python 版見 array.pydef find(nums: list[int], target: int) - int: 在陣列中查詢指定元素 for i in range(len(nums)): if nums[i] target: return i return -1兩個實作細節值得注意一是查詢到第一個匹配即返回因此重複元素只會返回最小索引二是查詢失敗時返回-1作為哨兵值因為-1不是合法索引這是 Carray.c、Javaarray.java、Goarray.go等語言中約定俗成的做法。線性查找的平均時間複雜度為 $O(n)$若陣列已排序則可以改用二分搜尋將複雜度降為 $O(\log n)$見 zh-hant/docs/chapter_searching/binary_search.md。擴容陣列重建更大陣列並複製在複雜的系統環境中程式難以保證陣列之後的記憶體空間是可用的從而無法安全地擴展陣列容量。因此在大多數程式語言中陣列的長度是不可變的。如果我們希望擴容陣列則需重新建立一個更大的陣列然後把原陣列元素依次複製到新陣列。這是一個 $O(n)$ 的操作在陣列很大的情況下非常耗時。extend函式實作Python 版見 array.pydef extend(nums: list[int], enlarge: int) - list[int]: 擴展陣列長度 # 初始化一個擴展長度後的陣列 res [0] * (len(nums) enlarge) # 將原陣列中的所有元素複製到新陣列 for i in range(len(nums)): res[i] nums[i] # 返回擴展後的新陣列 return resC 語言版array.c更能體現「手動管理記憶體」的細節先以malloc分配size enlarge個int的空間複製原元素後還要顯式將擴展出的空間初始化為0最後由呼叫方在main中透過free(res)釋放記憶體。Java 版array.java則依賴 GC 自動回收舊陣列。需要強調的是擴容的成本極高$O(n)$ 的時間與空間開銷這正是實際工程中普遍採用「動態陣列」的原因——例如 Python 的list、Java 的ArrayList會在容量不足時以倍增策略擴容均攤下來每次追加元素的成本接近 $O(1)$。這一設計的詳細討論參見串列章節 zh-hant/docs/chapter_array_and_linkedlist/list.md。陣列的優點與侷限性陣列儲存在連續的記憶體空間內且元素型別相同。這種做法包含豐富的先驗資訊系統可以利用這些資訊來最佳化資料結構的操作效率。優點空間效率高陣列為資料分配了連續的記憶體塊無須額外的結構開銷不像鏈結串列每個節點還要儲存指標支援隨機訪問陣列允許在 $O(1)$ 時間內訪問任何元素這是鏈結串列無法比擬的後者訪問第 $i$ 個元素需要 $O(n)$ 走訪見 zh-hant/docs/chapter_array_and_linkedlist/linked_list.md快取區域性當訪問陣列元素時計算機不僅會載入它還會快取其周圍的其他資料從而藉助高速快取CPU Cache來提升後續操作的執行速度——這是陣列在實際效能上往往遠勝鏈結串列的重要原因。侷限性插入與刪除效率低當陣列中元素較多時插入與刪除操作需要移動大量的元素平均時間複雜度為 $O(n)$長度不可變陣列在初始化後長度就固定了擴容陣列需要將所有資料複製到新陣列開銷很大空間浪費如果陣列分配的大小超過實際所需那麼多餘的空間就被浪費了。陣列的典型應用陣列是一種基礎且常見的資料結構既頻繁應用在各類演算法之中也可用於實現各種複雜資料結構。隨機訪問如果我們想隨機抽取一些樣本那麼可以用陣列儲存並生成一個隨機序列根據索引實現隨機抽樣——本文random_access函式就是這一場景的最小示範排序和搜尋陣列是排序和搜尋演算法最常用的資料結構。快速排序、合併排序、二分搜尋等都主要在陣列上進行對應實作見 zh-hant/codes/chapter_sorting 與 zh-hant/codes/chapter_searching 目錄下的各語言原始碼查詢表當需要快速查詢一個元素或其對應關係時可以使用陣列作為查詢表。假如我們想實現字元到 ASCII 碼的對映則可以將字元的 ASCII 碼值作為索引對應的元素存放在陣列中的對應位置機器學習神經網路中大量使用了向量、矩陣、張量之間的線性代數運算這些資料都是以陣列的形式構建的。陣列是神經網路程式設計中最常使用的資料結構資料結構實現陣列可以用於實現堆疊、佇列、雜湊表、堆積、圖等資料結構。例如圖的鄰接矩陣表示實際上是一個二維陣列見 zh-hant/codes/chapter_graph 中的graph_adjacency_matrix系列原始碼用陣列實作的佇列與堆疊則見 zh-hant/codes/chapter_stack_and_queue 中的array_queue與array_stack。動手驗證閱讀並執行倉庫範例如果你想親眼驗證以上所有操作可以直接閱讀各語言的array範例原始碼其Driver Codemain函式會依序示範初始化、隨機訪問、擴容、插入、刪除、走訪與查找的完整流程與輸出Pythonzh-hant/codes/python/chapter_array_and_linkedlist/array.pyCzh-hant/codes/c/chapter_array_and_linkedlist/array.cJavazh-hant/codes/java/chapter_array_and_linkedlist/array.javaGozh-hant/codes/go/chapter_array_and_linkedlist/array.go其餘語言C、C#、Swift、JS、TS、Dart、Rust、Kotlin、Ruby、Zig見 zh-hant/codes 對應語言目錄下的chapter_array_and_linkedlist/array.*此外倉庫還提供了 Python Tutor 視覺化執行腳本 zh-hant/codes/pythontutor/chapter_array_and_linkedlist/array.md可以逐行觀察陣列初始化與各操作的執行過程特別適合初學者建立直觀的記憶體模型。小結陣列以「連續記憶體 相同型別」換來了 $O(1)$ 隨機訪問與出色的快取區域性代價是 $O(n)$ 的插入、刪除與擴容成本。理解「索引即記憶體位址偏移量」是掌握陣列的本質鑰匙而「插入尾部丟失、刪除末尾殘留」的現象則時刻提醒我們陣列長度不可變的特性。在《Hello 算法》的後續章節中陣列將作為基石支撐起串列、堆疊、佇列、雜湊表、堆積與圖等更複雜的資料結構——這正是把這門「最基礎」的資料結構學紮實的最大價值。【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考