• Unidirectional cyclic linked list foundation

    • concept

    A circular list is another form of chained storage. Its characteristic is that the pointer field of the last node in the table points to the head node, and the whole linked list forms a ring.

    The difference from a singly linked list is that a pointer to a tail node does not point to NULL, but to a head node or primary node

    • The illustration

  • Initialization and assignment of a one-way circular list

#define OK 1
#define ERROR 0typedef int Status; typedef int ElemType; typedef struct Node { ElemType data; struct Node * next; } Node; typedef struct Node *LinkList; Status createLinkList(LinkList *L){int number; LinkList temp = NULL; LinkList target = NULL;printf("You can enter a value to insert a linked list. Type 0 to break out of the loop \n"); // Insert data into the listwhile(1){
        scanf("%d",&number);
        if(number == 0) break;
        if(*L == NULL){// List is NULL //1. create a new node //2. Next points to *L *L = (LinkList)malloc(sizeof(Node));if(L == NULL) exit(0); (*L)->data = number; (*L)->next = *L; // The pointer to the primary node needs to point to itself}else{// List is not NULL //1. Create a new node //2. Temp = (LinkList)malloc(sizeof(Node));if(temp == NULL) exit(0);
            for(target = *L; target->next != *L; target = target->next);
            temp->data = number;
            temp->next = *L;
            target->next = temp;
        }
    }
    
    return OK;
}

Status createLinkList2(LinkList *L){
    int number;
    LinkList temp = NULL;
    LinkList lastNode = NULL;
    printf("You can enter a value to insert a linked list. Type 0 to break out of the loop \n");
    while (1) {
        scanf("%d",&number);
        if(number == 0) break;
        if(*L == NULL){
            //列表是NULL
            //1.创建一个新的节点
            //2.节点的next指向*L
            //3.lastNode = *L
            *L = (LinkList)malloc(sizeof(Node));
            if(*L == NULL) exit(0);
            (*L)->data = number;
            (*L)->next = *L;
            lastNode = *L;
        }else{// List is not NULL //1. Create a new node //2. Temp = (LinkList)malloc(sizeof(Node)); temp = (LinkList)malloc(sizeof(Node))if(temp == NULL) exit(0); temp->data = number; temp->next = *L; lastNode->next = temp; lastNode = temp; }}return OK;
}
Copy the code

  • Unidirectional circular linked list insertion

    • List inserts without headers

      • The insertion position is at the head node
        1. Create a new node target and assign it to it
        2. Find the tail
        3. Target points to the prime node
        4. The endpoint next pointer points to target
        5. L to target

      The difference is that insertion at the initial node requires additional modification of the orientation of L

      • Insert position in other position
        1. Create a new node target and assign it to it
        2. Find temp, the node above the insertion position
        3. Target – > next to temp – > next
        4. Temp – > next point to the target

      Note: reverse the order of 3 and 4; otherwise, the node after temp will be lost

    • Insert a linked list with a header

Insert (LinkList *L,int item, int place){if(*L == NULL) return ERROR;
    LinkList temp = NULL;
    LinkList target = NULL;
    if(place == 1){// When the place is 1 //1. Create a new node temp and copy data //3. Point next to *L //4. 5. *L to temp // Find the last nodefor(target = *L; target->next ! = *L; target = target->next); temp = (LinkList)malloc(sizeof(Node)); temp->next = (*L)->next; target->next = temp; *L = temp; }else{// If the position of the insert is not 1 //1. Create a new node, temp, and assign data //3. // Set target->next to temp;for(target = *L,i = 1; target->next ! = *L && i ! = place - 1; i ++,target = target->next);if(i ! = place - 1){printf("Insert position out of list length");
            return ERROR;
        }
        temp = (LinkList)malloc(sizeof(Node));
        if(temp == NULL) return ERROR;
        temp->data = item;
        temp->next = target->next;
        target->next = temp;
    }
    return OK;
}
Copy the code

  • Unidirectional circular linked list deleted

    • Delete linked list without header

      • Delete the header node
        1. Create a pointer target to the initial node
        2. Find the temp tail
        3. The temp->next pointer points to target-> Next
        4. L to target – > next
        5. The release of the target
      • Delete other location nodes
        1. Find temp, the previous pointer to the pointer to be deleted
        2. Create a pointer target to temp->next
        3. Temp – > next point to the target – > next
        4. The release of the target

      Also pay attention to the order otherwise you might lose nodes

    • Delete a linked list containing a header

Status delete(LinkList *L,int place){if(*L == NULL) return ERROR;
    LinkList target = NULL;
    LinkList temp = NULL;
    if(place = = 1) {/ / remove the first finally point / / 1. Find the end node / / 2. The temp at first finally point / / 3. Point to * * L L - > next / / 4. The end point is *L //5for(target = *L; target->next ! = *L; target = target->next); temp = *L; target->next = (*L)->next; *L = (*L)->next; free(temp); }else{// Delete not the initial node //1. Find the previous contact target //2. Target ->next refers to temp->next //4. Temp int I;for(i = 1,target = *L; target->next ! = *L && i < place-1; target = target->next,i++);if(i < place) return ERROR;
        temp = target->next;
        target->next = temp->next;
        free(temp);
    }
    return OK;
}
Copy the code

Note: this code shows the operation with a header list. Interested friends can try the implementation without a header list