双链表以及循环链表详解
有了单链表的基础之后，我们就可以进一步的看一下双链表和循环链表了。
1.双链表
- 单链表的结点当中既有数据域又有指针域数据，但是它的数据域和指针与都只有一个，指针是单向的指向后继结点的指针。一连串的好像一个骨肉相连，要吃最后一块只能从第一块吃起。为了解决这个问题，双链表登场。
-
双链表指的是有两个指针的链表，即每个结点有两个指针域，这两个指针域的作用分别是指向前驱结点以及后继结点
- 双链表的定义：
typedef struct DNode{
int data;
struct DNode *prior, *next; //两个指针，分别指向前驱和后继
}DNode, *DLinkList;
-
双链表的插入操作
殊途同归其实，和单链表的插入类似，但是要注意一点，他有好多指针。好的我们看一下简单的代码：
s->next = p->next;
p->next->prior = s; //c的前驱结点
s->prior = p;
p->next = s;
其实语句的顺序不是唯一的，但是需要注意的一点就是，要注意不能把链表断开！ -
双链表的删除操作
说了无数遍的话继续说 – 唯一的要求，保证不断链就行了。
代码：
q = p->next;
p->next = q->next;
q->next->prior = p;
free(q)
2.循环链表
- 所谓循环链表就是让最后一个结点的指针域指向第一个结点（不是头结点哦，头结点就是个不含数据域的指针～虽然这么说可能太武断，但是照着么理解是没问题的）
-
循环单链表
操作和单链表一样，唯一的不同就是尾结点的指针域指向了第一个结点。
记住图形就好啦 -
循环双链表
emmmmmm，一来没啥好说的，基操都在上面。二来好像也不怎么爱考，记住图形长啥样就行了。
3.静态链表
-
所谓静态链表，就是借助数组来描述线性表的链式存储结构，结点同样有数据域和指针域。但是静态链表的指针是数组下标，也称游标。
- 静态链表的定义如下：
#define MaxSize 50
typedef struct{
int data;
int next;
}LinkList(MaxSize);
next==-1作为静态链表的结束标志，插入删除和动态链表一样。也就是用数组下标模拟了链表的指针域。对指针运用不熟练的同学可以考虑一下这个。
4.顺序表和链表的比较
-
我觉得最重要的一点就是
随机存取
了吧。顺序表支持随机存取，说人话就是通过位置直接访问，和它在哪无关，只要有下标就能逮到他。链表是顺序存取，你能多快的逮到它取决于它躲在哪个地方。 - 其他的…具体情况具体分析吧，考也爱考随机存取。
5.典型例题
读题：时间复杂度尽可能高效，读到这句话DNA动了，经典名言空间换时间。
（1）这道题和我在上一章顺序表的那个题有异曲同工之妙，空间换时间肯定是借助辅助数组去完成一些操作。因此我们可以使用一个辅助数组记录链表中已出现的数值。
因为data的绝对值小于等于n，因此我们开辟一个大小为n+1的数组a，比如data小于3，那么有0，1，2，3.让辅助数组中的元素初值为0，依次扫描链表中的所有结点，扫描的
同时
检查a[|data|],如果a[|data|]的值为0，那么置1，如果a[|data|]的值为1，那么删除当前链表中的结点。
（2）代码：代码当伪代码看看就好了，按照逻辑想法写的，不一定正确，看个热闹就行了
typedef struct Node{
int data;
struct Node *next;
}Node, *PNode;
void(PNode P, int n){
int a[n+1];
PNode *l = P; //l赋值为头结点
for(int i=0;i<n+1;i++)
a[i] = 0;
while(l->next!=NULL){
k = l.data;
if(k<0)
k *= -1;
if(a[k]==0)
a[k] = 1;
l = l -> next;
q = l->next;
l->next=q->next; //指针自动后移了，不需要再特意的去移动指针
free(q)
}
}
（3）时间、空间复杂度都是O(n)
（1）要求空间复杂度低并且时间高效，DNA这次不动了。像这样要求改变链表元素顺序并且还要求空间复杂度低的，一般都是搞两个指针，让他们换着玩儿。
先把链表折半，后半段的链表逆置，然后前半段链表和后半段链表你一个结点我一个结点的凑成一个新链表。
（2）代码(换成我绝对不会这么写，我最多使用两到三个指针，通过遍历去找位置，多写几个for循环，平行的for循环不会增加时间复杂度，因此关于代码的写法还是人各有志，没有所谓的标准答案，因此也不用纠结，最重要的反而是第一问，明白算法的思想之后，就算用伪代码去写，也能写出个答案来)：
void change(NODE *h){
NODE *p, *q, *r, *s;
p = h;
q = h;
while(q->next!=NULL){
p = p->next;
q = q->next;
if(q->next!=NULL)
q = q->next; //p到链表的中间时，q就到链表结尾了
}
q = p->next;
q->next = NULL;
while(q!=NULL){
r = q->next;
q->next=p->next;
p->next=q;
q=r;
}
s=h->next;
q=p->next;
p->next=NULL;
while(q!=NULL){
r=q->next;
q->next=s->next;
s->next=q;
s=q->next;
q=r;
}
}
(3)时间复杂度O(n)
总结：线性表到此结束，我觉得最重要的还是拿笔去推一推，看看各个结点之间的逻辑关系。不是很难！