关键词：

C++ "链链"不忘@必有回响之双向链表

1. 前言

写过一篇与单链表相关的博文（https://blog.51cto.com/gkcode/5681771），实际应用中，双向循环链表的功能更强大。

单链表中，查询一个已知结点的后驱结点的时间复杂度为O(1)。因结点本身不存储与前驱结点相关的地址信息，查询前驱结点需要从头结点扫描一次，所以时间复杂度是O(n)。

双向链表在结点类型中增加了可以存储前驱结点地址的指针位，如下图所示：

如此，无论查询已知结点的后驱结点还是前驱结点的时间复杂度都是O(1)，缺点是需要付出空间上的代价。

结点的类型定义：

typedef int dataType;
//结点
struct LinkNode 
	//数据成员
	dataType  data;
	//后驱结点的地址
	LinkNode *next;
	//前驱结点的地址
	LinkNode *pre;
	//构造函数
	LinkNode(dataType data) 
		this->data=data;
		this->next=NULL;
		this->pre=NULL;
	
;

2. 双向链表

双向链表中除了有存储头结点的head指针变量外，一般还会增加一个存储尾结点的tail指针变量。这样，可以实现从头至尾或从尾至头对链表进行遍历。

在双向链表中，如果尾结点的后驱指针位存储头结点地址，头结点的前驱指针位存储尾结点地址，如此形成一个首尾相连的闭环，则称此链表为双向循环链表。

双向链表需要提供对结点上的数据进行常规维护的操作，如：

• 链表初始化。
• 创建链表。
• 查找。
• 后插入、前插入。
• 删除。
• ……

算法的整体思路和单链表相似，因结点中多了一个前驱结点信息，为各种操作带来便利的同时，也多了需要关注的细节。 下文将介绍双向链表中的几个重要函数。

2.1 初始化

如果是双向循环链表，初始化时：

• head和tail指向空白头结点。
• 且head的前驱结点和tail的后驱结点也指向空白头结点。这个过程也可以放到创建链表时实现。

class LinkList 
	private:
		//头指针
		LinkNode *head;
    	//尾指针
		LinkNode *tail;
		//链表的长度
		int length;
	public:
        //构造函数
		LinkList() 
			this->initLinkList();
		
		//初始化链表
		void  initLinkList() 
             //头指针存储空白头结点地址
			this->head=new LinkNode(0);
			//尾指针和头指针位置相同
			this->tail=this->head;
             //尾结点的后驱结点是头结点
			this->tail->next=this->head;
             //头结点的前驱结点是尾结点
			this->head->pre=this->tail; 
		
       //……其它函数

2.2 创建链表

可以使用头部插入或尾部插入算法创建链表，本文仅介绍尾部插入创建算法，头部创建算法可自行了解。如下演示使用尾部创建法构建以数列7，3为数据的链表。

• 创建值为7的新结点n。

• 设置新结点n的前驱结点为原尾结点。

n->pre=tail;

• 设置新结点n的后驱结点为原尾结点的后驱结点。

n->next=tail->next;

• 设置原尾结点的后驱结点为新结点n。

tail->next=n;

• 新结点n成为新的尾结点。

tail=n;

• 设置头结点的前驱结点为新的尾结点。

head->pre=tail;

重复上述流程，最终完成链表的创建过程。

是否可以无视上述创建流程中的顺序？

全局而言，顺序基本是要遵循上述的要求，原则是新结点->尾结点->头结点。

• 新结点：先设置新结点的前驱和后驱结点的地址。新结点的相应存储位都是空白的，先设置前驱还是后驱不影响结果。
• 尾结点：修改原尾结点的后驱结点地址为新结点，原尾结点的使命完成后，再指定新结点为新的尾结点。
• 头结点：修改头结点的前驱地址为新尾结点。

编码实现：

