18 | 重新认识数据结构（上）：初识链表结构

你好，我是胡光，欢迎来到“算法数据结构篇”的第一课。

在之前的学习中，我们对数据结构的认识，主要集中在它是用来做数据的表示，更具体地讲，就是数据结构所讨论的问题，是将现实中的数据如何合理地表示在程序中，以使程序完成既定的目标任务。

不知道你还记不记得，在上节课 Shift-And 算法的学习中，我们发现不同的数据，或者说信息表示方式，会给解决问题的效率带来很大的影响。因此，基本确定了数据的表示，在程序设计过程中发挥着非常重要的作用，也就意味着我们必须对数据结构的学习重视起来。

之前我们所讨论的数据结构呢，其实都只是停留在程序内部的数据结构，这是一种具体的，可见的数据结构，并对我们设计的程序产生重要影响。我们也认识到，这种具体的数据结构的重要作用，会对我们设计的程序产生重要的影响。今天呢，我将带你重新认识数据结构，发现它的另一面，那就是数据结构对我们思维方式的影响，这种影响更抽象，也更重要。

接下来的两次课程内容呢，我将通过链表结构的讲解，让你认识这种思维层面的数据结构。

必知必会，查缺补漏

今天我们将要学习的链表，是一种常见的基础数据结构，属于数据结构中线性结构的一种。在讲如何学习链表之前，我们先来看一看通常情况下，如何学习数据结构的相关的知识。

1.数据结构：结构定义+结构操作

你应该玩过拼装式的玩具吧，类似于高达机器人之类的。面对这样的玩具，我一般在拼装之前看看说明书，知道这个玩具包含哪几部分，然后对这些部分进行拼装，等把各部分拼好了后，再把它们组合起来，最终的成品就完成了。

其实学习某样知识也是一样的，要先搞清楚这门知识的组成部分，从组成部分开始入手学习，最后把所有的知识碎片整合到一起，就是知识的全貌了。

回到如何理解数据结构这个问题，我先给你列出重要的两句话：

数据结构 = 结构定义 + 结构操作
数据结构，就是定义一种性质，并且维护这种性质

其实这两句话，说的是一回事儿。结构定义，指的是就是说明这种数据结构长成什么样子，具备什么性质。结构操作，就是确定这种数据结构都支持哪些操作，同时结构操作的结果，不能破坏这类结构原本的性质。这也就到了第二句话中说的内容，维护这种性质。

这就好像刚才我说到的高达机器人，结构定义类比高达机器人的样子，结构操作就是这个机器人都支持什么功能，比如抬手、伸腿之类的。但是无论是哪种结构操作，你都不能把机器人玩坏掉（也就是不能破坏结构定义），这就是我们所说的：操作归操作，但是你要维护这种性质。

接下来呢，我将会通过这两句话，带你学习链表这种数据结构。

2.链表的结构定义

链表的结构定义中，包含了两个信息，一个是数据信息，用来存储数据的，也叫做数据域；另外一个是地址信息，用来存储下一个节点地址的，也叫做指针域。

记住，链表结构是由一个一个链表节点组成的，在应用这种结构的时候，你无需对这种结构本身做改变，你只需要按照自己的需求，把自己想要的数据，放在链表结构定义的数据域中即可。比如说，整型是你想存储在链表中的数据，那么数据域的类型就是整型，如果字符串类型是你想存储的数据，那么数据域的类型就是字符串类型。

在示意图中可以看到，链表节点以整型作为数据域的类型，其中第一个链表节点，存储了 763 这个数据，指针域中呢，存储了一个 0x56432地址，这个地址而 0x56432正是第二个链表节点的地址。我们可以说，第一个节点指向第二个节点，因此这两个节点之间，在逻辑上构成了一个指向关系。

在第二个节点的指针域中呢，存储了一个地址，是0x0，这个地址值所对应的整型值就是 0。这是一个特殊的地址，我们称它为空地址，在 C 语言中用 NULL 宏表示这个空地址，读作nào。我们让第二个链表节点指向空地址，就意味着它就是这个链表结构的最后一个节点。

