链表 Linked list

引入

链表是一种用于存储数据的数据结构，通过如链条一般的指针来连接元素。它的特点是插入与删除数据十分方便，但寻找与读取数据的表现欠佳。

与数组的区别

链表和数组都可用于存储数据。与链表不同，数组将所有元素按次序依次存储。不同的存储结构令它们有了不同的优势：

链表因其链状的结构，能方便地删除、插入数据，操作次数是 $O(1)$。但也因为这样，寻找、读取数据的效率不如数组高，在随机访问数据中的操作次数是 $O(n)$。

数组可以方便地寻找并读取数据，在随机访问中操作次数是 $O(1)$。但删除、插入的操作次数是 $O(n)$ 次。

程序包含头文件

#include <iostream>
#include <cstdlib>

using namespace std;

创建一个链表

Tip

构建链表时，使用指针的部分比较抽象，光靠文字描述和代码可能难以理解，建议配合作图来理解。

单向链表

单向链表中包含数据域和指针域，其中数据域用于存放数据，指针域用来连接当前结点和下一节点。

实现

C

typedef struct Node_t
{
  struct Node_t* next;
  int key;
} Node;

C++

struct Node
{
  int value;
  Node* next;
};

图示

双向链表

双向链表中同样有数据域和指针域。不同之处在于，指针域有左、右（或上一个、下一个）之分，用来连接上一个结点、当前结点、下一个结点。

实现
1
struct
图示

向链表写入数据

单向列表

流程
1. 初始化待插入的数据 node；
2. 将 node 的 next 指针指向 p 的下一个结点；
3. 将 p 的 next 指针指向 node。
图示

实现

void insertNode (int temp, Node* p)
{
  Node* node = new Node;
  node->value = temp;
  node->next = p->next;
  p->next = node;
}

单向循环链表

将链表的头尾连接起来，链表就变成了循环链表。由于链表首尾相连，在插入数据时需要判断原链表是否为空：为空则自身循环，不为空则正常插入数据。

流程
1. 初始化待插入的数据 node；
2. 判断给定链表 p 是否为空；
3. 若为空，则将 node 的 next 指针和 p 都指向自己；
4. 否则，将 node 的 next 指针指向 p 的下一个结点；
5. 将 p 的 next 指针指向 node。
图示

实现

void insertNode (int temp, Node* p)
{
  Node* node = new Node;
  node->value = temp;
  node->next = nullptr;
  if (p == nullptr){
    p = node;
    node->next = node;
  } else {
    node->next = p->next;
    p->next = node;
  }
}

从链表中删除数据

单向（循环）链表

设待删除结点为 p，从链表中删除它时，将 p 的下一个结点 p->next 的值覆盖给 p 即可，与此同时更新 p 的下下个结点。

流程
1. 将 p 下一个结点的值赋给 p，以抹掉 p->value；
2. 新建一个临时结点 t 存放 p->next 的地址；
3. 将 p 的 next 指针指向 p 的下下个结点，以抹掉 p->next；
4. 删除 t。此时虽然原结点 p 的地址还在使用，删除的是原结点 p->next 的地址，但 p 的数据被 p->next 覆盖，p 名存实亡。
图示

实现

void deleteNode (Node* p)
{
  p->value = p->next->value;
  Node *t = p->next;
  p->next = p->next->next;
  delete t;
}