链表

链表是一种最基础的数据结构，和数组一样可以用来进行其他数据结构的构建。

链表的结构

链表一般有两部分。

第一部分为数据部分，用于存储相应的数据。

第二部分为指针部分，用于指向其他节点。

 (后面几个节点外的大方框表示前一个节点的 nxt 指向的时这个节点整体而不只是数据)

通过改变指针部分的指针数量和使用方式，就可以将链表修改为其他数据结构。

树：（以二叉树为例）

图：(某些情况下可以这样表示）

链表的形式

链表一般有两种形式，一种叫静态链表，一种叫。。。就叫它指针链表吧。

指针链表

这种链表一般来说是我们学习链表时，最先接触到的链表类型，它的特点是，要通过动态申请内存来创建节点，所以，它的优点是不浪费存储空间，有多少数据就有多少节点，没有多余的节点；

缺点是，需要进行内存管理，防止内存泄漏。同时，在创建节点时，由于要使用分配内存的函数，所以速度稍慢。

指针链表的一般写法：

1 typedef struct ListNode {
2     int data;
3     struct ListNode *nxt;
4 } ListNode;
5 
6 typedef struct List {
7     ListNode *head;
8     int length;
9 } List;

我这里将链表节点整合进链表里，写好了函数后，在使用时可以减少指针的出现。

链表的一些操作：

创建节点

（由于要申请内存，所以不要忘了加与 malloc 相关的库）

1 ListNode* createListNode(int data) {
2     ListNode *lstn = (ListNode*)malloc(sizeof(ListNode));
3     lstn->data = data;
4     lstn->nxt = NULL;
5     return lstn;
6 }

初始化链表

1 void initList(List *l) {
2     l->head = createListNode(0); // 初始化链表时，设置一个头节点，不保存值 
3     l->length = 0; 
4     return;
5 }

插入节点

 1 void insertListNode(List* l, ListNode* lstn, int index) {
 2     int i = 0;
 3     ListNode *curNode = l->head;
 4     for (i = 0; i < index; ++i) {
 5         curNode = curNode->nxt;
 6     }
 7     lstn->nxt = curNode->nxt; // 由于有头节点，就可以不判断是不是要插在头上 
 8     curNode->nxt = lstn;
 9     l->length += 1;
10     return;
11 }

 删除节点

 1 void deleteListNode(List *l, int index) {
 2     ListNode* curNode = l->head;
 3     int i = 0;
 4     for (i = 0; i < index; ++i) {
 5         curNode = curNode->nxt;
 6     }
 7     ListNode *tmp = curNode->nxt;
 8     curNode->nxt = curNode->nxt->nxt; // 这里同样的，可以不用判断是不是要删除第一个节点 
 9     free(tmp);
10     return;
11 }

静态链表

这种链表可以在一些竞赛大量中看到。它是一种用数组加下标“模拟”指针链表的数据结构，但它也是一种链表。这种用数组写的链表在程序被加载时就已经创建好了一大片内存空间，后续使用时，不用再申请内存，速度较指针链表有所提升，并且不用小心地进行内存管理，是众多”高度近视“的福音，也省下了后期debug的时间。

静态链表的结构从数组的角度来看是这样的：

看起来很乱是吗？

但其实，只要我们把一头一尾找到，抓住它们，抖一抖，就会发现，它又变成了这样：

 所以其实，它和指针链表没啥差别，就只是把指针换成了数组下标而已，如果我们不把数组看作一段连续的内存空间，那么这两种链表就完全没有差别。（甚至后者还不用专门去管理内存）

那么，下面给出一种它的写法

1 #define MAX_SIZE 110
2 
3 struct ListNode {
4     int data;
5     int nxtIndex;
6 } nodes[MAX_SIZE];

看起来确实很像指针链表

不过，由于是静态链表，不存在指针，所以我们还需要两个变量存储一些数据。

1 int head = -1; // 用来指向链表头所在的位置
2 int nodeCnt = 0; // 用来记录我们已经用过多少个节点

接下来是一些操作

先是初始化

1 void initList(void) {
2     memset(nodes, -1, sizeof(nodes)); // 个人习惯将整个数组初始化为每个字节都是 0xFF，也可以是0
3     return;
4 }

这次我打算不使用空的头节点，所以我们就会面临要插入的节点在最开头的情况

为此，我写了一个头插函数

1 void insertListNode2Head(int data) {
2     nodes[cnt].data = data;
3     nodes[cnt].nxtIndex = head;
4     head = cnt++;
5     return;
6 }

一般的插入函数

 1 oid insertListNode(int data, int index) {
 2     if (index == 0) { // 看起来不太爽的判断语句
 3         insertListNode2Head(data);
 4         return;
 5     }
 6     int i = 0;
 7     int curNode = head;
 8     for (i = 0; i < index - 1; ++i) {
 9         curNode = nodes[curNode].nxtIndex;
10     }
11     nodes[cnt].data = data;
12     nodes[cnt].nxtIndex = nodes[curNode].nxtIndex;
13     nodes[curNode].nxtIndex = cnt;
14     cnt++;
15     return;
16 }

然后是删除

 1 void deleteListNode(int index) {
 2     if (index == 0) { // 同样需要一个判断
 3         head = nodes[head].nxtIndex;
 4         return;
 5     }
 6     int i = 0;
 7     int curNode = head;
 8     for (i = 0; i < index - 1; ++i) {
 9         curNode = nodes[curNode].nxtIndex;
10     }
11     nodes[curNode].nxtIndex = nodes[nodes[curNode].nxtIndex].nxtIndex;
12     return;
13 }

这里我们发现了一些静态链表不好的地方。删除的时候，我们没有办法回收不再使用的数组元素，在大量的插入与删除后，可能陷入明明没有几个节点，却没地方存数据的窘境。所以，在使用静态链表时，我们应该考虑到是否有大量的修改（特别是删除）操作。在竞赛中，这样的链表一般被用来存储图的边，而这些边一般是没有删除操作的。

总结

1.指针链表泛用性强，并且结构更易懂，理解其中的思想后，理解静态链表会更容易，但写指针时需要小心

2.静态链表快，安全隐患低，但不适合大量修改操作

3.如果可以，尽量增加一个空的头节点