4种链式存储结构详解

链式存储结构，又叫链接存储结构。在计算机中用一组任意的存储单元存储线性表的数据元素。链式存储结构不要求逻辑上相邻的元素在物理位置上也相邻，因此它没有顺序存储结构所具有的弱点,但也同时失去了顺序表可随机存取的优点。

链式存储结构一般有单链表、静态链表、循环链表和双向链表。下面为大家一一介绍：

1.单链表

n个结点链结成一个链表，即为线性表的链式存储结构，因为此链表的每个结点中只包含一个指针域，所以叫做单链表，单链表是通过每个结点的指针域将线性表的数据元素按其逻辑次序链接在一起。

有的链表是带有头结点的，有的是不包含头结点的，头节点的数据域可以不存储任何信息，可以存储线性表长度等附加信息，头节点的 指针域存储指向第一个结点的指针。当链表是带有头结点的时候，就相当于火车头一样的存在，只是用来表面列车顺序开始的方向，并不乘坐客人。（链表一般都是包含头结点的）

带头结点的单链表中，头指针head指向头结点，头结点的数据域不包含任何信息，从头结点的后继结点开始存储数据信息。头指针始终不等于NULL(指针是指指向下一个元素的的信息，当为NULL时，即不指向任何元素)，head->next等于NULL的时候，链表为空。

不带头结点的单链表中的头指针head直接指向开始结点，当head等于NULL（head->=NULL）的时候，链表为空。

链表中整个链表的存取就必须从头指针开始进行，之后的每个结点就是上一个结点的后继指针指向的位置，最后一个结点（终端结点）的指针为空，通常用NULL或^表示。

2.静态链表

前面的单链表是用的指针，但是有的编程语言是没有指针这个功能的，那怎么？聪明的人总是有，有人想出了用数组来代替指针，来描述单链表，让每个数组的元素都由两个数据域组成，数组的每个下标都对应两个数据域，一个用来存放数据元素，一个用来存放next指针。我们把这种用数组描述的链表叫做静态链表。

3.循环链表

将单链表中终端结点的指针端由空指针改为指向头结点，就使整个单链表形成一个环，这种头尾相接的单链表称为单循环链表，简称循环链表。

4.双向链表

在单链表的基础上，再在每个结点中设置一个指向其前驱结点的指针域，这样一个结点既可以指向它的前面又可以指向它的下一个，我们把这种链表称为双向链表。

结点是内存中一片由用户分配的存储空间，只有一个地址用来表示它的存在，没有显式的名称，因此我们会在分配链表结点空间的时候，同时定义一个指针，来存储这片空间的地址（这个过程通俗的讲叫指针指向结点），并且常用这个指针的名称来作为结点的名称。

链式存储结构的出现实际上是为了改善顺序存储结构的缺点，逻辑上相邻的节点物理上不必相邻。同时，链式存储结构比顺序存储结构的存储密度小(链式存储结构中每个结点都由数据域与指针域两部分组成，相比顺序存储结构增加了存储空间)。本文对顺序存储结构就不过多介绍，感兴趣的小伙伴可以观看本站的数据结构和算法教程自主学习。