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本篇技術指南以《Hello 演算法》繁體中文版「陣列與鏈結串列」章節的練習題zh-hant/docs/chapter_array_and_linkedlist/exercises.md為主體逐題講解「知識鞏固」三道思考題與「程式設計練習」兩道實戰題並結合本倉庫中 Python 與 C 語言的完整實作原始碼my_list.py、array.c、linked_list.c交叉印證。讀完本文你將能準確回答「陣列與鏈結串列在查詢、插入上的本質差異」理解動態陣列串列擴容的底層機制並獨立寫出「陣列表示的大整數加一」與「反轉單向鏈結串列」兩道經典演算法題的迭代解法。一、知識鞏固三道必考的底層概念題本節三道題分別對應本章三大核心知識點隨機訪問 vs. 順序訪問、插入操作的實作細節、以及動態陣列的擴容原理。每道題都先給出題面與參考答案再補充倉庫原始碼佐證。1. 陣列和鏈結串列怎樣找到元素題面陣列和單向鏈結串列中都按順序儲存了[A, B, C, D, E]現在要讀取第 4 個元素D陣列可以直接使用哪個索引單向鏈結串列從頭節點A開始要沿著next依次經過哪些節點當要讀取的元素位置越來越靠後時兩種結構所需的步驟會怎樣變化哪一種更適合反覆按位置讀取為什麼參考答案若索引從 0 開始第 4 個元素的索引是 3陣列可直接讀取arr[3]。單向鏈結串列必須從頭開始訪問路徑為A → B → C → D需要沿next前進 3 次。陣列可以根據首位址和索引直接定位元素按位置訪問的時間複雜度為 $O(1)$單向鏈結串列訪問第 $k$ 個節點時必須從頭節點開始沿著next前進 $k-1$ 次最壞需要 $O(n)$ 時間。這裡只比較按位置讀取不表示鏈結串列在所有操作上都更慢。源碼佐證陣列的隨機訪問體現在 array.c 的randomAccess函式中——它直接用nums[randomIndex]一步取出目標元素無須走訪而鏈結串列的access函式則在 linked_list.c 中透過for (int i 0; i index; i) head head-next;逐節點跳轉訪問第index個節點需要迴圈index次。這一對比在 linked_list.md 中被總結為「訪問元素陣列 $O(1)$ vs. 鏈結串列 $O(n)$」。2. 陣列和鏈結串列怎樣插入元素題面陣列和單向鏈結串列中都儲存了A、B、C、D現在要在B後面插入X陣列容量為 5當前狀態是[A, B, C, D, _]鏈結串列為A → B → C → D並且已經拿到了指向節點B的引用。陣列需要移動哪些元素寫出插入後的陣列。鏈結串列應按什麼順序修改X.next和B.next寫出插入後的鏈結串列。為什麼比較插入效率時要特別說明「已經拿到了節點 B 的引用」參考答案陣列要先把D向右移動一格再把C向右移動一格最後把X放入索引 2得到[A, B, X, C, D]。B.next原本指向C。應先令X.next B.next讓X指向C再令B.next X結果為A → B → X → C → D。如果先覆蓋B.next又沒有儲存原來的連線就可能找不到C。已知B的位置後鏈結串列插入只需修改兩個連線可以在 $O(1)$ 時間完成如果還要從頭查詢B查詢過程本身可能需要 $O(n)$ 時間。源碼佐證陣列的插入在 array.c 的insert函式中體現為「從尾部開始向前逐一搬移元素」/* 把索引 index 以及之後的所有元素向後移動一位 */ for (int i size - 1; i index; i--) { nums[i] nums[i - 1]; } nums[index] num;鏈結串列的插入則在 linked_list.c 的insert函式中僅修改兩條指標順序與題解完全一致void insert(ListNode *n0, ListNode *P) { ListNode *n1 n0-next; // 先保存原後繼節點 P-next n1; // 第一步新節點指向原後繼 n0-next P; // 第二步前驅指向新節點 }注意其中關鍵的第一步ListNode *n1 n0-next;——正是為了避免題目第 2 問所指出的「先覆蓋B.next導致找不到C」的陷阱。Python 版實作見 linked_list.py 的insert函式邏輯完全相同。3. 串列容量是怎樣增長的題面一個基於陣列實現的串列當前內容為[A, B, C]長度size 3容量capacity 4。規定容量不足時新陣列的容量擴大為原來的 2 倍。追加D後串列的長度和容量分別是多少是否需要擴容接著追加E時容量會變為多少需要複製幾個原有元素底層陣列的長度不可變為什麼串列的容量看起來卻可以增長參考答案D可以放入最後一個空位。此時內容為[A, B, C, D]size 4、capacity 4不需要擴容。再追加E時已經沒有空位需要建立容量為 8 的新陣列將A、B、C、D共 4 個原有元素複製過去再加入E。此時size 5、capacity 8。原來的陣列本身沒有變長。串列建立了一個更大的新陣列複製原有元素再改用新陣列作為底層儲存因此對使用者來說容量增長了。源碼佐證本題正是動態陣列串列設計的核心。在 list.md 的「串列實現」一節中明確規定了三個重點設計初始容量選 10、用變數size記錄當前元素數量、每次擴容至之前的 2 倍。Python 實作 my_list.py 完整對應def __init__(self): self._capacity: int 10 # 串列容量 self._arr: list[int] [0] * self._capacity # 陣列儲存串列元素 self._size: int 0 # 串列長度當前元素數量 self._extend_ratio: int 2 # 每次串列擴容的倍數 def add(self, num: int): if self.size() self.capacity(): # 容量滿時觸發擴容 self.extend_capacity() self._arr[self._size] num self._size 1 def extend_capacity(self): self._arr self._arr [0] * self.capacity() * (self._extend_ratio - 1) self._capacity len(self._arr)C 語言版 my_list.c 的extendCapacity則展現了更「底層」的擴容三步驟malloc新陣列 → 逐元素複製舊資料 → 釋放舊陣列並更新arr與capacity。該檔案 Driver Code 中的add迴圈正好示範了「在 i 5 時觸發擴容」的時機。需要特別留意的是 summary.md 的提醒擴容是 $O(n)$ 操作因此在串列末尾新增元素並非時時刻刻都是 $O(1)$——當新增觸發擴容時需要申請新記憶體並搬運全部元素此時時間複雜度退化为 $O(n)$。同時擴容倍數如 $\times 2$ 或 $\times 1.5$會導致串列出現空位這是串列記憶體空間浪費的主要來源。二、程式設計練習一陣列表示的大整數加一題目陣列digits從左到右儲存一個非負整數的各位數字例如[3, 0, 8]表示 308。數字 0 用[0]表示其他輸入的第一位均不為 0。請模擬一次十進位制豎式加法將這個整數增加 1並把結果仍按相同的陣列形式返回。可以直接修改digits若最前面產生新的進位可以返回一個更長的陣列。解題提示原題像做豎式加法一樣從陣列最後一位開始當前位小於 9 時加一後即可立即返回當前位等於 9 時把它改成 0若所有位都是 9需要在最前面補 1。思路解析這道題是本章「陣列遍歷與就地修改」的典型應用。關鍵洞察在於只有「9 1」才會產生進位而一旦某一位加一後不再產生進位後面的高位就完全不會受到影響可以直接返回。因此最優解是從最低位陣列末尾向左掃描一次遇到小於 9 的位立即加一返回遇到 9 就置 0 繼續向左進位若全部位都是 9如[9, 9]則需要新建長度為n 1的陣列並在首位放 1如[1, 0, 0]。整個過程只走訪陣列一遍時間複雜度為 $O(n)$除了「全 9」的特殊情形外空間複雜度為 $O(1)$。這與本章 array.md 中「走訪陣列」「就地修改元素」的操作一一對應——你可以先參考 array.c 的traverse與set式操作理解如何在連續記憶體上按索引讀寫。參考實作Pythondef plus_one(digits: list[int]) - list[int]: # 從最低位開始向高位掃描 for i in range(len(digits) - 1, -1, -1): if digits[i] 9: digits[i] 1 # 加一後無進位直接返回 return digits digits[i] 0 # 9 1 10本位歸 0繼續向左進位 # 所有位都是 9需要在最前面補 1 return [1] digits這道題即 LeetCode 經典題目66. Plus One加一也是面試中高頻考察的陣列模擬題。三、程式設計練習二反轉單向鏈結串列題目給定一個單向鏈結串列的頭節點head。每個節點包含一個值和指向下一節點的next。請使用迭代方法反轉所有節點之間的連線並返回反轉後的頭節點。要求不建立新的鏈結串列節點。解題提示原題先在紙上畫出三個相連的節點和prev、cur兩個指標改寫cur.next前必須先用nxt儲存原來的下一個節點反轉cur.next後令prev cur再令cur nxt繼續處理原鏈結串列中的下一個節點。思路解析反轉鏈結串列是本章「鏈結串列引用指標操作」的最高頻考點直接檢驗你對「節點之間靠引用連線」這一本質的理解。迭代法的核心是三指標走訪prev指向已反轉部分的新頭cur指向當前待處理節點nxt提前保存cur的原始後繼。每一步把cur.next指向prev完成一個節點的反轉再整體向右移動三個指標直到cur為空此時prev即為反轉後的新頭節點。為什麼必須先用nxt保存後繼這與前面「陣列和鏈結串列怎樣插入元素」第 2 問的陷阱同源一旦cur.next被改寫原鏈結串列的其餘部分就「失聯」了若沒有提前保存nxt迭代將無法繼續。這正是 linked_list.c 中insert/removeItem反覆出現的「先保存、再改寫」模式——只是反轉操作把這種模式用到了極致。參考實作Python不新建節點def reverse_list(head: ListNode | None) - ListNode | None: prev None cur head while cur is not None: nxt cur.next # 先保存原始後繼 cur.next prev # 反轉當前節點的指向 prev cur # 移動 prev cur nxt # 移動 cur 到原始後繼 return prev # 遍歷結束後 prev 即新頭節點這道題即 LeetCode 經典題目206. Reverse Linked List反轉鏈結串列。對比本章 linked_list.md 中insert的「兩次改指標」可以發現反轉只是把「向後連」變成「向前連」本質都是引用指標的重新定向掌握了這個思維模型鏈結串列題就不再需要死記硬背。四、本章知識地圖與延伸閱讀練習題的背後是本章完整的概念體系建議按以下脈絡複習練習對應知識點對應章節文件對應原始碼陣列隨機訪問、插入、刪除、擴容array.mdarray.c鏈結串列插入、刪除、訪問、查詢linked_list.mdlinked_list.c、linked_list.py串列動態陣列初始化與擴容機制list.mdmy_list.c、my_list.py陣列 vs. 鏈結串列效率對比、常見問答summary.md—複習時可以重點對照 summary.md 中的幾組結論性問答陣列與鏈結串列分別對應「連續空間儲存」與「分散空間儲存」兩者特性互補陣列支援 $O(1)$ 隨機訪問、快取命中率高但插入刪除是 $O(n)$ 且長度不可變鏈結串列插入刪除是 $O(1)$、長度靈活但訪問節點需要 $O(n)$ 且每個節點多存一個引用指標記憶體佔用更大。最後動手驗證建議在「程式設計練習」中plus_one可以反覆用[0]、[9]、[9, 9]、[3, 0, 8]等邊界輸入檢驗reverse_list則可以用空鏈結串列None、單節點、雙節點、多節點四種情況完整覆蓋邊界。寫完後對照本倉庫 codes 目錄下 Python、C、Java、C 等多語言的同章節實作觀察不同語言在「引用/指標」表達上的差異會對本章概念有更立體的理解。【免费下载链接】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），仅供参考