catalogue
Familiar with circular linked list
Definition of circular chain header node and data node
Creation of circular linked list
Insertion of circular linked list data node
Deletion of circular linked list data node
Traversal and printing of circular linked list
Familiar with circular linked list
After learning the single linked list and advanced double linked list, you need to further learn the circular linked list. As the name suggests, the head and tail of this linked list are connected to form a ring (that is, the subsequent pointer of the tail node points to the first node). There is little difference between other single linked lists, but the circular linked list can access all other nodes from any node in the list, both before and after, This is also the advantage that single linked list does not have. There are many kinds of circular linked list, including single circular linked list, double circular linked list and many kinds of circular linked list. Here we only study single circular linked list. The following figure is a kind of single cycle chain.
As can be seen from the figure, the circular linked list has no NULL pointer, so the termination condition also changes. Let's enter the text below:
Definition of circular chain header node and data node
Here, we still choose to define the header structure and data node structure to make the linked list. The definition of circular linked list is the same as that of single linked list. I won't say more here. I will directly provide the code:
typedef struct header//Head node structure
{
int length;//Save circular linked list information
struct node* next;//Point to the first data node
}head;
typedef struct node//Data node structure
{
int val;//Data domain
struct node* next;//Pointer field
}node;In this way, the structure of the head node and data node can be defined. We can directly reference it when we need it. Next, let's create a single cycle linked list
Creation of circular linked list
When you create a node in the same form as the linked list, you can add a data header to the node, so you can use the following code to create a small linked list:
head* listcreat()
{
head* p;//Define header node
p=(head*)malloc(sizeof(head));
p->next=NULL;//There is no data node at this time, so the header node points to NULL
p->length=0;//Initialize header node
return p;//Return the created header node address
}An initial header node is created. Use a graph to show the linked list. The current situation is as follows
Insertion of circular linked list data node
In fact, the insertion of data nodes in the circular linked list is not complicated. The main reason is that the head insertion and tail insertion are a little difficult compared with the single linked list. It is suggested that you can draw a sketch in that book (very easy to use). The insertion of other positions is the same as the operation of the single linked list, and the code is attached directly:
void listinsert(head* p,int pos,int x)//Head node, position to be inserted, element to be inserted
{
if(p==NULL||pos<0||pos>p->length)//Robustness judgment
{
printf("listinsert():error\n");
return;
}
node* temp=(node*)malloc(sizeof(node));For the data to insert temp Allocate space
temp->val=x;//Populate data fields
node* pcur=p->next;//Define a pointer to the first data node
node* plast=p->next;//Point to the first node for easy traversal
while(pcur!=NULL&&plast->next!=pcur)//Make plast point to the last node
{
plast=plast->next;
}
if(p->length==0)//Judge whether the circular linked list is empty
{
p->next=temp;
temp->next=temp;
}
else if(pos==0)//Head insert
{
plast->next=temp;
temp->next=pcur;
p->next=temp;
}
else if(pos==p->length)//Tail insertion
{
plast->next=temp;
temp->next=pcur;
}
else
{
node* pval=p->next;//pval is used to point to the data node where you want to insert it
for(int i=1;i<pos;i++)
{
pval=pval->next;
}
temp->next=pval->next;
pval->next=temp;
}
p->length++;//Record the changes of the circular linked list
return;
}The insertion function of the data node is encapsulated successfully. Finally, the data node in the circular linked list is deleted.
Deletion of circular linked list data node
After understanding the characteristics of the circular linked list and the difference between the circular linked list and the single linked list, the problem of deleting data nodes can also be solved. However, note that the deletion of data nodes in the circular linked list, like the double linked list, needs to be analyzed by inserting the head and tail separately, and when there is only one data node in the list, it also needs to be analyzed separately. The specific code is as follows:
void listdelete(head* p,int x)//Header node, the element to be deleted
{
node* temp;//temp will point to the node to be deleted later
temp=p->next;
for(int i=0;i<p->length;i++)//Traverse the linked list to find the data node to be deleted
{
if(temp->val==x)
{
break;
}
temp=temp->next;
}
if(temp->val!=x)//No corresponding data node found
{
printf("listdelete():error\n");
return;
}
node* pcur=p->next;//pcur points to the first node
node* plast=p->next;//plast is used to point to the last node
while(plast->next!=pcur)//Move plast to the last node
{
plast=plast->next;
}
if(p->length==1)//When there is only one data node in the circular linked list
{
p->next=NULL;
}
else if(temp==pcur)//When the first node is deleted
{
p->next=pcur->next;
plast->next=pcur->next;
}
else if(temp==plast)//When the last node is deleted
{
node* pre=p->next;//Define a pointer to the penultimate node later
while(pre->next!=plast)
{
pre=pre->next;
}
pre->next=pcur;
}
else
{
node* pre=p->next;
while(pre->next!=temp)//Make pre point to the previous element of temp (note that the pre here is not the pre above)
{
pre=pre->next;
}
pre->next=temp->next;
}
p->length--;//Record the changes of the circular linked list
}Traversal and printing of circular linked list
In order to facilitate practical operation, the printout of the circular linked list can also be encapsulated into a function, as follows:
void listprint(head* p)//Head node
{
if(p==NULL||p->length==0)//Robustness judgment
{
printf("listprint():error");
return;
}
node* temp=p->next;
for(int i=0;i<p->length;i++)//Note the end condition of traversal at this time
{
printf("%d ",temp->val);
temp=temp->next;
}
printf("\n");
return;
}When printing and outputting a single cycle linked list, it is worth noting the end condition during traversal. Because the cycle linked list no longer has a NULL pointer, the end condition also changes. At this time, the size of the linked list recorded in the header node plays a role.
Complete code
The operations of circular linked list are far more than these. I won't write them one by one here, but I think after understanding these operations, other operations will become simpler. The complete code for the comprehensive use of these functions is as follows, which can be selected according to needs:
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct header
{
int length;
struct node* next;
}head;
typedef struct node
{
int val;
struct node* next;
}node;
head* listcreat()
{
head* p;
p=(head*)malloc(sizeof(head));
p->next=NULL;
p->length=0;
return p;
}
void listinsert(head* p,int pos,int x)
{
if(p==NULL||pos<0||pos>p->length)
{
printf("listinsert():error\n");
return;
}
node* temp=(node*)malloc(sizeof(node));
temp->val=x;
node* pcur=p->next;//Point to the first data node
node* plast=p->next;//Point to the last data node
while(pcur!=NULL&&plast->next!=pcur)//Make plast point to the last node
{
plast=plast->next;
}
if(p->length==0)//Judge whether the circular linked list is empty
{
p->next=temp;
temp->next=temp;
}
else if(pos==0)//Head insert
{
plast->next=temp;
temp->next=pcur;
p->next=temp;
}
else if(pos==p->length)//Tail insertion
{
plast->next=temp;
temp->next=pcur;
}
else
{
node* pval=p->next;//pval is used to point to the data node where you want to insert it
for(int i=1;i<pos;i++)
{
pval=pval->next;
}
temp->next=pval->next;
pval->next=temp;
}
p->length++;
return;
}
void listdelete(head* p,int x)
{
node* temp;//temp points to the node to be deleted
temp=p->next;
for(int i=0;i<p->length;i++)
{
if(temp->val==x)
{
break;
}
temp=temp->next;
}
if(temp->val!=x)
{
printf("listdelete():error\n");
return;
}
node* pcur=p->next;//pcur points to the first node
node* plast=p->next;//plast is used to point to the last node
while(plast->next!=pcur)
{
plast=plast->next;
}
if(p->length==1)//When there is only one element
{
p->next=NULL;
}
else if(temp==pcur)//The first node is deleted
{
p->next=pcur->next;
plast->next=pcur->next;
}
else if(temp==plast)//The last node is deleted
{
node* pre=p->next;//Point to the penultimate node
while(pre->next!=plast)
{
pre=pre->next;
}
pre->next=pcur;
}
else
{
node* pre=p->next;
while(pre->next!=temp)//Make pre point to the previous element of temp
{
pre=pre->next;
}
pre->next=temp->next;
}
p->length--;
}
void listprint(head* p)
{
if(p==NULL||p->length==0)
{
printf("listprint():error");
return;
}
node* temp=p->next;
for(int i=0;i<p->length;i++)
{
printf("%d ",temp->val);
temp=temp->next;
}
printf("\n");
return;
}
int main()
{
head* p;
p=listcreat();
int number;
printf("Please enter the initial number of data nodes of the circular linked list\n");
scanf("%d",&number);
int a[number];
printf("Please fill in the data nodes in turn\n");
for(int i=0;i<number;i++)
{
scanf("%d",&a[i]);
}
for(int i=number-1;i>=0;i--)
{
listinsert(p,0,a[i]);
}
printf("Output initial linked list\n");
listprint(p);
printf("Please enter the insertion location and element\n");
int m,n;
scanf("%d%d",&m,&n);
listinsert(p,m,n);
printf("Output the inserted linked list\n");
listprint(p);
printf("Please enter the element to delete\n");
int del;
scanf("%d",&del);
listdelete(p,del);
printf("Output the deleted linked list\n");
listprint(p);
}Just write some data and run it. It's the following effect. I've just learned c language for half a year. Please forgive me for any imperfections. Thank you for reading.
Please enter the initial number of data nodes of the circular linked list
6
Please fill in the data nodes in turn
1 2 3 4 5 6
Output initial linked list
1 2 3 4 5 6
Please enter the insertion location and element
6 7
Output the inserted linked list
1 2 3 4 5 6 7
Please enter the element to delete
5
Output the deleted linked list
1 2 3 4 6 7
Note: This article needs a certain foundation of single linked list. If you want to know about single linked list, you can also see my previous blog. Click this link to directly enter: C language data structure chapter - the creation, insertion, node deletion and printing of single linked list_ Grande joie's blog - CSDN blog