記得數組嗎，一個蘿卜一個坑的想象。在數組的世界里我們就是第三視角，置身于坑外的。如果我們是二維平面上的生物，那數組就是一維的線，我們可以隨機訪問，增刪查改，也可以一眼看出數組大小。
那么對于鏈來說，我們則是一維鏈上的一維生物，所能知道的所有信息(即我們能看到的)就只有鏈定義的信息(比如指向自己當前位置的指針，指向下一個或上一個節點的指針)(這里面的看到，意指我們所掌握的指針)
//這是雙鏈表template <typename E>class Node {public:E val;Node* next;Node* prev;Node(Node* prev, E element, Node* next) {//這個是構造函數，可以沒有this->val = element;this->next = next;this->prev = prev;}};
顯然按照我們的設想，我們永遠都局限在鏈的一個節點上，永遠都不可能一次性看到整個鏈，就像我們在地球上一樣。于是無法直接計算出鏈的長度，以及無法直接存取，存儲空間并不連續。
增刪→
就很高效了，因為(對于有效鏈)我們一次能看兩個(單向鏈表)或三個結點，那就說明我們可以操作鏈點的鏈接，這也是鏈的核心關鍵。
我們可以銷毀砍掉的結點，也可以鏈上新定義的節點。
而操作的唯一要點就是處理好結點之間的鏈接。（就只有兩條訊息，prev?前驅指針和next?后繼指針）
對于單鏈表，朝且只能朝著著指針指示下一個結點方向走，依次處理好每個結點存儲的指針就好了。(為什么朝且只能朝著呢，因為我們手里的信息就只有那個方向的鄰接結點嘛)
對于雙鏈表，只按一個方向走一遍是不夠的，因為至少結點n本身的指針會被存儲在兩個地方——n+1，和n-1。你需要帶著n的指針前往n-1處和n+1處將它存下。于是想要處理好一個結點就需要處理好這個結點兩端的鏈接處。記住，鏈接處只和與之相連的兩個結點有關系。(這時候就可以不止往兩個方向走了，因為我們在結點處手頭可是握有兩個方向的訊息)
定義單鏈表→
本結點的存儲，后繼結點的訊息(指針)
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 = 1; i < arr.size(); i++) {cur->next = new ListNode(arr[i]);cur = cur->next;}return head;
}
查/改→
// 創建一條單鏈表
ListNode* head = createLinkedList({1, 2, 3, 4, 5});// 遍歷單鏈表
for (ListNode* p = head; p != nullptr; p = p->next) {std::cout << p->val << std::endl;
}
增→
需要處理被增結點n，那就需要處理它兩端的鏈接處，需要處理好鏈接處，那就只和鏈接處接壤的結點有關，所以這里只要處理好三個結點里的信息存儲(即指針)就好了。
插入頭部→
// 創建一條單鏈表
ListNode* head = createLinkedList({1, 2, 3, 4, 5});// 在單鏈表頭部插入一個新節點 0
ListNode* newNode = new ListNode(0);
newNode->next = head;
head = newNode;// 現在鏈表變成了 0 -> 1 -> 2 -> 3 -> 4 -> 5
插入尾部→
// 創建一條單鏈表
ListNode* head = createLinkedList({1, 2, 3, 4, 5});// 在單鏈表尾部插入一個新節點 6
ListNode* p = head;
// 先走到鏈表的最后一個節點
while (p->next != nullptr) {p = p->next;
}
// 現在 p 就是鏈表的最后一個節點
// 在 p 后面插入新節點
p->next = new ListNode(6);// 現在鏈表變成了 1 -> 2 -> 3 -> 4 -> 5 -> 6
插入中間→
// 創建一條單鏈表
ListNode* head = createLinkedList({1, 2, 3, 4, 5});// 在第 3 個節點后面插入一個新節點 66
// 先要找到前驅節點，即第 3 個節點
ListNode* p = head;
for (int i = 0; i < 2; i++) {p = p->next;
}
// 此時 p 指向第 3 個節點
// 組裝新節點的后驅指針
ListNode* newNode = new ListNode(66);
newNode->next = p->next;// 插入新節點
p->next = newNode;// 現在鏈表變成了 1 -> 2 -> 3 -> 66 -> 4 -> 5
刪
刪中間→
// 創建一條單鏈表
ListNode* head = createLinkedList({1, 2, 3, 4, 5});// 刪除第 4 個節點，要操作前驅節點
ListNode* p = head;
for (int i = 0; i < 2; i++) {p = p->next;
}// 此時 p 指向第 3 個節點，即要刪除節點的前驅節點
// 把第 4 個節點從鏈表中摘除
p->next = p->next->next;// 現在鏈表變成了 1 -> 2 -> 3 -> 5
刪尾部→
// 創建一條單鏈表
ListNode* head = createLinkedList({1, 2, 3, 4, 5});// 刪除尾節點
ListNode* p = head;
// 找到倒數第二個節點
while (p->next->next != nullptr) {p = p->next;
}// 此時 p 指向倒數第二個節點
// 把尾節點從鏈表中摘除
p->next = nullptr;// 現在鏈表變成了 1 -> 2 -> 3 -> 4
刪頭部→
// 創建一條單鏈表
ListNode* head = createLinkedList(vector<int>{1, 2, 3, 4, 5});// 刪除頭結點
head = head->next;// 現在鏈表變成了 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;
}
遍歷/查找/修改
// 創建一條雙鏈表
DoublyListNode* head = createDoublyLinkedList({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;
}
增
頭部插入→
// 創建一條雙鏈表
DoublyListNode* head = createDoublyLinkedList({1, 2, 3, 4, 5});// 在雙鏈表頭部插入新節點 0
DoublyListNode* newHead = new DoublyListNode(0);
newHead->next = head;
head->prev = newHead;
head = newHead;// 現在鏈表變成了 0 -> 1 -> 2 -> 3 -> 4 -> 5
尾部插入→
// 創建一條雙鏈表
DoublyListNode* head = createDoublyLinkedList({1, 2, 3, 4, 5});DoublyListNode* tail = head;
// 先走到鏈表的最后一個節點
while (tail->next != nullptr) {tail = tail->next;
}// 在雙鏈表尾部插入新節點 6
DoublyListNode* newNode = new DoublyListNode(6);
tail->next = newNode;
newNode->prev = tail;
// 更新尾節點引用
tail = newNode;// 現在鏈表變成了 1 -> 2 -> 3 -> 4 -> 5 -> 6
中間插入→
// 創建一條雙鏈表
DoublyListNode* head = createDoublyLinkedList({1, 2, 3, 4, 5});// 想要插入到索引 3（第 4 個節點）
// 需要操作索引 2（第 3 個節點）的指針
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
刪
刪中間→
// 創建一個雙鏈表
DoublyListNode* head = createDoublyLinkedList({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
刪頭部→
// 創建一條雙鏈表
DoublyListNode* head = createDoublyLinkedList({1, 2, 3, 4, 5});// 刪除頭結點
DoublyListNode* toDelete = head;
head = head->next;
head->prev = nullptr;// 清理已刪除節點的指針
toDelete->next = nullptr;// 現在鏈表變成了 2 -> 3 -> 4 -> 5
刪尾部→
// 創建一條雙鏈表
DoublyListNode* head = createDoublyLinkedList({1, 2, 3, 4, 5});// 刪除頭結點
DoublyListNode* toDelete = head;
head = head->next;
head->prev = nullptr;// 清理已刪除節點的指針
toDelete->next = nullptr;// 現在鏈表變成了 2 -> 3 -> 4 -> 5
總結，在鏈表的定義和操作中，我們要且僅要關注的要點，我們手頭握有的訊息(指針(方向))，處理好鏈接處(也就是處理好每個結點中存儲的訊息，這事關鏈表的結構)。
)
