趣味数据结构之—

记得数组吗，一个萝卜一个坑的想象。在数组的世界里我们就是第三视角，置身于坑外的。如果我们是二维平面上的生物，那数组就是一维的线，我们可以随机访问，增删查改，也可以一眼看出数组大小。

那么对于链来说，我们则是一维链上的一维生物，所能知道的所有信息(即我们能看到的)就只有链定义的信息(比如指向自己当前位置的指针，指向下一个或上一个节点的指针)(这里面的看到，意指我们所掌握的指针)

    //这是双链表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

总结，在链表的定义和操作中，我们要且仅要关注的要点，我们手头握有的讯息(指针(方向))，处理好链接处(也就是处理好每个结点中存储的讯息，这事关链表的结构)。