這是本人第二次學習鏈表，第一次學習鏈表是在大一上的C語言課上，首次接觸，感到有些難；第二次是在大一下學習數據結構時（就是這次），使用C++再次理解鏈表。同時，這也是開啟數據結構學習寫的第一篇文章，但愿以后有時間一直寫下去。
當然，學習數據結構還是保持著學習計算機的基本素養——增、刪、查、改。
一、為什么需要鏈表？
首先，理解數組與鏈表區別，數組是一塊連續的內存空間，有了這塊內存空間，可以通過數組索引計算出任意位置元素內存；而鏈表，不需要一塊連續的內存空間，可以分散在各處，只需通過節點連接起來，這是相對于數組的好處，但是也有弊端，由于鏈表中每個元素不是連續挨著的，所以訪問時，需要從頭結點開始遍歷直至找到你要的元素。
二、單鏈表基本操作
首先，創建一條單鏈表：
class ListNode {
public:int val;ListNode* next;ListNode(int x):val(x),next(NULL){}
};ListNode* createLinkedList(std::vector<int> arr) {//輸入數組，轉換成單鏈表if (arr.empty()) {return nullptr;}ListNode* head = new ListNode(arr[0]);ListNode* cur = head;for (int i = 0; i < arr.size(); i++) {cur->next = new ListNode(arr[i]);cur = cur->next;}return head;
}1、單鏈表查找、遍歷、修改
ListNode* head = createLinkedList({1, 2, 3, 4, 5});
for (ListNode* p = head; p != nullptr; p = p->next) {std::cout << p->val << std::endl;
}這是遍歷一個單鏈表↑
如果是要通過索引訪問或修改鏈表中的某個節點，也只能用 for 循環從頭結點開始往后找，直到找到索引對應的節點，然后進行訪問或修改。
2、增加
2.1頭插
ListNode* head = createLinkedList({1, 2, 3, 4, 5});
ListNode* newHead = new ListNode(6);
newHead->next = head;
head = newHead; // 現在的鏈表 6 -> 1 -> 2 -> 3 -> 4 -> 52.2尾插
比頭插只復雜一步，需要遍歷到末尾，再插入
ListNode* head = createLinkedList(std::vector<int>{1, 2, 3, 4, 5});
ListNode* p = head;
while (p->next != nullptr) {p = p->next;
}
p->next = new ListNode(6);// 現在鏈表變成了 1 -> 2 -> 3 -> 4 -> 5 -> 62.3中間插入
在鏈表的中間插入，只需要找到前驅節點，然后插入
ListNode* head = createLinkedList({ 1,2,3,4,5 });
ListNode* p = head;
for (int i = 0; i < 2; i++) {p = p->next;
}
ListNode* newNode = new ListNode(66);
newNode->next = p->next;
p->next = newNode;// 現在鏈表變成了 1 -> 2 -> 3 -> 66 -> 4 -> 53、刪除
3.1中間刪除
還是找到要刪除的節點的前一個節點，把前一個節點的next指針指向刪除節點的next指針
ListNode* head = createLinkedList({1, 2, 3, 4, 5});
ListNode* p = head;
for (int i = 0; i < 2; i++) {p = p->next;
}
p->next = p->next->next;// 現在鏈表變成了 1 -> 2 -> 3 -> 5這里不懂可以看看我之前發的鏈表文章（配圖的那篇）鏈表?
3.2尾部刪除
這種刪除是最簡單的，找到倒數第二個節點，將它的next指針設為null
ListNode* head = createLinkedList({1, 2, 3, 4, 5});
ListNode* p = head;
while (p->next->next != nullptr) {p = p->next;
}
p->next = nullptr;// 現在鏈表變成了 1 -> 2 -> 3 -> 43.3頭部刪除
ListNode* head = createLinkedList(vector<int>{1, 2, 3, 4, 5});
head = head->next;// 現在鏈表變成了 2 -> 3 -> 4 -> 5第一次學習鏈表時，這里就出現了困惑，困惑出在第一個節點身上，原第一個節點的next還指向第二個，所以看起來沒有刪除，只是沒有訪問，是否會造成內存泄漏？但實際上，沒有其它引用第一個節點，它就會被回收掉，當然也可以把第一個節點的next設為null，這就避免這個問題，如下：
ListNode* head = createLinkedList(vector<int>{1, 2, 3, 4, 5});
ListNode* oldHead = head;
head = head->next;
oldHead->next = nullptr;
delete oldHead;// 現在鏈表變成了 2 -> 3 -> 4 -> 5這樣就嚴謹了。
三、雙鏈表基本操作
首先，創建雙鏈表：
class DoublyListNode {
public:int val;DoublyListNode *next, *prev;DoublyListNode(int x) : val(x), next(NULL), prev(NULL) {}
};DoublyListNode* createDoublyLinkedList(vector<int>& arr) {if (arr.empty()) {return NULL;}DoublyListNode* head = new DoublyListNode(arr[0]);DoublyListNode* cur = head;// for 循環迭代創建雙鏈表for (int i = 1; i < arr.size(); i++) {DoublyListNode* newNode = new DoublyListNode(arr[i]);cur->next = newNode;newNode->prev = cur;cur = cur->next;}return head;
}1、遍歷、查找、修改
對于雙鏈表，從頭節點或尾節點，向后或向前遍歷
DoublyListNode* head = createDoublyLinkedList(new int[]{1, 2, 3, 4, 5});
DoublyListNode* tail = nullptr;
// 從頭節點向后遍歷雙鏈表
for (DoublyListNode* p = head; p != nullptr; p = p->next) {cout << p->val << endl;tail = p;
}
// 從尾節點向前遍歷雙鏈表
for (DoublyListNode* p = tail; p != nullptr; p = p->prev) {cout << p->val << endl;
}訪問或修改節點時，可以根據索引是靠近頭部還是尾部，選擇合適的方向遍歷，這樣可以一定程度上提高效率。
2、增加
2.1頭插
需要改變新節點和原頭結點指針
DoublyListNode* head = createDoublyLinkedList({1, 2, 3, 4, 5});
DoublyListNode* newHead = new DoublyListNode(0);
newHead->next = head;
head->prev = newHead;
head = newHead; // 現在鏈表變成了 0 -> 1 -> 2 -> 3 -> 4 -> 5
頭插步驟如圖
2.2尾插
雙鏈表尾插與單鏈表尾插一樣，需要遍歷到最后一個節點，如果已知尾節點的引用，就簡單很多了（不需要遍歷了）
DoublyListNode* head = createDoublyLinkedList({1, 2, 3, 4, 5});
DoublyListNode* tail = head;
while (tail->next != nullptr) {tail = tail->next;
}
DoublyListNode* newNode = new DoublyListNode(6);
tail->next = newNode;
newNode->prev = tail;
// 更新尾節點引用
tail = newNode; // 現在鏈表變成了 1 -> 2 -> 3 -> 4 -> 5 -> 6比較簡單，先是尾節點的next指針指向newNode，然后newNode的prev指針再指向原tail，這是一個互逆過程，即我指向你，你也需要指向我，這樣才符合雙鏈表的定義。
最后，更新一下尾節點，方便下一次在尾部直接插入，重復執行上面的操作。
2.3中間插入
雙鏈表的中間插入需要同時關注前驅指針和后繼指針
如：把元素 66 插入到索引 3（第 4 個節點）的位置
DoublyListNode* head = createDoublyLinkedList({1, 2, 3, 4, 5});
DoublyListNode* p = head;
for (int i = 0; i < 2; i++) {p = p->next;
}
DoublyListNode* newNode = new DoublyListNode(66);
newNode->next = p->next;
newNode->prev = p;p->next->prev = newNode;
p->next = newNode; // 現在鏈表變成了 1 -> 2 -> 3 -> 66 -> 4 -> 5下面，用畫圖解釋一下：
第一步，初始化和p的遍歷（遍歷到第三個節點）
第二步，newNode->next = p->next;（紅色箭頭）
第三步，newNode->prev = p;（綠色箭頭）
第四步，p->next->prev = newNode;（藍色）
第四步，p->next = newNode;（黃色）
這樣，66就成功插入到了第三個節點之后
3、刪除
3.1中間刪除
DoublyListNode* head = createDoublyLinkedList(std::vector<int>{1, 2, 3, 4, 5});
// 刪除第 4 個節點
// 先找到第 3 個節點
DoublyListNode* p = head;
for (int i = 0; i < 2; ++i) {p = p->next;
}
// 現在 p 指向第 3 個節點，我們將它后面那個節點摘除出去
DoublyListNode* toDelete = p->next;
// 把 toDelete 從鏈表中摘除
p->next = toDelete->next;
toDelete->next->prev = p;
// 把 toDelete 的前后指針都置為 null 是個好習慣（可選）
toDelete->next = nullptr;
toDelete->prev = nullptr; // 現在鏈表變成了 1 -> 2 -> 3 -> 5中間刪除比較復雜，還是采用畫圖的方法理解
第一步，還是初始化和遍歷
第二步，摘出要刪除的節點（即4）
第三步，p->next = toDelete->next;（藍色）
第四步，toDelete->next->prev = p;（黃色）
其實，到這里已經結束了，但還是最開始的問題，為了規范，把要刪除的節點前驅和后繼指針置為null
3.2頭刪
DoublyListNode* head = createDoublyLinkedList({1, 2, 3, 4, 5});
DoublyListNode* toDelete = head;
head = head->next;
head->prev = nullptr;toDelete->next = nullptr; // 現在鏈表變成了 2 -> 3 -> 4 -> 53.3尾刪
在單鏈表中，由于缺乏前驅指針，所以刪除尾節點時需要遍歷到倒數第二個節點，操作它的?next?指針，才能把尾節點摘除出去。但在雙鏈表中，由于每個節點都存儲了前驅節點的指針，所以我們可以直接操作尾節點，把它自己從鏈表中摘除：
DoublyListNode* head = createDoublyLinkedList(std::vector<int>{1, 2, 3, 4, 5});
DoublyListNode* p = head;
while (p->next != nullptr) {p = p->next;
}
// 現在 p 指向尾節點
// 把尾節點從鏈表中摘除
p->prev->next = nullptr;
// 把被刪結點的指針都斷開是個好習慣（可選）
p->prev = nullptr; // 現在鏈表變成了 1 -> 2 -> 3 -> 4雙鏈表的頭刪和尾刪比較簡單，所以就沒畫圖
以上就是關于單雙鏈表的基本操作，學識淺薄，錯誤內容還望指正
)
![Ditto-Talkinghead：阿里巴巴數字人技術新突破 [特殊字符]?](http://pic.xiahunao.cn/Ditto-Talkinghead：阿里巴巴數字人技術新突破 [特殊字符]?)