//尾部插入方式创建链表
void createFromTail(int n) 
	LinkNode *newNode,*p,*tail;
	//头结点地址
	p=this->head;
    //尾结点地址
    tail=this->tail;
    for(int i=0; i<n; i++) 
        //构建一个新结点
        newNode=new LinkNode(0);
        cout<<"请输入结点数据"<<endl;
        cin>>newNode->data;
        //原来的尾结点成为新结点的前驱结点
        newNode->pre=tail;
        //新结点的后驱结点为原来的尾结点的后驱结点 
        newNode->next=tail->next;
        //原尾结点的后驱结点为新结点
        tail->next=newNode; 				
        //新结点成为新的尾结点
        tail=newNode;
        //头结点的前驱为新尾结点
        head->pre=tail; 
    
    this->head=p;
    this->tail=tail;

测试尾部创建：

int main(int argc, char** argv) 
	LinkList list ;
	list.createFromTail(2);
	//没删除之前
	cout<<"显示创建结果:"<<endl;
	LinkNode *head= list.getHead();
	cout<<"从头结点向尾结点方向搜索："<<endl;
	cout<<head->next->data<<endl;
	cout<<head->next->next->data<<endl;
	LinkNode *tail=list.getTail();
	cout<<"从尾结点向头结点方向搜索 ："<<endl;
	cout<<tail->data<<endl;
	cout<<tail->pre->data<<endl; 
	head=tail->next;
	cout<<"从尾结点的后驱信息位得到头结点信息 ："<<endl;
	cout<<head->next->data<<endl;
	cout<<head->next->next->data<<endl;
	return 0;	

执行结果：

2.3 查找

因双向循环链表的头尾是相连的，其查询方案可以有多种变化：

• 按位置查找： 按位置查找建议从头结点开始。
• 按值查找： 按值查找可以从头结点或从尾结点开始。
• 查询所有： 查询所有可以从头结点也可以从尾结点开始。

2.3.1 按位置查找

设空白头结点编号为0，从头结点向尾结点扫描过程中，给扫描到的结点依次编号，当查询到和指定参数相同的编号时停止。

//按位置查询结点（从头部扫描到尾部） 
LinkNode * findNodeByIndex(int index) 
    int j=0;
    LinkNode *p=this->head;
    if(index==j)
        //如果 index 值为 0 ，返回空白头结点
        return p;
    //第一个数据结点	
    p=p->next;
    //设置第一个数据结点的编号为 1 ，当然这不是绝对，可以根据自己的需要设置编号
    j=1;
    while(p!=this->head && j<index) 
        p=p->next;
        j++;
    
    if(j==index)return p;
    else return NULL;

2.3.2 按值查找

按值查找可以有 2 种方案：

• 头结点向尾结点方向查找。

//按值查询结点
LinkNode * findNodeByVal(dataType val) 
    //从第一个数据结点开始查找
    LinkNode *p=this->head->next;
    //当 p 再次指向头结点结束查找，这也空白结点存在的意义
    while(p!=this->head && p->data!=val ) 
        p=p->next;
    
    if(p!=this->head) 
        return p;
     else 
        return NULL;
    

• 尾结点向头结点方向查找。

LinkNode * findNodeByValFromTail(dataType val) 
    //从尾结点开始查找
    LinkNode *p=this->tail;
    while(p!=this->head && p->data!=val ) 
        //向头结点方向
        p=p->pre;
    
    if(p!=this->head) 
        return p;
     else 
        return NULL;
    

2.3.3 查询所有

• 从头结点向尾结点方向查询所有结点。

void showSelf() 
    if(this->head==NULL)return;
    //得到第一个数据结点
    LinkNode *p=this->head->next;
    while(p!=this->head) 
        cout<<p->data<<"\\t";
        p=p->next;
    

• 从尾结点向头结点方向查询所有结点。

void showSelf_() 
    if(this->tail==NULL)return;
    LinkNode *p=this->tail;
    while(p!=this->head) 
        cout<<p->data<<"\\t";
        p=p->pre;
    

2.4 插入

插入有前插入和后插入 2 种方案，于双向链表而言，其时间复杂度都为O(1)。

2.4.1 后插入

把新结点插入到已知结点的后面，称为后插入，其插入流程如下所示：

• 找到已知结点p，创建新结点n。

• 设置n结点的前驱结点为已知结点p，设置其后驱结点为已知结点p的后驱结点。

n->pre=p;
n->next=p->next;

• 设置p结点的后驱结点为n结点。

p->next=n;

• 设置结点n为其后驱结点的前驱结点。

n->next->pre=n;

编码实现：

	//后插入
int instertAfter(dataType val,dataType data) 
    //按值查找到结点
    LinkNode *p=this->findNodeByVal(val);
    if (p==NULL) 
        //结点不存在，返回 false
        return false;
    
    //创建新结点
    LinkNode *n=new LinkNode(0);
    n->data=data;
    //设置 p 结点为新结点的前驱结点 
    n->pre=p;
    //新结点的后驱结点为已知结点 p 的后驱结点
    n->next=p->next;
    //已知结点的后驱结点为新结点
    p->next=n;  
    //已知结点的原后驱结点的前驱结点为新结点
    n->next->pre=n;
    return true;

测试后插入：

int main(int argc, char** argv) 
	LinkList list ;
	//创建 7,3 两个结点
    list.createFromTail(2);
    //在结点 7 后面插入值为 9 的结点
	list.instertAfter(7,9);
	list.showSelf();
    return 0;

执行结果：

2.4.2 前插入

把新结点插入到已知结点的前面，称为前插入，因结点有前驱结点的地址信息，双向链表的前或后插入都较方便。

• 找到已知结点p，创建新结点n。

• 设置结点n的前驱结点为p的前驱结点，设置其后驱结点为p结点。

n->pre=p->pre;
n-next=p;

• 设置p结点的前驱结点的后驱结点为n。

p->pre->next=n;
或
n->pre->next=n;

• 设置p结点的前驱结点为n结点。

p->pre=n;

编码实现：

//前插入
int insertBefore(dataType val,dataType data) 
    //按值查找到结点
    LinkNode *p=this->findNodeByVal(val);
    if (p==NULL)
        return false;
    //查找前驱结点
    LinkNode *p1=this->head;
    while(p1->next!=p) 
        p1=p1->next;
    
    //构建新结点
    LinkNode *n=new LinkNode(0);
    n->data=data;
    //新结点的后驱为 p 结点
    n->next=p;
    //新结点的前驱为 p 的前驱
    n->pre=p->pre;
    //p 的前驱结点的后驱结点为 n
    p->pre->next=n;
    //p 的前驱结点为 n
    p->pre=n;
    return true;

测试前插入：

int main(int argc, char** argv) 
	LinkList list ;
	//创建 7,3 两个结点
	list.createFromTail(2);
    //在值为 7 的结点前面插入值为 9 的结点
	list.insertBefore(7,9);
	list.showSelf();
    return 0;

执行结果：

2.5 删除

2.5.1 删除结点

删除已知结点的基本操作流程：

• 查找到要删除的结点p。

• 找到结点p的前驱结点，设置其后驱结点为p的后驱结点。

p->pre->next=p->next;

• 找到p结点的后驱结点，设置其前驱结点为p结点的前驱结点。删除p结点。

p->next->pre=p->pre;
delete p;

编码实现：

int delNode(dataType data) 
    //按值查找到要删除的结点
    LinkNode *p= this->findNodeByVal(data);
    if (p==NULL)return false;		
    //设置 p 的前驱结点的后驱结点 
    p->pre->next=p->next;
    p->next->pre=p->pre;
    delete p;
    return true;

测试删除操作：

LinkList list ;
//创建 7,3,9 3个结点
list.createFromTail(3);
//LinkNode *res= list.findNodeByValFromTail(4);
list.delNode(3);
list.showSelf();

执行结果：

2.5.2 删除所有结点

编码实现：

void delAll() 
    LinkNode *p=this->head->next;
    //临时结点
    LinkNode *p1;
    while(p!=this->head) 
        //保留删除结点的后驱结点
        p1=p->next;
        delete p;
        p=p1;
    
    this->head=NULL;

3. 算法案例

界定数列的要求：对于一个无序数列，首先在数列中找出一个基数，然后以基数为分界点，把小于基数的数字放在基数前面，反之放在后面。