看完了链表的结构示意图以后，就来让我们看一下在代码中，如何定义链表节点结构吧：

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

正如这段代码所示，我们使用结构体，定义一种新的类型，叫做 struct Node 类型，来表示链表的节点结构。链表的每个节点内部，有一个数据域，一个指针域，对应到代码中，就是一个整型的 data 字段，和一个指向 struct Node 类型本身的指针字段 next。

值得注意的是，链表结构的指针域只有一个 next 变量，这就说明每一个链表节点，只能唯一地指向后续的一个节点，这是链表结构非常重要的一个性质，后续我们也会用到这个性质。

总地来说，链表结构中，数据域是留出来让我们实现自我需求的，就是想存整型，就改成整型，想存浮点型，就改成浮点型。而 next 指针域，是用来维护链表这个结构的，这里一般不需要你自由发挥，记住怎么回事儿，直接用就行了。记住，要想修改内存中的链表结构，就一定要修改节点内部 next 指针域中存储的地址值。

3.链表的结构操作

接下来呢，我会给你介绍一种链表的基础操作，就是向链表中插入节点的操作。

在讲解链表的插入和删除方法之前呢，我们先来对齐一个概念，就是链表节点的位置。当你把链表结构画出来以后，你会发现链表结构和数组结构很类似，只不过数组结构在内存中存储是连续的，链表结构由于有指针域的存在，它的每一个节点在内存中存储的位置未必连续。

我们也可以参考数组下标的编号规则，给每个链表节点编一个号，从第一个开始依次是0、1、2，具体如下图所示：

明白了什么是链表的节点位置以后呢，我们定义一个向链表中插入节点的函数方法：

struct Node *insert(struct Node *head, int ind, struct Node *a);

这个插入方法呢，传入三个参数，第一个是待操作的链表的头结点地址，也就是链表中第一个节点的地址；第二个参数代表插入位置；第三个参数是一个指针变量，指向要插入的新节点。

简单来说，就是向 head 所指向的链表的 ind 位置插入一个由 a 所指向的节点，返回值代表插入新节点以后的链表头结点地址。为什么要返回插入以后的链表头结点地址呢？因为新节点有可能插入到链表的第 0 位，插入以后，链表的头结点地址就发生了改变，我们必须把这个信息返回。

由于插入操作，会改变链表结构，刚刚我们说了，只有修改链表节点中的 next 指针域的值，才算是修改了链表的结构。为了完成插入操作，我们都需要修改哪些节点的 next 指针域的值呢？

首先是让 ind - 1 位置的节点指向 a 节点，然后是 a 节点指向原 ind 位置的节点，也就是说，涉及到两个节点的 next 指针域的值的修改，一个是 ind - 1 位置的节点，一个是 a 节点自身。我们就可以先找到 ind - 1位置的节点，然后再进行相关操作即可。写成代码，如下所示：

struct Node *insert(struct Node *head, int ind, struct Node *a) {
    struct Node ret, *p = &ret;
    ret.next = head;
    // 从【虚拟头节点】开始向后走 ind 步
    while (ind--) p = p->next;
    // 完成节点的插入操作
    a->next = p->next;
    p->next = a;
    // 返回真正的链表头节点地址  
    return ret.next;
}

代码中，涉及到一个很重要的技巧，就是 “虚拟头结点” 这个链表操作技巧。所谓虚拟头结点，就是在原有的链表头结点前面，加上另外一个节点，这个额外增加的头结点，就是虚拟头结点。增加虚拟头结点的目的，是为了让我们操作链表更方便，实际上，如果在某个操作中，头结点地址有可能发生改变，我们也可以使用虚拟头结点这个技巧。

我们来分析一下，对于插入操作，虚拟头结点有什么重要的作用。首先如果我们要在第 5 个位置插入新节点，那我们就要找到 4 号位的节点，也就是从头结点开始，向后走 4 步，确定了 4 号节点以后，再修改相关节点的 next 指针域即可。

