记得数组吗，一个萝卜一个坑的想象。在数组的世界里我们就是第三视角，置身于坑外的。如果我们是二维平面上的生物，那数组就是一维的线，我们可以随机访问，增删查改，也可以一眼看出数组大小。
那么对于链来说，我们则是一维链上的一维生物，所能知道的所有信息(即我们能看到的)就只有链定义的信息(比如指向自己当前位置的指针，指向下一个或上一个节点的指针)(这里面的看到，意指我们所掌握的指针)
//这是双链表
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
总结，在链表的定义和操作中，我们要且仅要关注的要点，我们手头握有的讯息(指针(方向))，处理好链接处(也就是处理好每个结点中存储的讯息，这事关链表的结构)。