【数据结构】线性表的链式存储结构

🦄个人主页:修修修也

🎏所属专栏:数据结构

⚙️操作环境:Visual Studio 2022

顺序存储结构的不足的解决办法

从上一节我们对顺序表的讨论中可见,线性表的顺序存储结构的特点是:

逻辑关系上相邻的两个元素在物理位置(内存)上也相邻,因此可以随机存取表中任一位置元素,它的存储位置可用一个简单,直观的公式来表示.

然而,从另一方面来看,这个特点也铸成了这种存储结构的弱点:

中间或头部位置进行插入/删除数据操作,需要挪动数据,效率低下
空间不够就需要扩容.扩容有一定的消耗,其次还可能有一定空间浪费.

显然,这样的结构如果碰到数据量庞大并且需要频繁进行头插或中间插入的情况时的操作时间复杂度是极其庞大的.那么如何解决这个问题呢?我们先来思考一下导致这个问题的原因:

为什么当插入和删除时,就需要移动大量元素?仔细分析后,发现原因就在于相邻两元素的存储位置也具有邻居关系.它们编号是1,2,3,...,n,它们在内存中的位置也是挨着的,中间没有空隙,当然就无法快速介入,而删除后,当中就会留出空隙,自然需要弥补.问题就出在这里.

小A:既然问题在于元素之间没有空隙,那我们不如提前在元素之间留出一个空位方便其他元素插入,这样插入一个元素就不用挪动了.

小B:那假如我们要插入2个数据呢?

小A:那我们就留10个空位.

小B:我们要插入11个数据呢?

小A:那我们就留10000个空位!

小B:我们要插入10001个数据呢?

小A:那就不留空位了!大家随便存吧,哪有空位存哪吧!

小B:你说的对!

小A:??????

小B:就是物理上的相邻的特性导致了顺序存储的弱点,那么我们不让它们在物理上不相邻不就可以解决这个问题了.

小A:可是不在物理上相邻了,我们怎么知道下一个数据存在哪呢?

小B:你傻啊,我们存上一个数据的时候顺便存入一个下个结点的地址就可以了嘛.

上面这段对话中小A和小B交流讨论的结果就是我们接下来将要讨论线性表的另一种表示方法——链式存储结构,由于它不要求逻辑上相邻的元素在物理位置上也相邻,因此它没有顺序存储结构所具有的弱点,但同时也失去了顺序表可随机存取的优点.

线性表链式存储结构的定义

线性表的链式存储结构的特点是:

用一组任意的存储单元存储线性表的数据元素,这组存储单元可以是连续的,也可以是不连续的.

这就意味着,这些数据元素可以存在内存未被占用的任意位置.

以前在顺序结构中,每个数据元素只需要存储数据元素信息就可以了.现在链式结构中,除了要存储数据元素信息外,还要存储它的后继元素的存储地址.

因此,为了表示每个数据元素 $a_{i}$ 与其直接后继数据元素 $a_{i+1}$ 之间的逻辑关系,对数据元素 $a_{i}$ 来说,除了存储其本身的信息外,还需存储一个指示其直接后继的信息(即直接后继的存储位置).我们把存储数据元素信息的域称为数据域,把存储直接后继位置的域称为指针域.指针域中存储的信息称作指针或链.这两部分信息组成数据元素 $a_{i}$ 的存储映像,称为结点(Node).

结构图示如下:

n个结点( $a_{i}$ 的存储映像)链结成一个链表,即为线性表( $a_{1},a_{2},a_{3}...a_{n}$ )的链式存储结构,因为此链表的每个结点中只包含一个指针域,所以叫做单链表.单链表正是通过每个结点的指针域将线性表的数据元素按其逻辑次序链接在一起,如下图:

对于线性表来说,总得有个头有个尾,链表也不例外.我们把链表中第一个结点的存储位置叫做头指针,那么整个链表的存取就必须是从头指针开始进行了.之后的每一个结点,其实就是上一个的后继指针指向的位置.想象一下,最后一个结点,它的指针指向哪里?

最后一个,当然就意味着直接后继不存在了,所以我们规定,线性链表的最后一个结点指针为"空"(通常用NULL或"^"符号表示,如下图)

有时,我们为了更加方便地对链表进行操作,会在单链表的第一个结点前附设一个结点,称为头结点.

头结点的数据域可以不存储任何信息,也可以存储如线性表的长度等附加信息,头结点的指针域存储指向第一个结点的指针,如下图所示:

头指针与头结点的异同

头指针

头指针是指链表指向第一个结点的指针,若链表有头结点,则是指向头结点的指针.
头指针具有标识作用,所以常用头指针冠以链表的名字.
无论链表是否为空,头指针均不为空.头指针是链表的必要元素.

无头结点单链表示意图:

无头结点空链表示意图:

头结点

头结点是为了操作的统一和方便而设立的,放在第一元素的结点之前,其数据域一般无意义(也可存放链表的长度).
有了头结点,对在第一元素结点前插入结点和删除第一结点,其操作与其他结点的操作就统一了.
头结点不一定是链表必须要素.

带头结点单链表示意图:

带头结点空链表示意图: