从头详细了解单链表、双向链表，循环链表的构建及操作【c++】_循环链表的创建 c++

目录

引入

单链表

创建链表的准备

链表的创建

链表的插入

链表的删除

链表的打印 

举例 插入节点、按数据删除节点、打印链表数据 的代码实现

双向链表

循环链表

---

引入

自引用结构体：

即在结构体中包含了一个指向与其类型相同的结构体的指针成员。例如下面的例子：

struct node{
    int data;
    struct node* nextPtr
}

定义了一个 struct node ，其中包含一个数据成员 data 和一个指针成员 nextPtr，而nextPtr是一个指向该类型结构体的指针，所以称该结构体为自引用结构体。其中的nextPtr起到链接作用，在它的指向下，一个节点可以找到它下一个的节点，如此许多节点相链接便形成了一个链表。

动态内存分配：

程序中会包含许多动态数据结构，链表就是其中之一，因为在运行时所占用的内存是不能在程序运行之前确定的，所以我们就需要动态内存分配使程序具备需要时从系统中获取内存空间，不需要时可以释放掉这些内存的能力。在C语言中使用的是malloc、calloc、realloc、free来实现内存的动态分配，而在C++中，以上函数也可以使用，但还是推荐使用new和delete来实现内存动态分配。

数组与链表：

既然一组相同的数据可以存储在数组中，那还要链表干什么呢？那肯定是因为链表有很多数组没有的优点啦！

1. 链表是动态的而数组是静态的，在程序运行时我们可以根据需要对链表进行增加和缩短，但数组大小是在编译时确定的不能改变。
2. 链表的长度不受限制（除非是内存不够），但数组却很容易装满。
3. 当然你可以声明一个足够大的数组，让它可存储的数据数量大于预期的数据数量，但这样会造成内存浪费，使用链表则可以提高内存的利用率。
4. 在一个数组中插入或删除一个元素十分耗时，因为其后的每个元素都要相应的移动，而插入链表的操作时间复杂度为O(1)。
5. 因为数组在内存中连续分布，所以你可以通过下标访问法快速访问某个数据，而链表中的内存并不是连续分布的，所以必须要从头开始逐个访问，这是很耗费时间的。

单链表

这里讲单链表两个基本操作：插入和删除。

创建链表的准备

首先，我们需要一个节点，节点如上面的自引用结构体，分为数据部分与指针部分，如下图

 

然后需要一个空的头节点head，让headPtr指向头节点（注意headPtr指向在操作中不会改变，也尽量不要改变），如下图：

 链表的创建

     步骤：

1.  new一个新的节点，并定义一个指针temp指向新建的节点，新建节点的nextPtr设为NULL。
2. 将链表的tailPtr指针（这个图里没有写，其实就是一个指向链表最后一个节点的指针，会随着链表的增加而改变，在下面的图里tailPtr==headPtr）指向的节点即末尾节点的nextPtr指向新建的节点，完成链接。
3. 让tailPtr等于temp，此时tailPtr指向了新的末尾节点。

 创建链表的代码：

insertNode(NodePtr& tail,int num){ //只写了核心的代码
    NodePtr temp=new Node; // 对应步骤1
    temp->data=num;
    temp->nextPtr=NULL;
    tail->nextPtr=temp; //对应步骤2
    tail=temp; //对应步骤3
}

链表的插入

 步骤：

1.  new一个新的节点，并定义一个指针temp指向新建的节点，新建节点的nextPtr指向front的后一个节点。
2. 将front节点的nextPtr指向新建节点，完成链接。

 

插入链表的代码：

insertNode(NodePtr front,int num){ //将数据num插入到front指向的节点后
    NodePtr temp=new Node; //新建一个节点，并让temp指向它
    temp->data=num; //将数据num存入新建节点
    temp->nextPtr=front->nextPtr; //将temp的nextPtr指向front的后一个节点
    front->nextPtr=temp; //将front的nextPtr指向新建节点，完成链接
}

链表的删除

步骤：

