The benefits of using header nodes have been introduced in 01– one-way lists. In order to give you a better understanding of the benefits of using header nodes, this article does not include header nodes in the design of one-way lists. See how cumbersome it is to implement a one-way list without adding a head node.

Unidirectional cyclic linked lists

The biggest difference between a one-way circular list and a one-way linked list is that each data element has a precursor and a successor, making the whole one-way circular list form a ring, as shown in the figure:

  • The first element nodeIs preceded by a tail node, followed by its last node;
  • End nodeIs followed by the primary node, and the precursor is its previous node;
  • The other nodesIs preceded by its previous node, followed by its last node;

The preparatory work

Create a macOS command line project and prepare the following data in main.c:

#define ERROR 0 #define TRUE 1 #define FALSE 0 #define OK 1 #define MAXSIZE 20 */ typedef int Status; / / typedef int ElemType; / / typedef int ElemType; /* ElemType specifies the value of the value. The value is assumed to be int */Copy the code

Define node:

typedef struct Node{ ElemType data; Struct Node *next; // Pointer field}Node; typedef struct Node * LinkList; // Rename the structure typeCopy the code

A, create,

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) { scanf("%d",&item); if(item == 0) break; // If the input list is empty. If (*L == NULL) {*L = (LinkList)malloc(sizeof(Node)); if(! L) return ERROR; (*L)->data = item; (*L)->next = *L; } else {// The input list is not empty, find the last node of the list, make the last node next= new node. For (target = *L; target->next ! = *L; target = target->next); temp = (LinkList)malloc(sizeof(Node)); if(! temp) return ERROR; temp->data = item; temp->next = *L; // The new node points to the primary node target->next = temp; // The tail node points to the new node}} return OK; }Copy the code

The abovecreateThe logic of a one-way circular linked list usesThe tail interpolation, roughly using a while loop to recursively create a one-way loop linked list with scanf input data as node data:

  • For the first time,When a node is inserted, a node is created that isThe first element nodeIs alsoEnd node, so its next points toTheir own;
  • If the data is not inserted for the first time, it must be found firstEnd nodeBecause createdThe new nodeNext points to the first node, and next points to the new node.

Second, the insert

Status ListInsert(LinkList *L, int place, int num){ LinkList temp ,target; int i; If (place == 1) {// If (place == 1) {// If (place == 1) { Create a new temp node and check whether it is created successfully. If it is created successfully, the value is assigned; otherwise, ERROR is returned. //3. Make the next of the new node point to the first element node. The next of the tail node points to the new head node; // Create a new Node temp = (LinkList)malloc(**sizeof**(Node)); if (temp == NULL) { return ERROR; } temp->data = num; For (target = *L; target->next ! = *L; target = target->next); Temp ->next = *L; temp->next = *L; Target ->next = temp; // The new node becomes the first node *L = temp; }else {//1. Create a new node temp and check whether it is created successfully. If it is created successfully, the value is assigned. If the list length is longer, the queue will be automatically inserted into the end of the queue. //3. Set target->next = temp; //4. Insert the node precursor to the new node, the new node next points to the original target next position; // Create a new Node temp = (LinkList)malloc(sizeof(Node)); if (temp == NULL) { return ERROR; } temp->data = num; For (I = 1,target = *L; target->next ! = *L && i ! = place - 1; target = target->next,i++) ; Temp ->next = target->next; Target ->next = temp; } return OK; }Copy the code

Case 1: The insertion position is on the primary node:

When the insertion position is the first position, that is, the position of the head node, it will affect the pointing of L, the pointing of next of the tail node, and the change of the head node. The original head node becomes the second node, and the newly inserted node becomes the new head node.

Case 2: The insertion position is in another position:

Other non-primary nodes, including the tail node, have precursors and followings. Therefore, it is only necessary to find the previous node to be inserted, point next of the new node to the original node to be inserted, and the next of the previous node to be pointed to the new node to complete the insertion of the new node.

Three, delete,

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) {// place = 1; if((*L)->next == (*L)){ (*L) = NULL; return OK; } //② there is still a lot of data in the list, but the primary node is deleted; Target ->next = (*L)->next; For (target = *L; for (target = *L; target->next ! = *L; target = target->next); temp = *L; *L = (*L)->next; Target ->next = *L; // Next points to the new primary node free(temp); }else {// If delete other nodes -- other nodes //1. 2. Make target->next point to the next node //3. For (I =1,target = *L; target->next ! = *L && i ! = place -1; target = target->next,i++) ; temp = target->next; Target ->next = temp->next; // Next points to next Free (temp); } return OK; }Copy the code

Deletion, as well as insertion, distinguishes whether it is a primal node. When deleting to the last node, point L to null.

Fourth, traverse

Void show(LinkList p) {// If the list is empty if(p == NULL){printf(" Print the list is empty! \n"); return; }else{ LinkList temp; temp = p; do{ printf("%5d",temp->data); temp = temp->next; }while (temp ! = p); printf("\n"); }}Copy the code

The most important thing for the traversal of a one-way circular linked list is to know how to end the traversal. The condition for ending the traversal is the first node of the node next ==, then the node is the last node and the traversal is finished.

Five, the query

int findValue(LinkList L,int value){ int i = 1; LinkList p; p = L; Data == value while (p->data! = value && p->next ! = L) { i++; p = p->next; } // If the end points to the head, it will jump out of the loop. if (p->next == L && p->data ! = value) { return -1; } return i; }Copy the code

Query and traversal should pay attention to the end of the query, that is, the next node points to the first node end query, to prevent circular search.

Six, summarized

The property of a unidirectional cyclic linked list is that all nodes have precursors and successors. The precursors of the head node are tail nodes, and the tail node is followed by the head node. Without the use of a head node, additional judgments need to be made about the insertion and removal of the position of the head node, making the code more complex. The design of a one-way circular linked list with a head node can be realized by the reader, to experience the benefits of the head section.