链表是线性表的链式存储方式，逻辑上相邻的数据在计算机内的存储位置不一定相邻，那么怎么表示逻辑上的相邻关系呢？可以给每个元素都附加一个指针域，指向下一个元素的存储位置。

从下图可以看出，每个节点都包含两个域：数据域和指针域。数据域存储数据元素，指针域存储下一个节点的地址，因此指针指向的类型也是节点类型。链表中的每个指针都指向下一个节点，都朝向一个方向的，这样的链表被称为单向链表或单链表。

单链表的节点结构体定义如下图所示。

定义了节点结构体之后，就可以把若干节点连接在一起，形成一个单链表了。

不管这个单链表有多长，只要找到它的头，就可以拉起整个单链表，因此如果给这个单链表设置一个头指针，则这个单链表中的每个节点就都可以找到了。

有时为了操作方便，还会给单链表增加一个不存放数据的头节点（也可以存放表长等信息）。给单链表加上头节点，就像给铁链子加上钥匙扣。

若想在顺序表中找第 i 个元素，则可以立即通过 L .elem[ i -1]找到，想找哪个就找哪个，被称为随机存取。但若想在单链表中找第 i 个元素该怎么办？答案是必须从头开始，按顺序一个一个地找，一直数到第 i 个元素，被称为顺序存取。

（1）插入。在第 i 个节点之前插入元素 e ，相当于在第 i -1个节点之后插入元素 e 。假设已找到第 i -1个节点，并用 p 指针指向该节点， s 指向待插入的新节点，则插入操作如下图所示。

其中，“ s ->next= p ->next”指将节点 p 后面的节点地址赋值给节点 s 的指针域，即节点 s 的next指针指向 p 后面的节点；“ p ->next=s”指将节点 s 的地址赋值给节点 p 的指针域，即节点 p 的next指针指向节点 s 。

算法代码：

（2）删除。删除一个节点，实际上是把这个节点跳过去。根据单向链表向后操作的特性，要想跳过第 i 个节点，就必须先找到第 i -1个节点，否则是无法跳过去的，如下图所示。

其中，“ p ->next= q ->next”指将节点 q 的下一个节点地址赋值给节点 p 的指针域。

在这些有关指针的赋值语句中，等号的右侧是节点的地址，等号的左侧是节点的指针域，如下图所示。

在上图中，假设节点 q 的下一个节点地址为1013，该地址被存储在 q ->next里面，因此等号右侧 q ->next的值为1013。把该地址赋值给节点 p 的next指针域，把原来的值2046覆盖，这样， p ->next的值也为1013，相当于把节点 q 跳过去了。赋值之后如下图所示。然后用delete q 释放被删除节点的空间。

算法代码：

在单链表中，每个节点除了存储自身数据，还存储下一个节点的地址，因此可以轻松访问下一个节点，以及后面的所有后继节点，但是如果想访问前面的节点就不行了，再也回不去了。例如删除节点 q 时，要先找到它的前一个节点 p ，然后才能删掉节点 q ，单链表只能向后操作，不能向前操作。如果需要向前操作，则该怎么办呢？

还有另外一种链表——双向链表。 79rS9eozKV3/A6pvRY+iIZarSY7kai8M6xW0v4I/jqVXPVrgnRc+LzQvgQvDYmRk