【图解】数据结构代码领背-08

01

双链表的插入与删除：

在p之后插入s和删除p的后继结点q

既然在上节中我们学习了双链表的基本概念与结构，那么按照之前的思路，我们就要来学习双链表的插入，删除这样的基本操作。

在介绍双链表的插入操作之前，我们要弄清一个概念，在双链表中，一个结点前驱的后继是它自己，后继的前驱也是它自己，即p->next->prior = p = p->prior->next，就如同上海的下一站是苏州，那么上海下一站的前一站是哪呢？还是上海！听起来有些拗口，甚至有些多此一举。但就像人生一样，想享乐就得先努力，欲收获就得付出代价。双链表既然比单链表多了反向遍历查找的数据结构，那就要付出一些代价：指针变量更加复杂，插入和删除时需要改变两个指针变量。

01

图例

其实，插入的过程并不是很复杂，仍然是连接好相邻的指针，只不过这次要改变指向前驱和指向后继两个指针。这么说的话，其实还是比较的抽象，而我们之前一直讲的链表的代码要多画图，我们就不妨画出整个过程的示意图来帮助我们理解，见图1：

图1

很显然可以看出，整体的思路与单链表无异，多的是要改变s的前驱要指向p，而p的后继结点q的前驱要指向s。

如果插入操作能够理解的话，删除也很容易就想明白，删除p的后继结点q只需要两步，如图2所示：

图2

02

代码

下面来看插入的代码：

删除的代码：

03

总结

很显然，根据图例，我们可以把插入操作分为4步：

1.把p的后继赋值给s的后继：s->next = p->next

2.P的后继结点q的前驱指向s：p->next->prior = s,这句可以拆开来理解前半部分是p->next，即p的后继结点q，q的前驱即q->prior，也就是p->next的prior。就此，s与p的后继结点的两个指针指向完毕。

3.s的前驱指向p：s->prior = p

4.p的后继指向s：p->next = s，就此，s与p的两个指针指向完毕，插入完成。

与单链表的插入一样，我们需要关注它的顺序，前两步都用到了p->next，第4步则把p->next = s，如果把第4步提到了两者之前，则p->next提前变成了s，插入就无法继续。

我们不妨在之前画的图基础上理解记忆：先搞定s的前驱和后继（s->next = p->next；s->prior = p），再搞定后继结点的前驱（p->next->prior = s），最后解决前结点的后继（p->next = s）。

相比之下，删除操作则只需要2步：

1.P的后继赋值给q的后继：p->next = q->next

2.q的后继的前驱指向p：q->next->prior = p，这里的q->next->prior也可以像插入里的分为两部分看，一部分是q->next也就是q的后继，这个后继结点的前驱prior就是q->next->prior。

总的来说，双链表的基础操作要比单链表复杂些，毕竟它多了prior指针，所以在插入删除是要格外小心。但是仍然是个链表，像单链表一样，画好图想清楚各自的前驱和后继，问题也就不难解决。

02

静态链表结构类型描述

通过之前对链表的学习，我们不禁感慨C语言真是个好东西，它拥有指针的功能，可以轻易的操纵内存中的数据和地址，这比其他高级语言要灵活方便。但是像早期的一些编程语言，它们没有指针这一概念，链表结构按我们之前的讲法就实现不了了，怎么办？

有人就想到了用数组来代替指针。来描述单链表，不得不佩服他们的智慧，看看他们是怎么做到的。

首先我们让数组的每一个元素都由两个数据与组成，data和next。也就是说数组的每个下标都代表一个data和next。数据域data用来存放数据元素，也就是通常我们要处理的数据，而next则相当于单链表的指针，存放该元素的后继在数组的下标。

我们就把用数组描述的链表称为静态链表，如果说之前的描述还有些抽象的话，我们不妨用例子来形象的解释一下。

01

图例

假设我们已经将数据存入静态链表，比如分别存放着“甲”，“乙”，“丙”，“丁”4个数据，则它将处于图3所示的这个状态：

图3

此时甲这里就存有下一个元素乙的位置2，乙则存有下一个元素丙的位置3，而丁是最后一个元素，所以它的next设置为0。通过这个例子，我们大概就能对静态链表有了个具体的认识，下面我们来看代码。

02

代码

03

总结

根据前面的介绍，我们很容易可以看出，它与一般单链表的结构非常相似，不过在建立结构的时候则用的是数组的建立方式，这就是静态链表的特别之处。

总的来说，静态链表是为了给没有指针的高级语言设计的一种实现单链表能力的方法。尽管正常使用大家不一定用得上，但这种思考方式是特别巧妙地，应该理解这种思想以备不时之需。