链表的三大"性状"
要搞清楚为什么链表有八大形态,就要先搞清楚链表的三大"性状".
说起"性状"这个词,大家是不是首先都会想到孟德尔的豌豆杂交实验:
你可能会疑惑,难道链表也像豌豆一样有相对性状吗?
我要告诉你,是的.而且链表的相对性状也和豌豆的相对性状一样可以"杂交".
在"杂交"出链表的八大形态之前,我们先来了解链表的三种相对性状:
一.带头链表和不带头链表
有时,我们为了更加方便地对链表进行操作,会在单链表的第一个结点前附设一个结点,称为头结点.
头结点的数据域可以不存储任何信息,也可以存储如线性表的长度等附加信息,头结点的指针域存储指向第一个结点的指针,如下图所示:
头指针与头结点的异同
头指针
- 头指针是指链表指向第一个结点的指针,若链表有头结点,则是指向头结点的指针.
- 头指针具有标识作用,所以常用头指针冠以链表的名字.
- 无论链表是否为空,头指针均不为空.头指针是链表的必要元素.
无头结点单链表示意图:
无头结点空单链表示意图:
头结点
- 头结点是为了操作的统一和方便而设立的,放在第一元素的结点之前,其数据域一般无意义(也可存放链表的长度).
- 有了头结点,对在第一元素结点前插入结点和删除第一结点,其操作与其他结点的操作就统一了.
- 头结点不一定是链表必须要素.
带头结点单链表示意图:
带头结点空单链表示意图:
二.循环链表和非循环链表
对于单链表,由于每个结点只存储了向后的指针,到了尾标志就停止了向后链的操作,这样,当中某一结点就无法找到它的前驱结点了.
举个例子,下面是北京的地铁线路图:
我们拿一号线举个例子,假设我想乘坐地铁一号线从双桥地铁站到天安门东地铁站去,那么我在双桥站登上地铁后,坐上一号线朝向苹果园的地铁就出发了.
但是因为我在地铁上玩着手机忽略了时间,等想起来才发现自己乘坐的这趟地铁已经行驶到复兴门了,那么我还能继续乘坐这趟地铁到达天安门东吗?显然是不能的.
其实这里一号线驶向苹果园的一趟地铁就有些类似于我们的单链表的结构,每个结点只能向后走,错过了就不能再回去.
但事实上,如果我们将地铁的尾站和首站连接起来,就能解决我们前面所面临的困难,如地铁10号线:
我们可以看到,地铁10号线的设计就是将整条地铁线路首尾相连,这样一趟地铁就可以在线路上一直循环,即使我乘坐10号线时错过了国贸站,但只要我有足够的恒心和毅力,等这班地铁再绕完一整圈的历程我就又可以回到国贸站.
这种将单链表中终端结点的指针端由空指针改为指向头结点,就使整个单链表形成一个环,这种头尾相接的单链表称为单循环链表,简称循环链表(circular linked list).
循环链表解决了一个很麻烦的问题:如何从当中一个结点出发,访问到链表的全部结点.
循环链表带有头结点的空链表示意图:
循环链表带有头结点的非空链表示意图:
循环链表和单链表的主要差异就在于循环遍历时的判断条件上,原来是判断p->next是否为NULL,现在则是p->next不等于头结点,则循环遍历未结束.
三.双向链表和单向链表
我们在单链表中,有了next指针,我们要查找下一个结点的时间复杂度为O(1).
可是如果我们要查找的是上一个结点的话,那最坏的时间复杂度就是O(n)了,因为我们每次都要从头开始遍历查找结点.
为了克服单向性这一缺点,我们的前辈们设计出了双向链表.
双向链表(double linked list)是在单链表的每个结点中,再设置一个指向其前驱结点的指针域.
所以在双向链表中的结点都有两个指针域,一个指向直接后继,另一个指向直接前驱.
双向链表结点结构示意图:
双向循环带有头结点的空链表示意图:
双向循环带有头结点的非空链表示意图:
对于双向链表中的某一个结点p,它后继的前驱还是它自己,即:
p->next->prev=p=p->prev->next
链表的八大形态
通过上面对链表性状的了解,我们知道了链表共有三种性状,如下:
- 有头结点/无头结点
- 非循环链表/循环链表
- 单向链表/双向链表
将链表的三种性状简单排列组合后我们就可以得到链表的八种形态了,分别是:
- 无头结点非循环单向链表
- 无头结点非循环双向链表
- 无头结点循环单向链表
- 无头结点循环双向链表
- 有头结点非循环单向链表
- 有头结点非循环双向链表
- 有头结点循环单向链表
- 有头结点循环双向链表
在以上8种链表的形态中我们最常用的是无头结点非循环单向链表和有头结点循环双向链表这两种链表结构,这两种链表的特性为:
- 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。并且这种结构在笔试面试中出现很多。
- 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。
因为这两种链表真的非常重要,所以我们必须对这两种链表的实现要十分熟悉,有关这两种链表的C语言实现详解我放在下面了,感兴趣的朋友可以直接点击链接跳转到相应文章参阅:
结语
希望通过上面的内容能对大家有所帮助,欢迎大佬们留言或私信与我交流.学海漫浩浩,我亦苦作舟!关注我,大家一起学习,一起进步!
