《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串列List是程式設計中最常用的線性資料結構之一它在本質上是「可動態擴容的陣列」。《Hello 演算法》繁體中文版在 zh-hant/docs/chapter_array_and_linkedlist/list.md 中從抽象概念、常用操作到動手實作動態陣列對串列進行了系統化講解。本文以該章節為主體結合倉庫內 Python、C、Java、C 等多語言原始碼深入剖析串列為何高效、如何在各語言中完成增刪查改與走訪排序並逐步拆解「初始容量、數量記錄、擴容機制」三大設計要點讓讀者既能寫出多語言可執行的串列程式碼也能真正理解其底層運作原理。串列是什麼介於陣列與鏈結串列之間的抽象串列list是一個抽象的資料結構概念它表示元素的有序集合支援元素訪問、修改、新增、刪除和走訪等操作且無須使用者考慮容量限制。串列可以基於鏈結串列或陣列實現鏈結串列天然可以看作一個串列其支援元素增刪查改操作並且可以靈活動態擴容相關講解見 鏈結串列章節。陣列也可以看作一個串列陣列同樣支援元素增刪查改但由於其長度不可變只能看作一個具有長度限制的串列。當使用陣列實現串列時長度不可變的性質會導致串列的實用性降低。原因在於我們通常無法事先確定需要儲存多少資料從而難以選擇合適的串列長度。若長度過小很可能無法滿足使用需求若長度過大則會造成記憶體空間浪費。為解決此問題可以使用動態陣列dynamic array來實現串列。它繼承了陣列的各項優點連續記憶體、隨機存取並且可以在程式執行過程中進行動態擴容。實際上許多程式語言標準庫中的串列都是基於動態陣列實現的例如程式語言動態陣列型別PythonlistJavaArrayListCvectorC#ListTGoslice切片[]TSwiftArrayJavaScript / TypeScriptArrayDartListRustVecTKotlinMutableListRubyArray在接下來的討論中我們將把「串列」和「動態陣列」視為等同的概念。值得注意的是C 語言本身並未提供內建動態陣列因此在多語言對照範例中C 語言的「串列常用操作」通常以註解形式說明其對應的動態陣列實作需要自行編寫本倉庫提供了 my_list.c 作為參考實現。串列常用操作多語言實戰本章節圍繞《Hello 演算法》串列章節的六大常用操作展開初始化、訪問元素、插入與刪除、走訪、拼接、排序。每項操作都給出代表性語言的完整可執行代碼並以表格整理全部語言的 API 對照方便快速查閱。初始化串列通常使用「無初始值」和「有初始值」兩種初始化方法# 初始化串列 # 無初始值 nums1: list[int] [] # 有初始值 nums: list[int] [1, 3, 2, 5, 4]/* 初始化串列 */ // 需注意C 中 vector 即是本文描述的 nums // 無初始值 vectorint nums1; // 有初始值 vectorint nums { 1, 3, 2, 5, 4 };/* 初始化串列 */ // 無初始值 ListInteger nums1 new ArrayList(); // 有初始值注意陣列的元素型別需為 int[] 的包裝類別 Integer[] Integer[] numbers new Integer[] { 1, 3, 2, 5, 4 }; ListInteger nums new ArrayList(Arrays.asList(numbers));各語言初始化方式對照如下語言無初始值有初始值Pythonnums1: list[int] []nums [1, 3, 2, 5, 4]Cvectorint nums1;vectorint nums { 1, 3, 2, 5, 4 };JavaListInteger nums1 new ArrayList();new ArrayList(Arrays.asList(numbers))C#Listint nums1 [];Listint nums [.. numbers];Gonums1 : []int{}nums : []int{1, 3, 2, 5, 4}Swiftlet nums1: [Int] []var nums [1, 3, 2, 5, 4]JS / TSconst nums1 []/const nums1: number[] []const nums [1, 3, 2, 5, 4]DartListint nums1 [];Listint nums [1, 3, 2, 5, 4];Rustlet nums1: Veci32 Vec::new();let nums: Veci32 vec![1, 3, 2, 5, 4];Kotlinvar nums1 listOfInt()var nums numbers.toMutableList()Rubynums1 []nums [1, 3, 2, 5, 4]執行驗證完整的驅動代碼位於 codes/python/chapter_array_and_linkedlist/list.py運行後會逐步列印每次操作後的nums內容該章節還提供了 Python Tutor 視覺化執行連結見 pythontutor 目錄可逐行觀察記憶體中元素的變化。訪問與更新元素串列本質上是陣列因此可以在 $O(1)$ 時間內訪問和更新元素效率很高# 訪問元素 num: int nums[1] # 訪問索引 1 處的元素 # 更新元素 nums[1] 0 # 將索引 1 處的元素更新為 0/* 訪問元素 */ int num nums.get(1); // 訪問索引 1 處的元素 /* 更新元素 */ nums.set(1, 0); // 將索引 1 處的元素更新為 0各語言訪問更新 API 對照語言訪問元素更新元素Python / C / C# / Go / Swift / JS / TS / Dart / Rust / Kotlin / Rubynums[1]下標運算子nums[1] 0Javanums.get(1)nums.set(1, 0)C未提供內建動態陣列需自訂get(nums, index)需自訂set(nums, index, num)之所以能做到 $O(1)$ 訪問是因為陣列元素儲存在連續記憶體中可透過「元素記憶體位址 陣列記憶體位址 元素長度 × 元素索引」直接計算出目標位址無須從頭走訪。插入與刪除元素相較於陣列串列可以自由地新增與刪除元素。在串列尾部新增元素的時間複雜度為 $O(1)$攤還意義下偶爾觸發擴容時為 $O(n)$見後文但在中間插入和刪除元素的效率仍與陣列相同時間複雜度為 $O(n)$——因為需要將後續元素整體向後或向前移動一位# 清空串列 nums.clear() # 在尾部新增元素 nums.append(1) nums.append(3) nums.append(2) nums.append(5) nums.append(4) # 在中間插入元素 nums.insert(3, 6) # 在索引 3 處插入數字 6 # 刪除元素 nums.pop(3) # 刪除索引 3 處的元素/* 清空串列 */ nums.clear(); /* 在尾部新增元素 */ nums.push_back(1); nums.push_back(3); nums.push_back(2); nums.push_back(5); nums.push_back(4); /* 在中間插入元素 */ nums.insert(nums.begin() 3, 6); // 在索引 3 處插入數字 6 /* 刪除元素 */ nums.erase(nums.begin() 3); // 刪除索引 3 處的元素各語言增刪 API 對照語言尾部新增中間插入刪除Pythonnums.append(x)nums.insert(i, x)nums.pop(i)Cnums.push_back(x)nums.insert(begin()i, x)nums.erase(begin()i)Javanums.add(x)nums.add(i, x)nums.remove(i)C#nums.Add(x)nums.Insert(i, x)nums.RemoveAt(i)Gonums append(nums, x)append(nums[:3], append([]int{6}, nums[3:]...)...)append(nums[:3], nums[4:]...)Swiftnums.append(x)nums.insert(x, at: i)nums.remove(at: i)JS / TSnums.push(x)nums.splice(3, 0, 6)nums.splice(3, 1)Dartnums.add(x)nums.insert(i, x)nums.removeAt(i)Rustnums.push(x)nums.insert(i, x)nums.remove(i)Kotlinnums.add(x)nums.add(i, x)nums.remove(i)Rubynums xnums.insert(i, x)nums.delete_at(i)注意 Go 的特殊性Go 的 slice 以append進行尾部新增中間插入與刪除需要透過切片重組實現在底層同樣涉及元素搬移時間複雜度仍是 $O(n)$。走訪串列與陣列一樣串列可以根據索引走訪也可以直接走訪各元素。兩種方式整體時間複雜度均為 $O(n)$# 透過索引走訪串列 count 0 for i in range(len(nums)): count nums[i] # 直接走訪串列元素 for num in nums: count num/* 透過索引走訪串列 */ count : 0 for i : 0; i len(nums); i { count nums[i] } /* 直接走訪串列元素 */ count 0 for _, num : range nums { count num }拼接串列給定一個新串列nums1可以將其拼接到原串列的尾部。拼接操作需要把nums1的所有元素逐一複製到nums尾部因此時間複雜度為 $O(m)$$m$ 為nums1的長度# 拼接兩個串列 nums1: list[int] [6, 8, 7, 10, 9] nums nums1 # 將串列 nums1 拼接到 nums 之後各語言拼接 API 對照語言拼接操作Pythonnums nums1Cnums.insert(nums.end(), nums1.begin(), nums1.end());Javanums.addAll(nums1);C#nums.AddRange(nums1);Gonums append(nums, nums1...)Swiftnums.append(contentsOf: nums1)JS / TSnums.push(...nums1)Dartnums.addAll(nums1);Rustnums.extend(nums1);Kotlinnums.addAll(nums1);Rubynums nums1排序串列完成串列排序後便可以使用在陣列類演算法題中經常考查的「二分搜尋」和「雙指標」演算法相關內容可參考 搜尋章節# 排序串列 nums.sort() # 排序後串列元素從小到大排列各語言排序 API 對照語言排序操作說明Pythonnums.sort()原地升序排序Csort(nums.begin(), nums.end());需包含algorithmJavaCollections.sort(nums);原地升序排序C#nums.Sort();原地升序排序Gosort.Ints(nums)需匯入sort套件Swiftnums.sort()原地升序排序JS / TSnums.sort((a, b) a - b);必須傳入比較函式否則按字典序排序Dartnums.sort();原地升序排序Rustnums.sort();原地升序排序Kotlinnums.sort()原地升序排序Rubynums nums.sort { \|a, b\| a b }透過區塊指定比較規則實作細節JavaScript / TypeScript 的Array.prototype.sort()預設將元素轉為字串後按字典序排序因此對數值陣列必須傳入(a, b) a - b比較函式才能得到正確的數值升序結果這是與其他語言差異最大的地方。操作時間複雜度一覽綜合以上操作串列動態陣列各操作的時間複雜度總結如下操作時間複雜度說明訪問元素$O(1)$下標隨機訪問更新元素$O(1)$下標賦值尾部新增$O(1)$ 攤還容量充足時 $O(1)$觸發擴容時 $O(n)$中間插入$O(n)$需將後續元素向後移動刪除元素$O(n)$需將後續元素向前移動走訪串列$O(n)$索引走訪或直接走訪拼接串列$O(m)$$m$ 為被拼接串列的長度排序串列$O(n \log n)$由排序演算法決定串列實現手寫一個動態陣列 MyList許多程式語言內建了串列例如 Java、C、Python 等。它們的實現比較複雜各個參數的設定也非常考究例如初始容量、擴容倍數等。為了加深對串列工作原理的理解《Hello 演算法》在章節末尾引導讀者從零實現一個簡易版串列包括以下三個重點設計初始容量選取一個合理的陣列初始容量。本章示例選擇10作為初始容量。數量記錄宣告一個變數size用於記錄串列當前元素數量並隨著元素插入和刪除即時更新。根據此變數可以定位串列尾部以及判斷是否需要擴容。擴容機制若插入元素時串列容量已滿則需要進行擴容。先根據擴容倍數建立一個更大的陣列再將當前陣列的所有元素依次移動至新陣列。本章示例規定每次將陣列擴容至之前的 2 倍。以下以 Python 實現為例完整講解 codes/python/chapter_array_and_linkedlist/my_list.py 的設計本章其他語言版本對應C my_list.cpp、Java my_list.java、C my_list.c、Go my_list.go。類別結構與構造方法class MyList: 列表类 def __init__(self): 构造方法 self._capacity: int 10 # 列表容量 self._arr: list[int] [0] * self._capacity # 数组存储列表元素 self._size: int 0 # 列表长度当前元素数量 self._extend_ratio: int 2 # 每次列表扩容的倍数構造方法一次性分配capacity 10的底層陣列並將size初始化為 0。這裡區分兩個易混淆的概念容量capacity底層陣列實際分配的空間大小即最多能容納多少元素長度size串列當前實際擁有的元素數量即「已用」空間。在 C 版本中這對應arrCapacity與arrSize兩個私有成員見 my_list.cpp在 C 版本中則封裝在MyList結構體內見 my_list.c。訪問與更新元素O(1)def get(self, index: int) - int: 访问元素 # 索引如果越界则抛出异常下同 if index 0 or index self._size: raise IndexError(索引越界) return self._arr[index] def set(self, num: int, index: int): 更新元素 if index 0 or index self._size: raise IndexError(索引越界) self._arr[index] numget與set均為 $O(1)$ 操作並且都做了索引越界檢查。不同語言採用的越界處理方式略有差異Python 拋出IndexErrorC 拋出out_of_range見 my_list.cppJava 拋出IndexOutOfBoundsException見 my_list.java而 C 語言則使用assert斷言見 my_list.c。尾部新增與擴容觸發攤還 O(1)def add(self, num: int): 在尾部添加元素 # 元素数量超出容量时触发扩容机制 if self.size() self.capacity(): self.extend_capacity() self._arr[self._size] num self._size 1add是理解動態陣列的核心先檢查size capacity若容量已滿則觸發extend_capacity()擴容然後把新元素寫入_arr[_size]位置並遞增size。這就是攤還 $O(1)$的由來——絕大多數情況下尾部新增是 $O(1)$僅在容量耗盡的少數時刻需要 $O(n)$ 的搬移成本平均攤還後仍為常數時間。中間插入與刪除O(n)def insert(self, num: int, index: int): 在中间插入元素 if index 0 or index self._size: raise IndexError(索引越界) # 元素数量超出容量时触发扩容机制 if self._size self.capacity(): self.extend_capacity() # 将索引 index 以及之后的元素都向后移动一位 for j in range(self._size - 1, index - 1, -1): self._arr[j 1] self._arr[j] self._arr[index] num # 更新元素数量 self._size 1 def remove(self, index: int) - int: 删除元素 if index 0 or index self._size: raise IndexError(索引越界) num self._arr[index] # 将索引 index 之后的元素都向前移动一位 for j in range(index, self._size - 1): self._arr[j] self._arr[j 1] # 更新元素数量 self._size - 1 # 返回被删除的元素 return num中間插入與刪除都需要搬移後續元素因此時間複雜度為 $O(n)$insert從尾部開始向前走訪把index及其之後的元素全部向後移動一位騰出空位後寫入新元素remove從index開始向後走訪把後續元素全部向前移動一位覆蓋被刪除元素並返回被刪除的值。在 C 語言的實現中刪除方法被命名為removeItem而非remove因為標準標頭檔stdio.h已佔用remove這個識別字見 my_list.c 的註解這是一個語言層面的實作細節。擴容機制2 倍擴容def extend_capacity(self): 列表扩容 # 新建一个长度为原数组 _extend_ratio 倍的新数组并将原数组复制到新数组 self._arr self._arr [0] * self.capacity() * (self._extend_ratio - 1) # 更新列表容量 self._capacity len(self._arr)擴容的完整流程是分配新空間建立一個長度為原容量 $\times$ 擴容倍數的新陣列。Python 中直接以self._arr [0] * 容量 * (倍數 - 1)串接生成C 中透過new int[newCapacity]分配見 my_list.cppC 中透過malloc分配見 my_list.c。搬移資料將原陣列的所有元素依序複製到新陣列C 和 C 需手動迴圈複製Java 可直接使用Arrays.copyOf見 my_list.java。釋放舊空間C/C 需手動delete[]/free舊陣列否則會造成記憶體洩漏Java、Python 等由垃圾回收機制處理。更新容量將capacity更新為新陣列的長度。之所以選擇「倍增」而非「每次 1」是為了減少擴容次數若每次只增加固定大小擴容的總搬移成本會累積為 $O(n^2)$而倍增策略使搬移成本攤還後僅為 $O(1)$ 每次新增。這也正是文章開頭所述「標準庫參數設定非常考究」的底層原因——初始容量與擴容倍數直接決定了記憶體浪費與擴容頻率的平衡。用 Driver Code 驗證執行結果my_list.py的驅動代碼完整演練了上述所有方法並特意測試了擴容機制Driver Code if __name__ __main__: # 初始化列表 nums MyList() # 在尾部添加元素 nums.add(1) nums.add(3) nums.add(2) nums.add(5) nums.add(4) print(f列表 nums {nums.to_array()} 容量 {nums.capacity()} 长度 {nums.size()}) # 在中间插入元素 nums.insert(6, index3) print(在索引 3 处插入数字 6 得到 nums , nums.to_array()) # 删除元素 nums.remove(3) print(删除索引 3 处的元素得到 nums , nums.to_array()) # 访问元素 num nums.get(1) print(访问索引 1 处的元素得到 num , num) # 更新元素 nums.set(0, 1) print(将索引 1 处的元素更新为 0 得到 nums , nums.to_array()) # 测试扩容机制 for i in range(10): # 在 i 5 时列表长度将超出列表容量此时触发扩容机制 nums.add(i) print(f扩容后的列表 {nums.to_array()} 容量 {nums.capacity()} 长度 {nums.size()})運行後可以看到初始容量為 10、長度為 5在連續新增 10 個元素、第 6 次新增時長度超出容量觸發擴容後容量變為 20完美印證了 2 倍擴容機制。該流程亦可透過 pythontutor 視覺化代碼 逐行觀察。效能與記憶體取捨串列的出現大幅提高了陣列的實用性但也帶來了一定的代價章節小結 中總結了幾個關鍵點記憶體空間浪費主要有兩方面含義。一方面串列都會設定一個初始長度我們不一定需要用這麼多另一方面為了防止頻繁擴容擴容一般會乘以一個係數例如 $\times 1.5$ 或 $\times 2$這樣一來會出現很多空位通常不能完全填滿。尾部新增並非時時刻刻都是 $O(1)$如果新增元素時超出串列長度需要先擴容申請新記憶體並搬運所有元素此時時間複雜度是 $O(n)$只有攤還意義下才為 $O(1)$。與鏈結串列的對比陣列以及基於動態陣列的串列由於資料連續存放、快取命中率高通常比鏈結串列更高效而鏈結串列在記憶體使用上更加靈活。在選擇資料結構時應根據具體需求和場景做出恰當選擇例如 C 中std::list雙向鏈結串列通常比std::vector更佔空間且快取不友好因此演算法實作中往往更青睞陣列。常見問題精選QA本章節末尾的小結中針對串列整理了幾個高頻疑問這裡選取與串列最相關的三個Q在串列末尾新增元素是否時時刻刻都為 $O(1)$不是。如果新增元素時超出串列長度則需要先擴容串列再新增。系統會申請一塊新的記憶體並將原串列的所有元素搬運過去這時候時間複雜度就會是 $O(n)$。Q「串列的出現極大地提高了陣列的實用性但可能導致部分記憶體空間浪費」這裡的空間浪費是指額外增加的變數如容量、長度、擴容倍數所佔的記憶體嗎不完全是。這裡的空間浪費主要有兩方面含義一方面串列都會設定一個初始長度我們不一定需要用這麼多另一方面為了防止頻繁擴容擴容一般會乘以一個係數比如 $\times 1.5$這樣一來也會出現很多空位我們通常不能完全填滿它們。Q在 Python 中初始化n [1, 2, 3]後這 3 個元素的位址是相連的但是初始化m [2, 1, 3]會發現它們每個元素的 id 並不是連續的而是分別跟n中的相同。這些元素的位址不連續那麼m還是陣列嗎是的m仍然是陣列。與許多語言不同Python 中的數字也被包裝為物件串列中儲存的不是數字本身而是對數字的引用。因此兩個陣列中的相同數字擁有同一個 id且這些數字的記憶體位址無須連續。給定一個串列索引仍然可以在 $O(1)$ 時間內獲取對應的引用因為陣列本身儲存的引用是連續的。這也提醒我們Python 串列中儲存可變物件如串列、字典時修改某個元素會直接改變該物件本身所有引用該物件的元素都會產生相同變化而整數是不可變物件修改元素實際上是切換為另一個物件的引用。小結串列是程式設計中最基礎也最常用的資料結構之一理解它需要把握三個層次抽象概念串列是支援增刪查改的元素有序集合基於動態陣列實現後既保留了陣列隨機訪問的高效又獲得了靈活調整長度的能力多語言操作各語言標準庫Pythonlist、JavaArrayList、Cvector、C#List、RustVec等提供的 API 形態各異但底層原理一致——本文的 API 對照表可供日常開發快速查閱底層實現手寫MyList的三個設計要點初始容量 10、size數量記錄、2 倍擴容機制揭示了動態陣列的核心奧秘也解釋了為何尾部新增是攤還 $O(1)$、中間插入與刪除是 $O(n)$。若想進一步鞏固可繼續閱讀同章節的 陣列、鏈結串列 與 小結含完整 QA並對照多語言原始碼運行驗證將「知其然」升級為「知其所以然」。【免费下载链接】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），仅供参考