3.1 演示流程

使用双向循环链表实现界定数列的流程。

• 已知的无序数列：

• 选择基数。这里选择第一个数字 7 作为基数。保存在临时变量 tmp中。声明 2 个变量 left、right，分别指向第一个数据和最后一个数据。

• 从 right位置开始扫描整个数列，如果 right位置的数字大于 tmp中的值，则继续向左移动right指针直到遇到比 tmp中值小的数字，然后保存到 left位置。

• 对left指针的工作要求：当所处位置的数字比tmp值小时，则向右边移动直到遇到比tmp值大的数字，然后保存至right。

• 重复上述过程，直到 left和right指针重合。

• 最后把tmp中的值复制到left和right指针最后所指向的位置。最终实现以数字7界定整个数列。

3.2 算法实现

使用双向链表实现上述需求：

• 初始化链表，并以尾部插入方式（保证数列的逻辑顺序和物理顺序一致）创建数列7,3,1,9,12,5,8。

int main(int argc, char** argv) 
	LinkList list ;	
	list.createFromTail(7);
	//没删除之前
	cout<<"显示创建结果:"<<endl; 
	list.showSelf();
	return 0;

执行后结果：

• 编写界定算法。

void  baseNumBound() 
    //第一个数据结点的数据作为界定数字
    int tmp=this->head->next->data;
    //左指针，指向第一个数据结点
    LinkNode *left=this->head->next;
    //右指针，指向尾结点
    LinkNode *right=this->tail;

    while(left!=right) 
        while(left!=right && right->data>tmp) 
            //右指针向左移动
            right=right->pre;
        
        left->data=right->data;
        while(left!=right && left->data<tmp) 
            //左指针向右移动
            left=left->next;
        
        right->data=left->data;
    
    left->data=tmp;

测试代码：

int main(int argc, char** argv) 
	LinkList list ;
	list.createFromTail(7);
	//没删除之前
	cout<<"显示链表的创建结果:"<<endl;
	list.showSelf();
	list.baseNumBound();
	cout<<"\\n显示界定后的数列："<<endl;
	list.showSelf();
	return 0;

执行结果：

使用双向循环链表，实现界定数列简单、明了。

4. 总结

双向链表的结点多了一个前驱指针位，对其内部数据的维护提供了大大的便利。对于程序而言，已知数据越多，算法也将会有更大灵活伸缩空间。

念念不忘，必有回响？

...奇怪怪的表情包，我好奇的问她，你在干嘛？她说，念念不忘，必有回响。我只能很尴尬的回了她三个“duang”。　　那么，念念不忘，会有回响吗？　　念念不忘，必有回响。这句话出自民国佛学大师李叔同的《晚晴集》。原... 查看详情

2019念念不忘，2020必有回响！！！

   本来是想在过年的时候写我的2019总结的，但是现在因为某些原因就提前吧。2019也是我比较总要的一年。我从校园=>社会的过渡年。   校园尾声  在学校的时候，我也有过在外面兼职程序员之前... 查看详情

c++双向链表(代码片段)

...点帮助进行删除所以为了克服这些缺点，我们引出了双向链表。一.基本介绍双向链表它的方向是双向的 查看详情

数据结构之带头结点的循环双向链表详细图片+文字讲解(代码片段)

双向循环链表文章目录双向循环链表前言文件的创建双向链表结构的定义创建返回链表的头结点值传递时：地址传递：双向链表的销毁双向链表的打印开辟一个新结点双向链表的尾插双向链表的头插双向链表的尾删双向... 查看详情

数据结构与算法-线性表之双向链表(代码片段)

...132351、概述线性表是一种线性结构，由数组、单项链表和双向链表组成，这里讲讨论双向链表的理论知识和实现代码。双向链表和单项链表类似，双向链表由两个指针作为指针域，分别指向前驱节点和后驱节点。 查看详情

c++之容器——list的源码模拟实现(代码片段)

...t的数据结构a.插入节点b.删除节点1.list的概述list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。它的优点是每次插入或删除一个元素，... 查看详情

