【玩转408数据结构】线性表——双链表、循环链表和静态链表（线性表的链式表示 下）

知识回顾

��       在前面的学习中，我们已经了解到了链表（线性表的链式存储）的一些基本特点，并且深入的研究探讨了单链表的一些特性，我们知道，单链表在实现插入删除上，是要比顺序表方便的，但是，单链表中每个结点仅存在一个指针指向其后续结点，那么如果我们想要找到其前面的节点，则需要从头部开始遍历，这是十分不方便的；那么，是不是对其添加一些元素或特性，使其的操作更加简单呢？那么我们就来看下这节将要学习的一些链表。 

双链表

        我们知道，单链表中每个结点只有一个指向其后续的指针，这边可以使得单链表可以从前往后的遍历整个链表，但如果我们想要去访问某个结点的前驱节点时，则需要从头开始遍历，这样就会消耗较多的时间；那么为了解决这一问题我们引入双链表。

         我们不难观察到，双链表则是在单链表的基础上，在结点中又添加了一个指针，用于指向该结点的前驱结点，那么这样的话，我们也就可以通过一个结点很好的去查询其前驱和后继结点了，虽然我们增加了存储密度，但在对链表的操作上就更加的灵活。

结点初始化：

typedef struct DNode{int data ;struct DNode *prior, *next ;}DNode, *DLinkList;

双链表的插入

        实际上，双链表的插入是类似于单链表的插入的，只不过，由于双链表存在指向后续结点以及前驱结点的指针，所以在进行插入操作时，我们需要对这两个指针分别进行类似的操作即可。

        如图所示，我们若要在双链表中插入x，那么我们首先需要让x结点的后续指针指向插入位置后结点，之后再将插入位置后结点（c）的前驱指针指向x；之后再让x结点的前驱指针指向插入位置的前驱结点（a），之后再将插入位置的前驱结点（a）的后继指针指向x；这样我们就成功的将x插入到链表之中了。

        需要思考的是，当我们的插入位置为链表的末尾时，我们应该怎么去操作呢？这当然也不难操作，通过对双链表的观察，我们知道，在其末尾结点的后续结点会指向NULL;那么这时就不会存在一个后面的结点指向末尾结点了，也就是说，在之前我们的结点是存在两个指向结点的箭头和两个指出的箭头；但到了末尾就缺少一个指向的箭头。

        知道了这层差异，那么我们就要对其进行相应的处理，首先我们需要判断我们插入位置前的结点是否指向NULL，当其指向NULL时，则证明我们插入的为末尾结点，这里我们对前续的操作不变，只不过在对其后续操作时，我们只需要让其指向NULL（也就前末结点指向的位置）即可，不需要进行指向插入结点的操作。

        当然，插入首位的方法也同上所示，只不过从特殊处理后续操作转变为特殊处理前驱操作即可。

//插入bool InsertNextDNode(DNode *p, DNode *s) {if(p == NULL || s == NULL)return false;s->next = p->next;if(p->next != NULL) {p->next->prior = s;}p->next = s;s->prior = p;return true;}

双链表的删除

        对于删除操作，其原理也与单链表的操作类似，只不过其具有两个指针，所以我们需要更改两个指针的指向即可。

        对于双俩表的删除操作，例如我们需要删除b结点，那么我们只需要让a的后续指针指向c（b后续指针指向位置），让c的前驱指针指向a（b前驱指针指向位置），这样我们就可以删除b结点了。

        例如：删除p指针后的结点b。

p->next=q->next;q->next->prior=p;free(q);

        当然，删除前驱结点的方法也与之类似，我们更改其相应的指针指向即可。

        那我们如果删除的结点位于双链表的头部或者尾部呢？这样对于我们的操作是否存在什么影响？下面我们来看一下：（在这里我们以末结点为例，实际上头结点删除方法与其类似）

 

        当我们遇到尾结点时，由于我们末尾元素后指向NULL，所以其不存在一个指向前的指针，也就是说，如果我们想要删除末尾元素的话，我们就只需要让其前面的元素结点向后指向NULL即可，之后再释放我们想要删除的末尾结点，就可以解决这种问题了。

//删除(p后的节点） bool DeleteNextDNode(DNode *p) {if(p == NULL)return false;DNode *q = p->next;if(q == NULL)return false;p->next = q->next;if(q->next != NULL)q->next->prior = p;free(q);return true;}

双链表的遍历 

        至于遍历双链表这里由于我们前面的学习，这部分的内容就十分的简单了。我们就像单链表遍历一样，通过头指针或头结点开始从头部或者我们所指定的某一点，以此遍历其next指针，直到其指向NULL为止，那么这样我们是不是就可以成功的从头部遍历一遍链表了呢！

        乍一听，这与单链表是没什么不同的，但由于我们双链表是一个结点存在两个指针的（也就是指向前的prior以及指向后续的next）指针，所以我们在进行遍历的时候，也就可以去尝试更多的遍历方法了，我们可以尝试从后向前遍历。

        这与前面的从前向后遍历并没有什么不同，只是我们需要从尾部向头部遍历的时候需要不停的访问改结点的prior指针，直到其指向NULL为止。

//遍历//从前向后遍历void PriorFindList(DLinkList L) {DNode *p = L->next;while(p != NULL) {cout data next;}cout next != NULL) {p = p->next;}while(p!=L) {cout data prior;}cout 数组[2]->数组[1]->数组[6]->数组[3]->-1;-1则表明到达了尾部。   
优点：增、删 操作不需要大量移动元素 缺点：不能随机存取，只能从头结点开始依次往后查 找；容量固定不可变
  
适用场景：①不支持指针的低级语言；②数据元素数 量固定不变的场景（如操作系统的文件分配表FAT）
  
代码
 
双链表代码
   
// 2.4 双链表#include using namespace std ;typedef struct DNode{int data ;struct DNode *prior, *next ;}DNode, *DLinkList;//初始化bool InitDLinkList(DLinkList &L) {L = (DNode *)malloc(sizeof(DNode)) ;if(L == NULL)return false ;//分配失败 L->next = NULL;L->prior = NULL;return true;}//尾插法建立DLinkList DList_TailInsert(DLinkList &L) {int x;cin >> x;DNode *s, *r = L;while(x!=9999) {s = (DNode *)malloc(sizeof(DNode)) ;s->data = x;r->next = s;s->prior = r;r = s;cin >> x;}r->next = NULL;return L;} //插入bool InsertNextDNode(DNode *p, DNode *s) {if(p == NULL || s == NULL)return false;s->next = p->next;if(p->next != NULL) {p->next->prior = s;}p->next = s;s->prior = p;return true;}//删除(p后的节点） bool DeleteNextDNode(DNode *p) {if(p == NULL)return false;DNode *q = p->next;if(q == NULL)return false;p->next = q->next;if(q->next != NULL)q->next->prior = p;free(q);return true;}//销毁void DestoryList(DLinkList &L) {while(L->next != NULL){DeleteNextDNode(L);}free(L);L=NULL;} //遍历//从前向后遍历void PriorFindList(DLinkList L) {DNode *p = L->next;while(p != NULL) {cout data next;}cout next != NULL) {p = p->next;}while(p!=L) {cout data prior;}cout