【数据结构】链式型存储结构-双向链表

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  小结

好了，双向链表我们就看到这里哈，有理解不对的地方欢迎指正哈。