也就是说，如果我们想插入到 ind 位，就需要从头结点向后走 ind - 1 步，定位到 ind - 1 号节点。如果插入的位置为 0 呢？我们总不能走 -1 步吧？这个时候，在程序中我们就只能对 ind 等于 0 的情况进行特殊判断了。这确实是一种可行的实现方法，可不够优美，因为这种做法没有统一 ind 在等于 0 和不等于 0 时候的处理情况。

可是当我们在原链表前面，加入了一个虚拟头结点以后，这一切的操作就变得自然了许多！一开始 p 指向虚拟头结点，由于链表头部增加了一个节点，原先我们要定位链表 ind - 1 位置，要走 ind - 1步，现在就是走 ind 步。

也就是说，在有虚拟头结点的情况下，如果我们插入到 5 号位，就从虚拟头结点向后走 5 步就行，同样的，想要插入到 0 号位呢，就向后走 0 步即可，即 p 指针指向虚拟头结点不动，直接将新的节点，插入到虚拟头结点后面即可。

其实，对于链表的相关操作，无论是插入还是删除，只要是有可能改变原有链表头结点的操作，增加虚拟头结点都是一个很实用的处理技巧。

一起动手，搞事情

今天给你留的作业呢，与链表的操作有关系，请看如下函数接口定义：

struct Node *erase(struct Node *head, int ind);

请你参照文中的链表插入操作，实现一个链表节点删除的操作，删除函数传入两个参数，分别代表指向链表头结点的指针变量 head，以及要删除的节点位置 ind，返回值代表删除节点以后的链表头结点地址。

由于删除操作，有可能改变链表的头结点，所以你可以尝试使用前面我们讲到的虚拟头结点的编码技巧。仔细分析，你可以的！

课程小结

我们今天介绍的链表呢，其实真实姓名叫做“单向链表”，这是一种很有代表性的链表结构。实际上，你学会了单向链表，也就很容易掌握其他形式的链表了。比如说：单向循环链表、双向链表、双向循环链表、块状链表、跳跃表。

尤其是块状链表和跳跃表，在工程中应用最广泛，C++ STL 中的 vector 底层用的就是块状链表。关于这些概念，如果你感兴趣，可以自行上网搜索相关资料。篇幅有限，我们就不一个个展开介绍了。

最后，我们来做一下今天课程的总结，今天我希望你记住如下几点：

数据结构 = 结构定义 + 结构操作，这个等式说明了我们学习数据结构的方法顺序。
单向链表节点中，存在数据域和指针域，指针域控制了链表的结构，一般不会根据应用场景的变化而变化，而数据域是根据应用场景的需求而设计的。

下节课呢，我将给你讲几种更有意思的链表操作。好了，今天就到这里了，我是胡光，咱们下期见。

精选留言

🤪HappyJoo

2020-02-29 07:47:26

老师您好，请问一下，这个虚拟头结点是如何不影响链表的呢？我的理解是，每次执行插入函数（这个*insert是函数吧。C语言的函数就是方法？）时，都创造一个虚拟结点（计算机会自动创造吗？），让它指向链表的真正头结点，执行函数。函数执行结束后，将虚拟结点与真正头结点断开，这样子就可以做到“虚拟”了。请问老师我的理解有哪些不对的地方吗？谢谢老师~~~

作者回复

当然不是计算机自动创造的，而是我们通过代码逻辑加上去的。所谓虚拟，就是只有在操作过程中，存在的一个节点，这个节点完全是为了操作简便，额外加上去的，不是链表的实际节点。

2020-02-29 13:34:04
徐洲更

2020-02-27 16:18:50

python里的list可以存放不同数据类型，也是用链表实现的嘛，C语言如何写出这种数据结构呢

作者回复

python中的list不是用链表实现的，那样的话，查找效率太差了，C中的话，可以用指针数组实现，指针类型是void *即可指向任意一种类型数据。

2020-02-28 12:57:55
注意力$

2022-06-26 15:39:30

