目录
双链表
在单链表中，每个元素都附加了一个指针域，指向下一个元素的存储位置。在双向链表中，每个元素都附加了两个指针域，分别指向前驱节点和后继节点。
单链表只能向后操作，不能向前操作。为了向前、向后操作方便，可以给每个元素都附加两个指针域，一个存储前一个元素的地址，一个存储下一个元素的地址。这种链表被称为双向链表示。
从上图中可以看出，双向链表的每个节点都包含三个域：数据域和两个指针域。两个指针域分别存储前后两个元素的地址，即指向前驱节点和后继节点。
初始化（带头结点）：
typedef struct DNode{ //定义双链表结点类型 Elemtype date; //数据域 struct DNode *prior,*next; //前驱和后继指针 }DNode,*DLinklist; //初始化双链表 bool InitDLinkList(DLinklist &L){ L =(DNode*)malloc(sizeof(DNode)); if(L==NULL) return false; L->prior = NULL; L->next = NULL; }
判断链表是否为空（带头结点）
bool Empty(DLinklist L){ if(L->next == NULL) return true; else return false; }
双链表的插入:
//在p结点之后插入s结点 bool InsertDNode(DNode *p,DNode *s) { if(p==NULL||s==NULL) return false; s->next = p->next; if(p->next != NULL) //如果在尾部插入，尾部是NULL，空的不能指向 p->next->prior = s; s->prior= p; p->next = s; return true; }
双链表的遍历：
后序遍历
while(P!=NULL) { //对结点p处理如打印 p = p -> next; }
前序遍历
while(p!=NULL){ //对结点p做相应的处理 p = p -> prior; }
前向遍历(跳过头结点）
while(p->prior!=NULL) { //对结点p做相应的处理 p = p-> prior; }
双链表不可随机存取，按位查找和按值查找都只能用遍历的方式实现。时间复杂度O(n)
循环链表
在单链表中，只能向后操作，不能向前操作，如果从当前节点开始，则无法访问该节点前面的节点；
如果最后一个节点的指针指向头节点，形成一个环，就可以从任何一个节点出发，访问所有节点，这就是循环链表。
循环链表和普通链表的区别就是最后一个节点的后继指向了头节点。下面看看单链表和单向循环链表的区别。
单向循环链表最后一个节点的next域不为空，而是指向了头节点，
而单链表和单向循环链表判断空表的条件也发生了变化，单链表为空表时，L ->next=NULL；单向循环链表为空表时，L ->next=L 。
双向循环链表除了要让最后一个节点的后继指向第1个节点，还要让头节点的前驱指向最后一个节点
双向循环链表为空表时，L ->next=L ->prior=L ，如下图所示。
循环单链表的初始化
typedef struct LNode{ //定义单链表的结点类型 ElemType date; //每个结点存放一个数据元素 struct LNode *next; //指针指向下一个结点 }LNode,*LinkList; //初始化一个循环单链表 bool InitList(LinkList &L) { L = (LNode*) malloc(sizeof(LNode)); //分配一个头结点 if(L==NULL) //内存不足分配失败 return false; L->next = L； //头接点next指向头结点 return true; }
循环双链表的初始化
//初始化一个循环双链表 typedef struct DNode{ ElemType date; struct DNode *prior,*next; }DNode,*DLinklist; bool InitDLinkList(DLinklist &L){ L = (DNode *) malloc(sizeof(DNode)); //分配一个头结点 if(L==NULL) return false; L->prior = L; //头结点的prior指向头结点 L->next = L; //头结点的next指向头结点 return true; }
此时判断是否为空和判断是否为尾结点的条件就是看next是否为L
双链表的插入
由于是循环双链表，就不用考虑是不是在尾部插入
//在p结点之后插入s结点 bool InsertDNode(DNode *p,DNode *s){ s->next= p->next; p->next->prior= s; s->prior = p; p->next = s; }
双链表的删除
//删除p的后继结点q p->next = q->next; q->next->prior = p; free(q);
静态链表
链表还有另一种静态表示方式，可以用一个数组存储数据，用另一个数组记录当前数据的后继的下标。
用静态链表可以先把数据存储在一维数组data[]中，然后用后继数组next[]记录每个元素的后继下标
定义静态链表
#define Maxsize 10 //静态链表的最大长度 struct Node{ //静态链表的结构类型定义 ElemType date； //存储数据元素 int next; //下一个元素数组下标 }SLinkList[MaxSize];
插入为i的结点：
1）找到一个空的结点存入数据元素
2）从头结点出发找到位序为i-1的结点
3) 修改新的结点next
4）修改i -1 的结点next
插入
若在第6个元素之前插入一个元素25，则只需将25放入data[]数组的尾部，即data[9]=25，然后修改后继数组next[5]=9，next[9]=6
插入之后，next[5]=9，next[9]=6，也就是说节点5的后继为9，节点9的后继为6，节点6的前驱为9，节点9的后继为6
相当于节点9被插入节点5和节点6之间，即插入节点6之前。也就是说，元素49的后继为25，元素25的后继为20。这就相当于把元素25插入49、20之间。是不是也很方便？不需要移动元素，只改动后继数组就可以了。
删除
若删除第3个元素，则只需修改后继数组next[2]=4，。此时，2的后继为4，相当于把第3个元素跳过去了，实现了删除功能，而第3个元素并未被真正删除，只是它已不在链表中。这样做的好处是不需要移动大量的元素。