《链表》之带头双向循环链表(代码片段)

文章目录一、带头双向循环链表概念及结构1、1 带头双向循环链表的概念1、2 带头双向循环链表的结构二、带头双向循环链表的思路及代码实现详解2、1 带头双向循环链表实现思路2、2 带头双向循环链表的模块细节及代码实... 查看详情

双向链表的增删改查c++完整实现(代码片段)

tags:C++DSALinkedList写在前面写一下双向链表的增删改查,用C++实现.完整代码可以看我的GitHub;节点类-链表类节点classListNodepublic:intval;ListNode*prev;//前驱结点ListNode*next;//后继结点ListNode():ListNode(0,nullptr,nullptr)ListNode(intx):ListNo... 查看详情

c++算法之链表排序的代码(代码片段)

下面的资料是关于C++算法之链表排序的代码。return;while(curr)prev=curr;curr=curr->next;insert_for_sort_operation(ppNode,prev);return;b）对于待插入的节点，选择合适的位置插入即可return;while(cur)if(pNode->data<cur->data)break 查看详情

redis源码解析之通用双向链表(adlist)(代码片段)

...中广泛使用**adlist(Agenericdoublylinkedlist)**，作为一种通用的双向链表，用于简单的数据集合操作。adlist提供了基本的增删改查能力，并支持用户自定义深拷贝、释放和匹配操作来维护数据集合中的泛化数据`value`。Redis源码解析之通... 查看详情

c经典之14-双向链表存储1-10---shinepans(代码片段)

#include<stdio.h>#include<conio.h>#include<stdlib.h>//system();这个指令须要用到此头文件#include<ctype.h>//toupper要用到#include<malloc.h>//在内存管理时用到的头文件voidmain() inti; structListEntry 查看详情

数据结构之双链表(代码片段)

...序表，单链表。下面我们来实现一种新的链表---带头双向循环链表！目录一.什么是带头双向链表二.为什么要使用双向链表三.双向链表的特点四：创建项目五：接口实现1.创建结构体类型2.带头节点开辟空间3.打印 查看详情

2054=数据结构实验之链表九：双向链表(代码片段)

...%d",&p->data);20p->next=NULL;21end->next=p;22p->last=end;//双向链表其实和单向链表没啥区别，就是在下一个加了一个（上一个）。23end=p;2425for(i=0;i<m;i++)2627scanf("%d",&a);28for(p=head->next;p;p=p->next)//这里是head不是NULL;2930if(p->... 查看详情

有些念念不忘，一辈子都不会有回响

　　有些念念不忘，一辈子都不会有回响　　多少恋情没能开花结果，成了一件未完成的事，深深地印在了当事人的脑海，终生难以忘却。因为没有真实的体会到那种得到的感受，就把没有得到的东西完美化，无限地扩大他们的... 查看详情

数据结构（链表——双向链表的实现）(代码片段)

链表——双向链表的实现链表的概念及结构链表的分类带头双向循环链表的介绍（重点）双向链表的实现模型思路（独一份）双链表的各种方法实现创建结构体并创建结构体指针变量实现双向表初始化实现双向链... 查看详情

双向链表(代码片段)

　　双向链表既可以向前，也可以向后，其节点是由两个指针域，一个指向上一个节点，一个指向下一个节点，和一个数据域构成的。第一个节点的指向前一个指针为None，最后一个节点指向下一个为None　　　　代码实现：　　#... 查看详情

[数据结构]双向链表(c语言)(代码片段)

双向链表双向链表概念双向链表也叫双链表，其每个数据结点中都有两个指针，分别指向直接后继和直接前驱。在单向链表中若要找到某个节点的前驱节点，需要先遍历到这个节点，然后再遍历一次找到其前驱节点，这无疑是十... 查看详情

3-2双向链表(代码片段)

双向链表一种更复杂的链表是“双向链表”或“双面链表”。每个节点有两个链接：一个指向前一个节点，当此节点为第一个节点时，指向空值；而另一个指向下一个节点，当此节点为最后一个节点时，指向空值。&n... 查看详情