struct LinkNode * init_LinkList(){
struct LinkNode * pHeader=malloc(sizeof(struct LinkNode));
if(pHeader == NULL){
return NULL;
}
//头结点不维护数据域
pHeader->num=-1;
pHeader->next=NULL;

// 创建尾结点指针用户记录当前链表尾部节点位置，方便尾插
struct LinkNode * pTail=pHeader;

int val=-1;

while(1)
{
printf("qingshuru\n");
scanf("%d",&val);
if(val ==-1){
break;
}
//创建新节点
struct LinkNode * newNode=malloc(sizeof(struct LinkNode));
newNode->num=val;
newNode->next=NULL;

//更新节点的指向
pTail->next=newNode;
pTail=newNode;
}

return pHeader;
}

void foreach_LinkList(struct LinkNode * pHeader){

if(pHeader ==NULL){
return;
}
//当前节点指向第一个有真实数据的节点
struct LinkNode * pCurrent = pHeader->next;
while(pCurrent !=NULL)
{
printf("%d\n",pCurrent->num);
pCurrent=pCurrent->next;
}
}

void insert_LinkList(struct LinkNode * pHeader,int oldVal,int newVal){
if(pHeader ==NULL){
return;
}

// 创建2个临时指针实现节点插入
struct LinkNode * pPrev=pHeader;
struct LinkNode * pCurrent=pHeader->next;
while(pCurrent != NULL)
{
if(pCurrent->num=oldVal)
{
break;
}
//两个辅助指针往后移动
pPrev=pCurrent;
pCurrent=pCurrent->next;
}
//创建新节点
struct LinkNode * newNode=malloc(sizeof(struct LinkNode));
newNode->num=newVal;
newNode->next=NULL;

//更改指针的指向
newNode->next=pCurrent;
pPrev->next=newNode;
}

老师上面是我实现链表的插入节点的方法，然后
insert_LinkList(pHeader,20,100);
insert_LinkList(pHeader,21,1000);
printf("charuhou \n");
foreach_LinkList(pHeader);
最后发现结果不对
qingshuru
10
qingshuru
20
qingshuru
30
qingshuru
-1
bianlijie
10
20
30
charuhou
1000
21
20
20
30

能看出来哪里错了吗
宋不肥

2020-02-29 22:54:50

作业打卡：
#include<stdio.h>
struct Node {
int data;
struct Node *next;
};

struct Node *insert(struct Node *head, int ind, struct Node *a) {
struct Node ret, *p = &ret;
ret.next = head;
// 从【虚拟头节点】开始向后走 ind 步
while (ind--) p = p->next;
// 完成节点的插入操作
a->next = p->next;
p->next = a;
// 返回真正的链表头节点地址
return ret.next;
}

struct Node *erase(struct Node *head, int ind){
struct Node ret, *p = &ret;
ret.next = head;
while(ind--) p = p->next;
p->next = p->next->next;
return ret.next;
}

main(){
struct Node N1,N0,N3;
N0.data = 0;
N0.next = &N1;
N1.data = 1;
N1.next = &N3;
N3.data = 3;
N3.next = NULL;
struct Node N2;
N2.data = 2;
N2.next = NULL;
insert(&N0, 2, &N2);
printf("%d\n",(N1.next)->data);
erase(&N0, 2);
printf("%d",(*N1.next).data);
}
然后有个问题，被删除的结点的内存需要手动释放嘛？感觉这样就只是不用这个结点了，他占用的内存会被当做垃圾碎片嘛

作者回复

对，实际上是需要手动释放的，如果是 C 的话，你可以使用 free 来进行释放。没有强调释放的原因是，咱们这个不是一份完整的链表代码，没有从创建开始讲，所以突然提到释放，就会很突兀。你可以想到这个问题，是很棒的！

2020-03-02 10:05:52
🤪HappyJoo

2020-02-29 07:49:18

不知道有没有用，“画”了一个图给对于插入不太懂的同学看看哈哈哈哈：

----p----p.next----| ----> |----p p.next----
| ----> | \ /
| ----> | \ /
-------a-----------| ----> | a

