【玩转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 << p->data << " " ;p = p->next;}cout << endl;
}
//从后向前遍历
void AfterFindList(DLinkList L) {DNode *p = L;while(p->next != NULL) {p = p->next;}while(p!=L) {cout << p->data << " " ;p = p->prior;}cout << endl;
}

循环链表

        循环链表又可以分为循环单链表和循环双链表。其原理是十分相同的。

循环单链表

        通过图我们不难看出，上面的链表是我们已经讨论过多次的单链表，其尾结点指针指向NULL，那么我们怎么使其变成循环链表呢？

        循环、循环，顾名思义，就是当我们访问某一序列最后一个元素时，紧接着我们就可以以相同的操作去访问该序列第一个元素；在这里对于链表也是相同的：也就是当我们访问的某链表的尾结点时，我们依旧可以通过常规的访问该结点的next指针的方法去访问到该链表的头结点。

        那么这样我们的思路就十分清晰了，我们就只需要在创立链表时，使其的末结点的next指针指向该链表的头结点，这样我们就可以很轻松的实现循环单链表了。

        那么我们为什么要学习单链表呢？ 

        如果我们只是使用单链表，当我们有某一结点的位置时，我们可以通过单链表的特性去合理的访问到其后面的各个结点；但其前面的结点对于我们来说就是未知的了。

        为了解决这个问题，我们就可以引入循环单链表，这样我们在得到某一结点位置后，我们依次访问最终就可以成功的访问到该链表头结点，那么我们指定结点前的区域就不再是未知的了。

 

         在引入循环链表时，我们就可以设立一个尾指针，甚至说尾指针在这里要比头指针更加的方便！我们不难知道，对于头指针来说访问链表头部需要O(1)的时间复杂度、访问尾部时需要O(n)的时间复杂度。但对于循环单链表的话，我们就可以使用O(1)的时间复杂度访问其头结点和尾结点，对于尾结点没什么好说的，因为其就指向尾结点我们直接访问即可；但对于头结点我们在访问时仅仅需要访问尾结点的next指针，由于其是循环的，所以我们就可以仅用O(1)的时间复杂度就访问到了头结点，这无疑来说节省了很多时间。那么同理，我们在遇到某些操作中包含需要查找尾结点的操作时，这样都可以节省其时间。

循环双链表 

        如上图中上方的链表一样，该链表是刚才我们已经了解过的双链表；那么其循环双链表的建立实际上是类似于循环单链表的；只不过需要注意的是，由于我们的双链表的每个结点是有两个指针的，所以我们在使其尾部指向头部时，也要去更改头部的prior指针，使其指向链表的尾，这样我们就可以实现循环双链表了。

         这里，由于循环链表于前面的单双链表相似，所以这里就不给出其完整代码实现了，实际上我们只需对一些地方的代码进行特定的修改就可以得到该循环链表的代码了。

静态链表

      通过前面的学习，我们知道，单链表各个结点的存储，在我们计算机的内存中是完全随机杂乱的，我们需要通过指针去link（连接）这些结点；那么我们可不可以在内存中申请一块连续的存储空间，去进行存储这个链表呢？

        当然这乍一听与数组十分的相似，只不过我们需要通过这一连续的存储空间去实现链表的功能，也就是需要通过next"指针"去指向后续节点。

        那么这里我们就可以参考数组，我们将结点划分为存数据的data和存下一位置的数组下标next；这样我们在存入一个元素时首先判断该数组位置是否已存入数据，若没有存入数据的话，我们将其存入，并将上一尾结点的next更新为该结点的数组下标。

        这里我们通过next去串联数组的下标，进而实现链表功能。

          例如上图所示，我们可以将结点的data默认初始化为 -2 (也就是说，当我们在某结点进行存入数据时，可以判断下其next是否为-2，若不是-2则说明该结点已经存在元素)，那么我们观察图中链表，可以看出这里我们:头->数组[2]->数组[1]->数组[6]->数组[3]->-1;-1则表明到达了尾部。

优点：增、删 操作不需要大量移动元素 缺点：不能随机存取，只能从头结点开始依次往后查 找；容量固定不可变

适用场景：①不支持指针的低级语言；②数据元素数 量固定不变的场景（如操作系统的文件分配表FAT）

代码

双链表代码

// 2.4 双链表#include <bits/stdc++.h>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 << p->data << " " ;p = p->next;}cout << endl;
}
//从后向前遍历
void AfterFindList(DLinkList L) {DNode *p = L;while(p->next != NULL) {p = p->next;}while(p!=L) {cout << p->data << " " ;p = p->prior;}cout << endl;
}int main() {DLinkList L;InitDLinkList(L);DList_TailInsert(L);PriorFindList(L);AfterFindList(L);DNode *p, *s;p = L;s = L;for(int i=0; i<=3; i++)	p = p->next;	//删去第五个值 DeleteNextDNode(p);PriorFindList(L);AfterFindList(L);return 0;
} 

 

 

尾：

        由于博主才疏学浅，总结的相关知识仅限于自我学习认知，若出现错误。望各位大神指点。在这里感谢各位。

        （由于学习的仓促，有些代码未能完全实现以及部分磨块的讲解不充分；若后期实现该代码，将会进行下一步的补充）