1. 找到待删除的节点，其中Ptr2为指向待删除节点的指针，Ptr1为指向待删除节点前一个节点的指针（用了两个指针，因为链表的遍历是不能回头的，错过了就错过了哦。而链接的时候又需要将待删除节点的前一个节点与待删除结点的后一个节点相链接，所以必须有一个指针指向待删除结点的前一个节点）。
2. 定位到待删除节点后执行删除操作，首先将Ptr1指向节点的nextPtr指向待删除节点的后一个节点。
3. 删除Ptr2指针指向的节点。

删除的代码： 

void deleteNode(){//这里只写了删除的核心代码
    Ptr1->nextPtr=Ptr2->nextPtr;
    //std::cout<<Ptr2->data<<std::endl; //这一段看需要写，如果需要输出delete的数据
    delete Ptr2;
}

链表的打印 

循环正向打印法：

void Print(NodePtr head){ //传入的是第一个空的头节点
	NodePtr temp=head->nextPtr; //temp指针指向第一个非空节点
	while(temp!=NULL){ //如果temp不是结尾NULL
		cout<<temp->data<<' '; //输出节点数据
		temp=temp->nextPtr; //指针移动到下一个节点
	}
	cout<<endl;
}

 这里初始化temp为head->nextPtr的原因是我传入的是head空节点，并没有数据，应该移动到第一个有数据的节点即head ->nextPtr所指向的节点。如果传入的就是第一个有数据的节点，那么这里的初始化就应该为 temp=head; 。

递归正向打印法：

void PrintAllData(NodePtr head){
	head=head->nextPtr;
	cout<<head->data<<' ';
	if(head->nextPtr!=NULL) PrintAllData(head);
	return;
}

 从第一个有数据的节点开始，打印节点中的数据后再次调用该函数移动到下一个节点，如此循环往复直到访问到最后的NULL，此时打印完所有节点的数据。

递归逆向打印法：

void RePrintAllData(NodePtr head){
	head=head->nextPtr;
	if(head->nextPtr!=NULL) RePrintAllData(head);
	cout<<head->data<<' ';
	return;
}

从第一个节点开始，如果该节点下一个不是NULL那么就先往下一个节点访问 （如果该节点的下一个节点是NULL那么该节点就是最后一个有数据的节点）直到最后一个有数据的节点。然后开始打印节点数据，打印完后再返回前一个节点，再打印，如此直到打印完第一个有数据节点的数据。

举例 插入节点、按数据删除节点、打印链表数据 的代码实现

#include <iostream>
using namespace std;
typedef struct node{ //c++可以不用typedef，结构名可以指代结构体，但c必须typedef
	int data;
	struct node* nextPtr;
}Node;
typedef struct node* NodePtr;
 
void insertNode(NodePtr& tail,int num){ //按引用传递将改变主函数中的 tailPtr ,这里只是插到尾部
	NodePtr temp=new Node; //新建一个节点 
	temp->data=num; //存入数据 
	temp->nextPtr=NULL; //节点的 nextPtr设为 NULL,此节点将作为新的尾节点 
	tail->nextPtr=temp; //将 temp接到 tail上, 成为新尾节点 
	tail=temp; //tail 指向当前尾节点 
}
 
void deleteNode(NodePtr head,int num){//num为待删除的元素,如果没有待删除的元素就不进行任何操作
	NodePtr Ptr1=head,Ptr2=head->nextPtr;//Ptr1所在位置是Ptr2前一个节点,Ptr2为待删除节点 
	while(Ptr2!=NULL&&Ptr2->data!=num){ //当 Ptr2不是结尾,同时 Ptr2的 data不是要找的 
		Ptr1=Ptr1->nextPtr;//两个指针分别指向它的下一个节点 
		Ptr2=Ptr2->nextPtr;
	}
	if(Ptr2!=NULL){ //当 Ptr2有数据时(即指针不在结尾),将删除改节点 
		Ptr1->nextPtr=Ptr2->nextPtr; //将 Ptr1所指的节点绕过 Ptr2所指节点连接到 Ptr2后一个节点 
		delete Ptr2; //删掉 Ptr2节点 
	}
	
}
 
void deleteAllNode(NodePtr& ptr){ //递归删除所有动态分配的节点 ，这里用循环也可以实现顺序的删除
	if(ptr==NULL) return;
	deleteAllNode(ptr->nextPtr);
	delete ptr;
	return;
}
 