作者回复

d(^_^o)给个封号：最强助教！

2020-02-29 13:29:03
doge

2020-02-28 16:37:54

struct Node* erase(struct Node *head, int ind){
struct Node ret, *p = &ret, *q = NULL;
if (ind < 1){
err("invalid position %d\n", ind);
return head;
}
ret.next = head;
while (--ind && p->next != NULL) p = p->next;
if (ind != 0) err("invaild position, node not found\n");
else {
q = p->next;
p->next = q->next;
free(q);
}
return ret.next;

作者回复

非常棒！还实现了非法情况判断！d(^_^o)

2020-02-28 23:22:47
奕

2020-02-27 23:31:58

// 删除指定索引位置的节点
struct Node *erase(struct Node *head, int ind) {
struct Node preNode, *p = &preNode;
preNode.next = head;
while (ind--) {
p = p->next;
}
// 指向删除节点的下一个位置
p->next = p->next->next;
return preNode.next;
}

作者回复

完美！d(^_^o)

2020-02-28 12:59:08
阿阳

2023-10-22 20:43:39

参考数组下标的编号规则，给每个链表节点编一个号，从第一个开始依次是 0、1、2。在链表插入操作中，ind这个参数表示要插入的位置，是从1开始的。
阿牛

2022-06-09 17:30:46

看评论区有位伙伴的代码写的是
p->next = p->next->next

我写出来的是
p = p->next

其他部分相同，
想问下如果想删除第3个节点，取ind=3
那两个代码哪个正确呢
马建华

2021-03-27 11:53:49

请问老师ret.next和p->next有何区别？为何不写为p=p.next？
一溢孤行

2020-08-10 11:22:09

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//定义单链表结点的数据结构
typedef struct Node
{
int data; //数据类型及其相应的值
struct Node* next; //指向下一个结点
}Node;

//创建单链表的一个结点
Node* create_node(int num)
{
//给每个节点分配结构体一样的空间大小
Node* p = malloc(sizeof(Node));
if (p == NULL)
{
printf("malloc error!\n");
return NULL;
}
//由于结构体在未初始化的时候数据是杂乱的，所以要清先进行清理
memset(p, 0, sizeof(Node));
//初始化第一个节点
p->data = num;
//将节点的后继指针设置为NULL
p->next = NULL;
}

Node* insert(Node* head, int ind, Node* a) {
Node ret, * p = &ret;
ret.next = head;
// 从【虚拟头节点】开始向后走 ind 步
while (ind--) p = p->next;
// 完成节点的插入操作
a->next = p->next;
p->next = a;
// 返回真正的链表头节点地址
return ret.next;
}

//链表的遍历
void Print_Node(Node* pH)
{
//获取当前的位置
Node* p = pH;
//获取第一个节点的位置
p = p->next;
//如果当前位置的下一个节点不为空
while (p->next != NULL)
{
//(1)打印节点的数据
printf("data: %d\n", p->data);
//(2)移动到下一个节点,如果条件仍为真，则重复(1)，再(2)
p = p->next;
}
//如果当前位置的下一个节点为空，则打印数据
//说明只有一个节点
printf("data: %d\n", p->data);
}

int main()
{
int i;
Node* header = create_node(0);//给头结点赋值为0
for (i = 1; i < 10; ++i)
{
insert(header, i, i);
}
Print_Node(header);
}
老师，我这段代码哪里有错误啊，为什么编译到你提供的插入函数的时候就访问异常了呀？

作者回复

代码 BUG 尽量自己找吧，程序员的职业道德是，自己写的 bug 自己找啊~~~~~

你首先看你的 print_node 里面的 while 循环逻辑。不应该是 p->next != NULL，而是 p 就不能为 null 啊~~~，p 不为 null，才能合法访问 p->data 啊

2020-08-28 14:02:53
罗耀龙@坐忘

2020-08-08 10:52:57

茶艺师学编程

是这样吗？

struct Node *erase(struct Node *head, int ind){
struct Node ret, *p = &ret;
ret.next = head;
while(ind--)p = p->next;
p->next = NULL;
return ret.next;
}
1043

2020-04-14 15:27:39

在“数据结构 = 结构定义 + 结构操作”这个公式里结构定义已经是像乐高玩具的形状一样做好的模型，这个基本上不改动硬件设施就不能变了，在计算机中这个操作是否是操作计算机是指令系统？结构操作是以给定的形状和结构特点自己拼装，这就涉及操作是否规范了，有的操作可能带来破坏性的结果，在计算机中这个结构操作也可能出现破坏性的结果或者直接能去通过计算操作损坏硬件吗？最古老的时代有个病毒记得叫CHI还行就能损坏硬件，好像也是c语言编写的，c真的有这么大的破坏力吗？

作者回复

结构性质是自己定义的，结构操作也是你自己实现的，所以是否规范，主要看操作是否破坏结构性质。操作系统是C语言写的，你想想C语言如果要是想干坏事儿，得多容易。(｡ì _ í｡)

2020-04-14 23:56:00
webmin

2020-04-02 09:26:40

```golang
type Node struct {
Val int
Next *Node
}

func erase(head *Node, ind int) *Node {
if head == nil {
return head
}

ret := &Node{
Next: head,
}

p, prev := ret, ret
for ; ind >= 0; ind-- {
if p == nil || p.Next == nil {
return ret.Next
}
prev = p
p = p.Next
}
prev.Next = p.Next
return ret.Next
}

func NewNode(nums []int) *Node {
if len(nums) == 0 {
return nil
}
head := &Node{
Val: nums[0],
}
h := &Node{
Next: head,
}
for i := 1; i < len(nums); i++ {
head.Next = &Node{
Val: nums[i],
}
head = head.Next
}
return h.Next
}

func TestErase(t *testing.T) {
head := NewNode([]int{1, 2, 3, 4, 5, 6})
head = erase(head, 3)
for head != nil {
fmt.Printf("%d -> ", head.Val)
head = head.Next
}

fmt.Println()
fmt.Println("###########")
head = NewNode([]int{1, 2, 3, 4, 5, 6})
head = erase(head, 0)
for head != nil {
fmt.Printf("%d -> ", head.Val)
head = head.Next
}

fmt.Println()
fmt.Println("###########")
head = NewNode([]int{})
head = erase(head, 1)
for head != nil {
fmt.Printf("%d -> ", head.Val)
head = head.Next
}

fmt.Println()
fmt.Println("###########")
head = NewNode([]int{1, 2, 3, 4, 5, 6})
head = erase(head, 5)
for head != nil {
fmt.Printf("%d -> ", head.Val)
head = head.Next
}

fmt.Println()
fmt.Println("###########")
head = NewNode([]int{1, 2, 3, 4, 5, 6})
head = erase(head, 7)
for head != nil {
fmt.Printf("%d -> ", head.Val)
head = head.Next
}
}
```

作者回复

可以可以！d(^_^o)

2020-04-02 10:10:58
信念

2020-03-14 13:40:04

我记得我们上学期计算机老师专门有一节课讲过数组和链表，数组是连续的，而链表不一定是连续的

作者回复

老师说的没错！

2020-03-15 00:08:17
🤪HappyJoo

2020-02-29 08:05:42

作业：https://github.com/HappyJoo/CLearningScript/blob/master/Linked-list/2_Erase_Node.cpp
但是暂时还不清楚如何使用这个函数，等会了再来update哈~老师辛苦啦~

作者回复

代码中 ret 的类型，不是一个指针类型哦，而应该是一个实实在在的节点类型，虚拟节点，本身就是一个节点，把前面的 * 去掉就好了。

2020-03-02 10:08:28
宋jia wen

2020-02-27 10:25:30

struct Node *insert(strcut Node *head, int ind, struct Node *a)
老师这是 struct Node 型指针还是一个函数

作者回复

这是一个函数，返回值是struct Node 类型的地址。

2020-02-28 12:58:31