一文详解动态链表和静态链表的区别

1、引言

        本文主要是对动态链表和静态链表的区别进行原理上的讲解分析，先通过对顺序表和动态链表概念和特点的原理性介绍，进而引申出静态链表的作用，以及其概念。通过这些原理性的概述，最后总结归纳出动态链表和静态链表的区别。本文不对代码进行额外的讲解，只对原理进行分析以加深基础的认识，相关概念的代码应用读者可以另行在网上进行搜索详细学习。

---

2、顺序表和动态链表的特点

        首先需要明白的是，顺序表和链表都是线性表，即线性存储结构。使用线性表存储数据的方式可以这样理解，即“把所有数据用一根线串起来，再存储到物理空间中”。

        如下图左边将数据依次存储在连续的整块物理空间中，这种存储结构称为顺序存储结构（简称顺序表）；下图右边数据分散的存储在物理空间中，通过一根线保存着它们之间的逻辑关系，这种存储结构称为链式存储结构（简称链表）。可以看出每一个数据按照“一对一”的关系按照次序逐个排列。

2.1 顺序表存储结构

        顺序表对数据的物理存储结构有要求，需预先申请一整块足够大的存储空间，然后将数据依次存储起来，数据之间紧密贴合，不留一丝空隙。如下图所示，顺序表数据的 '一对一' 逻辑关系就是数据按照次序连续存储到一整块物理空间上，一个数据存储在一个位置之后紧接着就是下一个数据存储在下一个连续的位置。其数据存储方式和数组非常相似。

        使用顺序表存储数据之前，除了要申请足够大小的物理空间之外，为了方便后期使用表中的数据，顺序表还需要实时记录以下 2 项数据：（1）顺序表申请的存储容量，即总的空间大小，类似于数组的总大小；（2）顺序表的长度，也就是当前表中存储数据元素的个数。正常状态下，顺序表申请的存储容量要大于顺序表的长度。顺序表的结构表示如下：

typedef struct Table
{int * head;//声明了一个名为head的长度不确定的数组，也叫“动态数组”int length;//记录当前顺序表的长度int size;//记录顺序表分配的存储容量
}table;

2.2 链表存储结构

        链表的存储方式与顺序表截然相反，链表不限制数据的物理存储状态，换句话说，使用链表存储的数据元素，其物理存储位置不是连续的，而是随机的。什么时候存储数据，才在什么时候申请存储空间。链表数据的 '一对一' 逻辑关系就是数之间通过指针来维持，一个数据存储在一个位置之后通过指针指向下一个数据存储在下一个位置。这样的链表，也称之为"动态链表"。

        链表中每个数据的存储都由两部分组成：（1）数据元素本身，其所在的区域称为数据域；（2）指向直接后继元素的指针，所在的区域称为指针域。这两个部分组成了链表中的一个数据节点，链表实际存储的是一个一个的节点，链表数据节点的结构表示如下：

typedef struct Link
{char elem; //代表数据域struct Link * next; //代表指针域，指向直接后继元素
}link; //link为节点名，每个节点都是一个 link 结构体

2.3 顺序表和动态链表的比较

        根据以上介绍的顺序表和动态链表的存储结构特点，可以比较出两者在以下几个方面的区别：

（1）开辟空间的方式

        顺序表存储数据实行的是 "一次开辟，永久使用"，即存储数据之前先开辟好足够的存储空间，空间一旦开辟后期无法改变大小（使用动态数组malloc的情况除外）。

而动态链表则不同，动态链表存储数据时一次只开辟存储一个节点的物理空间，如果后期需要还可以再申请。

        因此，若只从开辟空间方式的角度去考虑，当存储数据的个数无法提前确定，又或是物理空间使用紧张以致无法一次性申请到足够大小的空间时，使用动态链表更有助于问题的解决。

（2）空间利用率

        顺序表的空间利用率高，而动态链表的空间利用率低。

        顺序表用一段连续的存储单元依次存储线性表的数据元素，物理空间上是连续的；动态链表用一组任意的存储单元存放线性表的元素，逻辑上连续（通过指针维持），但物理空间上不一定连续。

        动态链表在物理空间上不一定连续是由于每次只申请一个节点的空间，且空间的位置是随机的。这种申请存储空间的方式会产生很多空间碎片，一定程度上造成了空间浪费。不仅如此，由于动态链表中每个数据元素都必须携带至少一个指针，因此，动态链表对所申请空间的利用率没有顺序表高。

（3）插入元素的容量

        顺序表中，空间不够时需要扩容，扩容会有一定的消耗，扩容后可能存在一定的空间浪费；动态链表没有容量的概念，按需申请空间。

（4）存储密度

        顺序表中，其存储密度均为1，因为数组空间只用来存数据元素。而在动态链表中，每个节点除了存储数据元素自身外，还会至少存储直接后继的存储位置信息。相对于顺序表，动态链表的存储密度要低得多。

（5）时间复杂度

针对随机访问性能来说：

        顺序表随机访问一个元素可以用下标的方式直接访问，无需遍历整个表，时间复杂度为O(1)；动态链表随机访问一个元素，需要从头到尾遍历，直到寻找到该元素，时间复杂度为O(N)。

针对任意位置插入或者删除元素来说：

        顺序表可能需要按顺序搬移大量元素后进行元素的插入或删除，效率较低，时间复杂度为O(N)；动态链表中数据元素之间的逻辑关系靠的是节点之间的指针，因此在动态链表中插入或删除元素只需修改指针的指向，不需搬移大量元素，时间复杂度为O(1)。

        因此涉及访问元素的操作，而元素的插入、删除和移动操作极少的场景时，适合用顺序表；涉及元素的插入、删除和移动，而访问元素的需求很少的场景时，适合用动态链表。

