《数据结构》第八篇、线性表中的链式存储

非常人贩3.jpg

顺序表必须占用一块事先分配好的、大小固定的存储空间，不便于存储空间的管理，为此有人提出可以实现存储空间的动态管理，即链式存储方式——链表。

本篇文章将学习下什么是链表，以及链表的实现。

链表存储的原理

和顺序存储不同，在链式存储中，结点之间的存储单元地址可能是不连续的。链式存储中每个结点都包含了两个部分：

存储元素本身的数据域

存储结点地址的指针域

我们在前边讲解连式存储时，提到了一些链式存储的原理，结点中的指针指向的是下一个结点，如果结点中只有指向后继结点的指针，那么这些结点组成的链表成为单向链表。

还是来张图复习一下撒

单向链表.png

一般在链表中也会有一个头结点来保存链表信息，然后有一个指针指向下一个结点，下一个结点又指向他后边的一个结点，如果这个指针没有后继结点，那么他就指向NULL。

在链表中，这些存储单元可以是不连续的，因此他可以提高空间利用率。当需要存储元素时，哪里有空闲的空间就在哪里分配，只要将分配的空间地址保存到上一个结点就可以。这样通过访问上一个元素就能找到后一个元素。

挡在链表中某一个位置插入元素时，从空闲空间中为该元素分配一个存储单元，然后将两个结点之间的指针断开，上一个结点的指针指向新分配的存储单元，新分配的结点中指针指向下一个结点。这样不需要移动原来元素的位置，效率比较高。同样，当删除链表中的某个元素时，就断开它与前后两个结点的指针，然后他的前后两个结点连接起来，同样也不需要移动原来元素的位置。与顺序表相比，在插入、删除元素方面，链表的效率要比顺序表高许多。

但是，随机查找元素时，由于链表没有像顺序表的索引标注，存储单元的空间并不连续，如果要查找某一个元素，必须先得经过他的上一个结点中的地址才能找到他，因此不管遍历哪一个元素，都必须要把他前面的那个元素都遍历后才能找到他，效率就不如顺序表的高了。

总结一句话，链表增删元素的效率比较高，但是查找元素的效率就比顺序表低了。

链式存储的实现

链表的几种操作与顺序表差不多，也是增删改查等操作，接下来我们实现一个链表。

1、创建链表（根据上图的单向链表创建）

在创建链表时，头结点中保存链表的信息，则需要创建一个结构体struct，在其中定义链表的信息与指向下一结点的指针。代码如下：

存储元素结点包含两部分内容：数据域和指针域，则也需要再定义一个struct,代码如下：

这样头结点与数据结点均已定义，为了使用方便，将两个struct用typedef重新定义新的名称，代码如下

创建链表要比创建顺序表简单一些。

顺序表中需要先为头结点分配空间，其次为数组分配一段连续空间，将这段连续空间地址保存在头结点中，然后往其中存储数据。

而创建链表时，只需要创建一个头结点，每存储一个元素就分配一个存储单元，然后将存储单元的地址保存在上一个结点的指针中即可，不需要再创建时把所有空间都分配好。

ok，我们把两个结构体定义好之后，就可以创建链表了，创建链表的代码如下：

2、获取链表大小

链表大小等信息也保存在头结点中，因此需要从头结点中获取即可，也是很简单的：

3、插入元素

在链表中插入元素要比在顺序表中快，只需要将插入位置前后指针断开，然后让前元素指针指向新元素，新元素指针指向后元素即可。

插入元素示意图

插入元素步骤1.png

插入元素步骤2.png

插入元素步骤3.png

插入元素bingo.png

代码如下：

4、查找某个元素

查找链表中的某个元素，其效率没有顺序表高，因为不管查找的元素在哪个位置，都需要将她前边的那个元素都完全遍历才能找到。查找元素的代码如下：

5、删除元素

再删除元素时，首相将被删除元素与上下结点之间的连接断开，然后将这两个上下结点重新连接，这样元素就从链表中成功删除了。示意图如下

删除元素步骤1.png

删除元素步骤2.png

删除元素bingo.png

我们看到，从链表中删除元素，也不需要移动其他元素，效率也比较高，我们看下代码吧

6、销毁链表

销毁链表时，将链表的每个结点元素释放。头结点可以释放，也可以保留，并将其置为初始化状态。代码如下：

在本例中，没有释放头结点，只是将头结点中的信息置为初始化状态了。

7、遍历打印链表

实现出链表的遍历打印函数，代码如下：

至此，链表基本的操作都已实现。

现在我们对于线性表的一些相关知识：原理及实现方式，应该有了一定的认识了，其实只要了解了其中的存储原理，思路清晰，代码实现并不难。

掌握了这两个最基本的线性表，对接下来我们学习其他数据结构会有很大帮助。

谢谢关注~~