1 前言
只要大家坐过火车,对于双向链表的理解就相当简单。双向链表就是在单链表的基础之上,为每一个结点增加了它的前继结点,我们来看看。
2 双向链表
双向链表的定义如下:
typedef struct DaulNode { ElemType data; struct DaulNode *prior; //前驱结点 struct DaulNode *next; //后继结点 }DaulNode, *DuLinkList;
下图可以更直观地反映双向链表的形式:
单链表存在循环链表,双向链表也有循环链表:
3 双向链表的操作
3.1 双向链表的插入
插入操作其实并不复杂,不过顺序很重要,千万不要写反了。
3.2 双向链表的删除
双向链表相对于单链表来说,是更复杂一些,每个结点多了一个prior指针,对于插入和删除操作的顺序一定要格外小心,就像你的 “求生欲”。双向链表可以有效提高算法的时间性能,说白了就是用空间来换取时间。
4 引申
我们趁着链式结构的最后一篇,引申一个链式结构有关的跳表,在解释跳表之前,先看一个简单的有序单链表:
对于上面这个有序单链表,我们查找一个元素的平均时间复杂度为O(n),那么是否有一种更快的方式查找元素呢?
答案是肯定的啦!我们可以通过在原始链表的基础之上,为其增加索引来解决这个问题,如下图:
我们以查找元素 6 为例,当我们在原始链表(Normal Line)上进行查找,将需要从头结点开始依次遍历直至找到值为6的结点;当我们在一级索引(Express Lane)上进行查找,将只需要从1->3->5->6,就可以找到元素6。相当于之前查找步数的一半,速度提升了一倍,那我们是否可以更快呢,当然可以,我想你已经想到啦!
通过上图可以发现,从二级索引开始,我们仅需要1->5->6,进一步的提升了查找的效率。
注意:跳表只能用于元素有序的情况
所以跳表对标的是平衡树和二分查找,是一种 插入/删除/搜索 都是O(log n) 的数据结构。
可以看到跳表也是类似拿空间换时间的,跳表的查询时间复杂度为O(log(n)),空间复杂度为O(n)。它最大的优势是原理简单、容易实现、方便扩展、效率更高。因此,在一些热门的项目里用来代替平衡树,如Redis、LevelDB 等。
5 小结
好了,双向链表我们就看到这里哈,有理解不对的地方欢迎指正哈。
标签:结点,跳表,单链,链式,链表,查找,双向,数据结构 From: https://www.cnblogs.com/kukuxjx/p/17365775.html