https://leetcode.cn/problems/design-linked-list/description/
一、題目分析
????????
你可以選擇使用單鏈表或者雙鏈表，設計并實現自己的鏈表。
單鏈表中的節點應該具備兩個屬性：val?和?next?。val?是當前節點的值，next?是指向下一個節點的指針/引用。
如果是雙向鏈表，則還需要屬性?prev?以指示鏈表中的上一個節點。假設鏈表中的所有節點下標從?0?開始。
實現?MyLinkedList?類：
MyLinkedList()?初始化?MyLinkedList?對象。int get(int index)?獲取鏈表中下標為?index?的節點的值。如果下標無效，則返回?-1?。void addAtHead(int val)?將一個值為?val?的節點插入到鏈表中第一個元素之前。在插入完成后，新節點會成為鏈表的第一個節點。void addAtTail(int val)?將一個值為?val?的節點追加到鏈表中作為鏈表的最后一個元素。void addAtIndex(int index, int val)?將一個值為?val?的節點插入到鏈表中下標為?index?的節點之前。如果?index?等于鏈表的長度，那么該節點會被追加到鏈表的末尾。如果?index?比長度更大，該節點將?不會插入?到鏈表中。void deleteAtIndex(int index)?如果下標有效，則刪除鏈表中下標為?index?的節點。
示例：
輸入 ["MyLinkedList", "addAtHead", "addAtTail", "addAtIndex", "get", "deleteAtIndex", "get"] [[], [1], [3], [1, 2], [1], [1], [1]] 輸出 [null, null, null, null, 2, null, 3]解釋 MyLinkedList myLinkedList = new MyLinkedList(); myLinkedList.addAtHead(1); myLinkedList.addAtTail(3); myLinkedList.addAtIndex(1, 2); // 鏈表變為 1->2->3 myLinkedList.get(1); // 返回 2 myLinkedList.deleteAtIndex(1); // 現在，鏈表變為 1->3 myLinkedList.get(1); // 返回 3
? ? ? ? 今天的這道題目算得上是目前碰到的最多字數的題了，但是需求很簡單，實現出四個功能即可。分別為：
- int get(int index)獲取鏈表中下標為index的節點的值
- void addAtHead(int val)將一個val的節點插入到鏈表中第一個元素之前，也就是頭插操作。
- void addAtTail(int val)將一個值為val的節點追加到鏈表中作為鏈表的最后一個元素，也就是尾插操作。
- void addAtIndex(int index, int val)將一個值為val的節點插入到鏈表中下標為index的節點之前，這里對應隨機插入操作。
- void deleteAtIndex(int index)?如果下標有效，則刪除鏈表中下標為?
index?的節點。
二、示例分析
輸入 ["MyLinkedList", "addAtHead", "addAtTail", "addAtIndex", "get", "deleteAtIndex", "get"] [[], [1], [3], [1, 2], [1], [1], [1]] 輸出 [null, null, null, null, 2, null, 3]解釋 MyLinkedList myLinkedList = new MyLinkedList(); myLinkedList.addAtHead(1); myLinkedList.addAtTail(3); myLinkedList.addAtIndex(1, 2); // 鏈表變為 1->2->3 myLinkedList.get(1); // 返回 2 myLinkedList.deleteAtIndex(1); // 現在，鏈表變為 1->3 myLinkedList.get(1); // 返回 3
三、設計思路&代碼實現
? ? ? ? 首先題目說明可以使用單鏈表||雙鏈表，這里我們選用單鏈表的解法，只要掌握了單鏈表的一些基本操作，再使用雙鏈表進行實現起來就會很容易。
?一、創建結構體
????????這里我們需要創建一個結構體，之前在和大家分享鏈表的中間節點那里，有提到過鏈表這種數據結構的存儲方式，如果忘記的同學，可以點擊鏈接重新回憶一下。
https://blog.csdn.net/m0_75144071/article/details/144828160?spm=1001.2014.3001.5502
// 定義鏈表節點的結構體
struct LinkNode {int val; // 節點存儲的數據值LinkNode* next; // 指向下一個節點的指針// 構造函數，用于初始化新節點// 參數 val: 要存儲在節點中的值LinkNode(int val) : val(val), // 初始化 val 成員為傳入的值next(nullptr) // 初始化 next 指針為 nullptr（表示這是尾節點）{// 構造函數體為空，因為初始化列表已經完成了所有初始化工作}
};?????????LinkNode是一個表示節點的結構體，包含兩個成員，分別為val用于存儲節點的數據（本題用到的數據類型為int型），next用于指向一下個節點的指針（LinkNode*類型）
二、初始化鏈表
? ? ? ? 在昨天的題目中給大家介紹了使用虛擬頭節點進行一些鏈表的基本操作時會很方便，今天我們同樣采用虛擬帶有虛擬頭節點的方式來實現。忘記的同學，可以點擊鏈接再重新回顧一下。
https://blog.csdn.net/m0_75144071/article/details/147662796?spm=1001.2014.3001.5502
// MyLinkedList 類的構造函數
MyLinkedList() {// 創建一個虛擬頭節點(dummy node)，其值初始化為0// 虛擬頭節點不存儲實際數據，它的存在是為了簡化鏈表操作// 例如在鏈表頭部插入/刪除節點時不需要特殊處理dummyHead = new LinkNode(0);// 初始化鏈表大小為0，表示當前鏈表為空（只有虛擬頭節點）size = 0;
}三、查找功能（按位序查找）
? ? ? ? 鏈表這種數據結構有一種缺點，不支持隨機訪問，也就是他沒有辦法做到像數組那樣，我只要有了元素的下標就可以用常數級的時間復雜度來找到這個元素。使用鏈表查找元素時復雜度為O(n)（最壞）。所以我們需要從頭開始遍歷才可以進行查找。
/*** 獲取鏈表中指定位置的元素值* index 要獲取的元素位置索引（從0開始）* return 如果索引有效則返回對應節點的值，否則返回-1*/
int get(int index) {// 邊界檢查：如果索引超出有效范圍（小于0或大于等于鏈表長度）// 則返回-1表示無效if (index > (size - 1) || index < 0)return -1;// 初始化當前指針指向第一個實際節點（跳過虛擬頭節點）LinkNode* cur = dummyHead->next;// 遍歷鏈表直到目標位置// 使用index--的方式移動指針，循環次數即為需要移動的步數while (index--) {cur = cur->next;}// 返回找到的節點的值return cur->val;
}四、頭插操作
? ? ? ? 在進行頭插入/頭刪除操作時候，鏈表的效率就會比順序表（數組）高很多，?鏈表的復雜度為O(1)，而數組則需要O(n)。
????????
/*** 在鏈表頭部插入一個新節點* val 要插入的節點值*/
void addAtHead(int val) {LinkNode* newNode = new LinkNode(val);// 新節點指向當前第一個節點newNode->next = dummyHead->next;// 更新dummyHead指向新節點dummyHead->next = newNode;// 增加鏈表長度size++;
}以下為圖文講解：?
五、尾插操作
? ? ? ? 鏈表的尾插操作由于每次需要從頭節點開始遍歷找到最后的尾部節點，所以整體時間復雜度為O(n)。
void addAtTail(int val) {LinkNode* newNode = new LinkNode(val); newNode->next = nullptr; // 由于是單鏈表的尾部插入，所以next的的指向應為nullptrLinkNode* cur = dummyHead;while (cur->next) { // 遍歷直到找到最后一個節點cur = cur->next;}cur->next = newNode; // 將新節點接在尾部size++; // 增加鏈表大小
}圖文講解：?
?
六、按位序的插入操作
? ? ? ? 在進行按位序插入操作時，鏈表整體的時間復雜度以查找位置為主導為O(n)?（最壞情況下），相比數組來說，時間復雜度整體相同。
/*** 在鏈表的指定位置插入一個新節點* index 要插入的位置索引（從0開始）* val 要插入的節點值*/
void addAtIndex(int index, int val) {// 1. 邊界檢查：如果索引大于當前鏈表長度或索引小于0，直接返回不執行插入if (index > size || index < 0)return;// 2. 創建新節點，使用構造函數直接初始化節點值LinkNode* newNode = new LinkNode(val);// 3. 定位到要插入位置的前驅節點LinkNode* cur = dummyHead; // 從虛擬頭節點開始while (index--) { // 循環index次，移動到插入位置的前一個節點cur = cur->next;}// 4. 執行插入操作newNode->next = cur->next; // 新節點的next指向原位置的節點cur->next = newNode; // 前驅節點的next指向新節點// 5. 更新鏈表長度size++;
}圖文解釋：
七、按位序的刪除操作?
? ? ? ??在鏈表中的按位序刪除與插入相同。鏈表整體的時間復雜度以查找位置為主導為O(n)?（最壞情況下），相比數組來說，時間復雜度整體相同。
// 刪除指定索引位置的節點
// 參數:
// index: 要刪除節點的索引，索引從 0 開始
void deleteAtIndex(int index) {// 檢查索引是否越界，如果索引大于等于鏈表的大小或者小于 0，直接返回if (index >= size || index < 0)return;// 定義一個指針 cur，初始指向虛擬頭節點 dummyHead// 虛擬頭節點的作用是簡化鏈表頭節點的操作LinkNode* cur = dummyHead;// 通過循環讓 cur 指針移動到要刪除節點的前一個節點// 循環條件 index-- 表示每次循環后 index 的值減 1，直到 index 變為 0while (index--) {cur = cur->next;}// 定義一個臨時指針 temp，指向要刪除的節點// 即 cur 指針當前所指節點的下一個節點LinkNode* temp = cur->next;// 調整 cur 指針的 next 指針，使其跳過要刪除的節點// 直接指向要刪除節點的下一個節點cur->next = cur->next->next;// 釋放要刪除節點所占用的內存，防止內存泄漏delete temp;// 鏈表的大小減 1，因為成功刪除了一個節點size--;
}圖文講解：
至此本題需實現的所有功能均已實現完畢！完結撒花！！！🌸🌸🌸
八、完整代碼
????????C++：
class MyLinkedList {
public:struct LinkNode {int val;LinkNode* next;LinkNode(int val) : val(val), next(nullptr) {}};MyLinkedList() {dummyHead = new LinkNode(0);size = 0;}int get(int index) {if (index > (size - 1) || index < 0)return -1;LinkNode* cur = dummyHead->next;while (index--) {cur = cur->next;}return cur->val;}void addAtHead(int val) {LinkNode* newNode = new LinkNode(0);newNode->val = val;newNode->next = dummyHead->next;dummyHead->next = newNode;size++;}void addAtTail(int val) {LinkNode* newNode = new LinkNode(0);newNode->val = val;newNode->next = NULL;LinkNode* cur = dummyHead;while (cur->next) {cur = cur->next;}cur->next = newNode;size++;}void addAtIndex(int index, int val) {if (index > size)return;LinkNode* newNode = new LinkNode(val);LinkNode* cur = dummyHead;while (index--) {cur = cur->next;}newNode->next = cur->next;cur->next = newNode;size++;}void deleteAtIndex(int index) {if (index >= size || index < 0)return;LinkNode* cur = dummyHead;while (index--) {cur = cur->next;}LinkNode* temp = cur->next;cur->next = cur->next->next;delete temp;size--;}void Print() {LinkNode* cur = dummyHead->next;while (cur->next) {cout << cur->val << " ";cur = cur->next;}cout << endl;}private:int size;LinkNode* dummyHead;
};/*** Your MyLinkedList object will be instantiated and called as such:* MyLinkedList* obj = new MyLinkedList();* int param_1 = obj->get(index);* obj->addAtHead(val);* obj->addAtTail(val);* obj->addAtIndex(index,val);* obj->deleteAtIndex(index);*/四、鏈表與數組的對比
鏈表 vs 數組 操作對比總結
時間復雜度對比
操作 鏈表 數組 勝出方 隨機訪問 O(n) O(1) 數組 頭部插入/刪除 O(1) O(n) 鏈表 尾部插入/刪除 O(n) O(1) 數組 中間插入/刪除 O(n) O(n) 平手 核心特點
鏈表：動態內存、插入刪除快（尤其頭部）、訪問慢
數組：連續內存、訪問快、插入刪除慢（需移動元素）
適用場景
選鏈表：頻繁在頭部/中部增刪（如棧、隊列）
選數組：頻繁隨機訪問或尾部操作（如數值計算）
五、題目總結?
????????這道題目讓我們自己動手實現一個鏈表數據結構，主要包含獲取節點值、頭部插入、尾部插入、指定位置插入和刪除這五個核心操作。通過這個實現過程，我們深入理解了鏈表的基本特性和操作原理。
????????鏈表最大的特點是插入刪除高效，尤其是頭部操作只需要O(1)時間，這比數組要快很多。但是鏈表訪問元素需要從頭遍歷，時間復雜度是O(n)，不如數組的隨機訪問快。在實際開發中，如果經常需要在頭部插入刪除數據，鏈表是更好的選擇；如果需要頻繁按位置訪問數據，數組會更合適。
????????實現鏈表時要注意幾個關鍵點：使用虛擬頭節點可以簡化操作；維護鏈表長度size變量能方便邊界檢查；指針操作要特別注意順序，避免出現斷鏈的情況。這些細節處理能力是成為一名合格程序員的基本功。
????????通過這道題目，我們不僅掌握了鏈表的實現方法，更重要的是理解了不同數據結構的適用場景。在實際工程中，要根據具體需求選擇最合適的數據結構，這是寫出高效代碼的重要基礎。鏈表作為基礎數據結構，它的思想在很多高級數據結構中都有體現，學好鏈表對后續學習樹、圖等結構很有幫助。今天的分享到此結束！謝謝大家！！！荊軻刺秦！！！
)