---

3、为什么会有静态链表

        单站在时间复杂度的角度上来看，是否能够有一种数据结构既能够像顺序表一样快速的访问数据元素，又可以像动态链表一样可以方便的插入、删除和移动数据元素？

        静态链表就是这样一种数据结构，其属于一种线性存储结构，分配一整片连续的内存空间，各个节点集中安置，逻辑结构上相邻的数据元素，存储在指定的一块内存空间中，数据元素只允许在这块内存空间中随机存放。数据全部存储在数组中（和顺序表一样），但存储位置是随机的，数据之间"一对一"的逻辑关系通过一个整型变量（称为"游标"，和指针功能类似）维持（和链表类似）。在将数据存放到数组中时，给各个数据元素配备一个整形变量，此变量用于指明各个元素的直接后继元素所在数组中的位置下标。

        如图中a[0]~a[6]为数组下标，分配的内存空间中绿色数字为数组的数据元素，红色数字就为数组的游标变量，表示当前节点的下一个节点的数组下标。因此下标为x的数组中存放当前的数组数据元素和后继元素所在数组中的位置下标。因此可以看出静态链表是用数组来实现链式存储结构，静态链表实际上就是一个结构体数组。

        如上图：a[1]中存放的数据元素值为2，通过a[1]中存放的游标变量4可找到后继元素所在的数组a[4]；a[4]中存放的数据元素值为5，通过a[4]中存放的游标变量3可找到后继元素所在的数组a[3]；a[3]中存放的数据元素值为7，通过a[3]中存放的游标变量6可找到后继元素所在的数组a[6]。以此类推，直到某元素的游标变量为0即可停止（注意：a[0]为头结点，其不存储数据元素）。

        但是从上图中，可以看出数组中间有未使用过的空间即没有数据元素的数组成员，这样岂不是浪费了存储空间？为了使我们创建的空间能够得到充分的利用，我们还需要一条连接各个空闲位置的链表，方便我们的随取随用，这条链表也被称为备用链表。

        备用链表的作用是回收数组中未使用或之前使用过（目前未使用）的存储空间，留待后期使用。也就是说，静态链表使用数组申请的物理空间中，存有两个链表，实现不同的功能，一个用来连接数据，另一个用来连接数组中的空闲空间。

        为了适应这个，会存在一个“潜规则”，默认备用链表的表头位于数组下标为0(a[0])的位置，而数据链表的表头位于数据下标为1(a[1])的位置。备用链表的数组成员中仅存放游标。如上图所示：备用链表的连接顺序依次是：a[0]、a[2]、a[5]，数据链表的连接顺序依次是a[1]、a[3]、a[4]、a[6]。

        静态链表中设置备用链表的好处是：可以清楚地知道数组中是否有空闲位置，以便数据链表添加新数据时使用。在静态链表的插入和删除操作中，都会与备用链表有着联系，当进行插入时，则是用备用链表上面取得一个节点作为待插入的新节点，反之，当在删除时，则将从链表上删除下来的节点链接到备用链表上面。整个过程中，我们需要做的工作就是更新游标的值。

        可见静态链表由数据链表的数据链表的各个节点和的备用链表的各个节点组成，静态链表节点的结构表示如下：

typedef struct List
{int data;//数据域int cur;//游标
}list;

---

4、动态链表和静态链表的区别

        通过以上对动态链表和静态链表原理概念和各自特点的介绍，我们可以对两者的区别有一个更深的认知。

（1）链表中数据“一对一”的关系

        动态链表是靠指针来维持。

        静态链表是靠游标来维持。

（2）内存空间申请

        使用动态链表存储数据，不需要预先申请内存空间，而是在需要的时候才向内存申请。也就是说，动态链表存储数据元素的个数是不限的，想存多少就存多少。

        使用静态链表存储数据，需要预先申请足够大的一整块内存空间，也就是说，静态链表存储数据元素的个数从其创建的那一刻就已经确定，后期无法更改。

（3）物理地址

        动态链表malloc 或 free 函数动态申请或释放内存，在长度上没有限制。因为是动态申请内存的，所以每个节点的物理地址不连续

        静态链表类是似于数组方法实现的，在物理地址上是连续的，而且需要预先分配地址空间大小，所以静态链表的初始长度一般是固定的。

（4）操作方式

        使用动态链表只需操控一条存储数据的链表。当表中添加或删除数据元素时，只需要通过 malloc 或 free 函数来申请或释放空间。

        静态链表是在固定大小的存储空间内随机存储各个数据元素，使用静态链表存储数据，需要操控两条链表，一条是存储数据的数据链表，另一条是记录空闲空间位置的备用链表，便于随时分配给新添加元素使用。当表中添加或删除数据元素时，需要更新数据链表和备用链表的对应节点的值。

（5）元素的访问

        动态链表随机访问一个元素，需要从头到尾遍历，直到寻找到该元素，时间复杂度为O(N)。

        静态链表随机访问一个元素，可以类似像数组通过下标的方式，通过游标来访问，时间复杂度为O(1)。

（6）元素的插入和删除

        动态链表插入或删除元素时不用做元素的移动，修改指针域即可。

        静态链表插入或删除元素时不用做元素的移动，可以通过修改游标的值来达到。

---

↓↓↓更多技术内容和书籍资料获取，入群技术交流敬请关注“明解嵌入式”↓↓↓