Unidirectional cyclic linked lists
The difference with unidirectional lists: The pointer field next of the last node of a unidirectional list is set to NULL. The pointer field NEXT of the last node of a unidirectional circular list points to the location of the initial node.
Unidirectional cyclic linked list design
- The definition of a one-way circular list is consistent with the structural design of a one-way list
// Define the node
typedef struct Node{
ElemType data;
struct Node *next;
}Node;
typedef struct Node * LinkList;
Copy the code
Unidirectional circular linked list creation
When creating linked lists, you need to consider two cases:
- Create a linked list for the first time
- The linked list has been created, and data needs to be added at the end
/* Create a loop list! There are two scenarios: (1) The system is created for the first time. YES-> create a new node and make the next of the new node point to itself; (*L)->next = (*L); NO-> find the end of the list and place next = new. Next = (*L); * /
Status CreateList(LinkList *L){
int item;
LinkList temp = NULL;
LinkList target = NULL;
printf("Enter the value of the node, enter 0 to end \n");
while(1) {
// Enter the value of the list
scanf("%d",&item);
// If 0 is entered, the input ends
if(item==0) break;
// If the input list is empty
if(*L==NULL) {
// create a new node
*L = (LinkList)malloc(sizeof(Node));
// Check whether the node is successfully created
if(! L)exit(0);
// Pass the input value to L
(*L)->data=item;
// Make the next pointer point to itself
(*L)->next=*L;
} else {
// The input list is not empty, look for the last node of the list
for(target = *L; target->next ! = *L; target = target->next);// Create a new node
temp=(LinkList)malloc(sizeof(Node));
// Check whether the node was successfully created
if(! temp)return ERROR;
/ / assignment
temp->data=item;
// Next of the new node points to the head node
temp->next=*L;
// Make next= new node for last nodetarget->next=temp; }}return OK;
}
Copy the codeIn the last code, we used a for loop to get the last node, but this approach added time complexity. So we can use a temporary pointer to record the last node, to ensure that every time new data is added, it is added to the last node and the linked list information is modified in time.
Status CreateList2(LinkList *L){
int item;
LinkList temp = NULL;
LinkList target = NULL;
// temporary node, used to record the last node
LinkList r = NULL;
printf("Please enter a new node, end when 0 is entered! \n");
while (1) {
scanf("%d",&item);
if (item == 0) {
break;
}
// Created for the first time
if(*L == NULL){
*L = (LinkList)malloc(sizeof(Node));
if(! *L)return ERROR;
(*L)->data = item;
(*L)->next = *L;
// The last node is the current node L
r = *L;
} else {
// Create a new node
temp = (LinkList)malloc(sizeof(Node));
if(! temp)return ERROR;
temp->data = item;
temp->next = *L;
// Insert temp at end r
r->next = temp;
// The latest node is the last node rr = temp; }}return OK;
}
Copy the codeUnidirectional circular linked list insertion
To insert a new node into a circular linked list, two cases need to be analyzed.
- Insert at the position of the head node
- Insert in other locations (including middle/end of list)
- Insert at the head node position
Status ListInsert(LinkList *L, int place, int num) {
LinkList temp ,target;
int i;
if (place == 1) {
// 1. Create a new node, temp, and check whether the node is successfully created
temp = (LinkList)malloc(sizeof(Node));
if (temp == NULL) {
return ERROR;
}
temp->data = num;
// 2. Find the last node in the list
for(target = *L; target->next ! = *L; target = target->next);// add temp next to *L
temp->next = *L;
// 4. Set next to temp
target->next = temp;
// 5. Finally, set header L to temp
*L = temp;
}
Copy the code- Plug it in another position
Status ListInsert2(LinkList *L, int place, int num){
LinkList temp ,target;
int i;
if(place ! =1) {
// If the insertion position is in another position;
Create a new node temp and check whether it is created successfully. If it is created successfully, the value is assigned. Otherwise, ERROR is returned.
temp = (LinkList)malloc(sizeof(Node));
if (temp == NULL) {
return ERROR;
}
temp->data = num;
If the list length is longer, the queue will be automatically inserted into the end of the queue.
for ( i = 1,target = *L; target->next ! = *L && i ! = place -1;
target = target->next,i++) ;
// set target->next = temp;
temp->next = target->next;
//4. Insert node precursor to new node, new node next to target next;
target->next = temp;
}
return OK;
}
Copy the codeUnidirectional circular linked list deleted
Unidirectional circular linked list deletion requires consideration of three cases
- The deleted location is at the head node
- When deleted, the list has only the last node
- Delete other nodes
- The deleted location is at the head node
It is necessary to determine whether there is only one node in the current circular linked list. If there is only one node, empty L directly. Otherwise, you need to find the end node of the linked list, temp, and redirect next of temp to next of L. The new node is used as the head node. Then, the original head node is released and the head node L is released
Status LinkListDelete(LinkList *L,int place){
LinkList temp,target;
int i;
//temp points to the first node of the list
temp = *L;
if(temp == NULL) return ERROR;
if (place == 1) {
// select *L from *L;
if((*L)->next == (*L)){
(*L) = NULL;
return OK;
}
// * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
// Find the end target
for(target = *L; target->next ! = *L; target = target->next);// Record the original header
temp = *L;
// the new node is used as the header
*L = (*L)->next;
// make the last node next point to the next node of the head node
target->next = *L;
// Release the original header
free(temp);
}
return OK;
}
Copy the code- Delete nodes at other locations
Status LinkListDelete(LinkList *L,int place){
LinkList temp,target;
int i;
//temp points to the first node of the list
temp = *L;
if(temp == NULL) return ERROR;
if(place ! =1) {
// If you delete other nodes -- other nodes
//1. Locate the target before deleting the target
for(i = 1,target = *L; target->next ! = *L && i ! = place- 1;
target = target->next,i++) ;
// 2. Make target->next point to the next node
temp = target->next;
target->next = temp->next;
// 3. Release the temp node to be deleted
free(temp);
}
return OK;
}
Copy the codeconclusion
When working with linked lists, some special scenarios need to be considered to ensure code robustness. For example, the position of the initial node, the position of the last node and whether it is an empty linked list, whether there is only one node in the linked list when deleting, etc.