链表（C++）

这是本人第二次学习链表，第一次学习链表是在大一上的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 -> 5

2.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 -> 6

2.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 -> 5

3、删除

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 -> 4

3.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 -> 5

3.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

双链表的头删和尾删比较简单，所以就没画图

以上就是关于单双链表的基本操作，学识浅薄，错误内容还望指正