int main(){
	Node head;
	head.nextPtr=NULL;
	NodePtr headPtr=&head,tailPtr=headPtr,temp;
	int n,data;
	cin>>n;
	for(int i=0;i<n;i++){//构建单链表 
		cin>>data;
		insertNode(tailPtr,data);
	}
	
	temp=headPtr->nextPtr;
	while(temp!=NULL){//打印链表所有元素 
		cout<<temp->data<<endl;
		temp=temp->nextPtr;
	}
	
	deleteNode(headPtr,data);//删除最后输入的元素(这里可以根据数据删除对应的节点,但是main函数需要稍微改一下，很简单就不写了)
	
	temp=headPtr->nextPtr;
	while(temp!=NULL){//打印链表所有元素 
		cout<<temp->data<<endl;
		temp=temp->nextPtr;
	}
    deleteAllNode(headPtr);
} 

双向链表

双向链表顾名思义就是可以向两个方向访问节点的链表，其指针域包含两个指针，一个指向前一个节点，另一个指向后一个节点（后面我用leftPtr代表指向前一个节点的指针，用rightPtr代表指向后一个节点的指针）。

逻辑上来看（因为内存上不连续哦），双向链表是这个样子的：

typedef struct node{
	int data;
	struct node* leftPtr;
	struct node* rightPtr;
}Node;
typedef struct node* NodePtr;

在创建、插入、删除节点时，注意要操作两个指针，其他与单链表的操作方法是一致的。

创建代码：

void creatNode(NodePtr& tail,int num){
	NodePtr temp=new Node; //新建节点 
	temp->data=num; //存储数据 
	temp->leftPtr=tail; //新节点的左指针指向链表的尾节点 
	temp->rightPtr=NULL; //新节点的右指针指向NULL 
	tail->rightPtr=temp; //尾节点的右指针指向新节点 
	tail=temp; //新节点成为尾节点 
}

插入代码：

void insertNode(NodePtr front,int num){ //插入到front所指的节点与behind所指节点之间
	//已知 behind==front->rightPtr,所以这里只传了一个指针形参 
	NodePtr temp=new Node; //新建节点 
	temp->data=num; //存储数据 
	temp->leftPtr=front; //新节点的左指针指向前一个节点 
	temp->rightPtr=front->rightPtr; //新节点的右指针指向front的后一个节点 
	front->rightPtr->leftPtr=temp; //behind节点的左指针指向新节点,完成此步后不front再是behind的前一个节点 
	front->rightPtr=temp; //front的右节点指向新节点,完成此步后behind不再是front的后一个节点
}

 删除代码：

void deleteNode(NodePtr ptr){ //删除ptr所指的节点 
	ptr->leftPtr->rightPtr=ptr->rightPtr; //ptr前一个节点的右指针指向ptr后一个节点 
	ptr->rightPtr->leftPtr=ptr->leftPtr; //ptr后一个节点的左指针指向ptr前一个节点 
	//std::cout<<ptr->data<<std::endl; //如果要输出删除的节点数据 
	delete ptr; //删除ptr节点 
}

循环链表

循环链表就是单链表（或双向链表）首尾相接构成一个环，让尾节点的nextPtr指向头节点（尾节点的rightPtr指向头节点，头结点的leftPtr指向尾节点）。

下面用一个例题来体验一下吧(我的解析放在题目下面了哦）！题目来源于洛谷-->洛谷题目链接

 对于这道题，很容易就会联想到双向循环链表，所以用它来模拟这个过程是最符合我们的理解的，你可以试着用循环链表写一写，但是这个题用链表会超时哦，所以我用了数组来模拟双向循环链表。

采用数组模拟的代码如下：

#include <iostream>
using namespace std;
typedef struct{
	char name[10];
	int facenum;
}person; 
int main(){
	person group[100000]={0};
	int pernum,ordernum;
	cin>>pernum>>ordernum;
	int i;
	for(i=0;i<pernum;i++){
		cin>>group[i].facenum>>group[i].name;
	}
	int direction,step,temp=0;
	for(i=0;i<ordernum;i++){
		cin>>direction>>step;
		if(direction^group[temp].facenum){
			temp+=step;
		}
		else{
			temp-=step;
		}
		if(temp<0) temp+=pernum;
		else if(temp>=pernum) temp-=pernum;
	}
	cout<<group[temp].name<<endl;
}