typedef struct DaulNode
{
ElemType data;
struct DaulNode *prior; //前驱结点
struct DaulNode *next; //后继结点
}DaulNode, *DuLinkList;
双向链表的插入操作
插入操作其实并不复杂，不过顺序很重要，千万不要写反了。
双向链表的删除操作
程序员永远都知道，删除一个元素更加容易，你说呢？
双向链表相对于单链表来说，是更复杂一些，每个结点多了一个prior指针，对于插入和删除操作的顺序一定要格外小心，就像你的 “求生欲”。
双向链表可以有效提高算法的时间性能，说白了就是用空间来换取时间。
02.
双向链表的两个实例
题目描述：
–要求实现用户输入一个数使得26个字母的排列发生变化，例如用户输入3，输出结果：
–DEFGHIJKLMNOPQRSTUVWXYZABC
–同时需要支持负数，例如用户输入-3，输出结果：
–XYZABCDEFGHIJKLMNOPQRSTUVW
双向循环链表初始化操作（InitList()函数）执行流程：
Caesar()函数的执行过程：
维吉尼亚加密
Vigenere（维吉尼亚）加密：
当输入明文，自动生成随机密匙匹配明文中每个字母并移位加密。
维吉尼亚加密与凯撒加密最大的区别就是，凯撒加密的秘钥是固定的，而维吉尼亚加密的秘钥随机生成，下面给出该加密方法实现的主要函数，完整的工程代码后台回复 「Vigenere」 即可获得。
维吉尼亚加密算法的加密流程：
#include <stdio.h>
#include <stdlib.h>
#define OK 1
#define ERROR 0
typedef char ElemType;
typedef int Status;
typedef struct DaulNode
{
ElemType data;
struct DaulNode *prior;
struct DaulNode *next;
}DaulNode, *DuLinkList;
Status InitList(DuLinkList *L)
{
DaulNode *p, *q;
int i;
*L = (DuLinkList)malloc(sizeof(DaulNode));
if(!(*L))
{
return ERROR;
}
(*L)->next = (*L)->prior = NULL;
p = (*L);
for( i = 0; i < 26; i++)
{
q = (DaulNode *)malloc(sizeof(DaulNode));
if( !q )
return ERROR;
q->data = 'A'+i;
q->prior = p;
q->next = p->next;
p->next = q;
p = q;
}
p->next = (*L)->next;
(*L)->next->prior = p;
return OK;
}
void Caesar(DuLinkList *L, int i)
{
if( i > 0 )
{
do
{
(*L) = (*L)->next;
}while(--i);
printf("%d", i);
}
if(i < 0)
{
(*L) = (*L)->next->prior;
do
{
(*L) = (*L)->prior;
}while( ++i );
}
}
int main()
{
DuLinkList L;
int i, n;
InitList(&L);
printf("Please input n :");
scanf("%d",&n);
printf("n");
Caesar(&L, n);
for( i=0; i < 26; i++)
{
L = L->next;
printf("%c",L->data);
}
}跳表(Skip List)
在解释跳表之前，先看一个简单的有序单链表：
对于上面这个有序单链表，我们查找一个元素的平均时间复杂度为O(n)，那么是否有一种更快的方式查找元素呢？
答案是肯定的啦！我们可以通过在原始链表的基础之上，为其增加索引来解决这个问题，如下图：
我们以查找元素 6 为例，当我们在原始链表（Normal Line）上进行查找，将需要从头结点开始依次遍历直至找到值为6的结点；当我们在一级索引（Express Lane）上进行查找，将只需要从1->3->5->6，就可以找到元素6。相当于之前查找步数的一半，速度提升了一倍，那我们是否可以更快呢，当然可以，我想你已经想到啦！
通过上图可以发现，从二级索引开始，我们仅需要1->5->6，进一步的提升了查找的效率。
注意：跳表只能用于元素有序的情况
所以跳表对标的是平衡树和二分查找，是一种 插入/删除/搜索 都是O(log n) 的数据结构。1989年实现。
它最大的优势是原理简单、容易实现、方便扩展、效率更高。因此，在一些热门的项目里用来代替平衡树，如Redis、LevelDB 等。
跳表查找的时间复杂度分析：
跳表查找的空间复杂度分析：
总结：跳表的查询时间复杂度为O(log(n))，空间复杂度为O(n)。
END
