Circular linked list

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

See my last blog post for the node definition of a circular linked list. Or you can refer to the code covered in this article, which hopefully will help you understand circular lists.

Create and initialize

Note when initializing or adding data to a circular list:

Circular linked lists are generalDon't needAdd an extra head node, that is, the head of the list.
The linked list needs to be handled when adding new nodes at the endEnd node, pointing it to the linked listFinally, some first.

The specific process is shown below:

Find the end of the list

Traversing the linked list nodes,If the next node of the current node is the head node, then the current node is the end node.
In a continuous operation, each operation isRecord tailEasy to use next operation. The code is as follows:

/* /* 4.1 Creating a circular 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 createCycleChain(List *l){
    int itemValue;
    List temp = NULL;
// find the tail
    List key = NULL;
// Each operation is used to record the tail
// List tail = NULL;
    printf("Enter the value of the node, end with 0: \n");
    while (1) {
        scanf("%d", &itemValue);
        if (itemValue == 0) break;
        

        if (*l == NULL) {
// If the list is empty, create a new node as the starting node of the new list, with next pointing to itself
            *l = (List)malloc(sizeof(Node));
            
            if(! l)exit(ERROR);
            (*l)->data = itemValue;
            (*l)->next = *l;
// tail = *l;
        }else{
// If the list is not empty, you need to find the tail of the list, insert the new data as the new tail, and make it next to the head.
// There are two ways to find the tail:
If next points to the head, it is tail 2. The tail is recorded during each operation.
            for(key = *l; key->next ! = *l; key = key->next) ;// Create new nodes
            temp = (List)malloc(sizeof(Node));
            temp->data = itemValue;
            temp->next = *l;
            key->next = temp;
            
// temp->data = itemValue;
// temp->next = *l;
// tail->next = temp;
// tail = temp;}}return SUCCESS;
}

Copy the code

The output

The printing output of the circular linked list is very simple and mainly involves the judgment of the end of the list.


A do while statement is best used to iterate over a list, since the head node has a value

/// iterate over the looping list
/// @param l linked list
Status printCycleChain(List l){
    
    if(! l) {return ERROR;
    }else{
        List t;
        t = l;
        printf("Linked list information \n");
        do {
            printf("%d, ", t->data);
            t = t->next;
        } while(t ! = l);// If the current node is a header, the printing is complete
        printf("\n");
    }
    return SUCCESS;
}

Copy the code

Insert the node

As for insertion, as there is no header added to the circular linked list, it is necessary to discuss whether the insertion position is in the first element of the list.

The insertion position is in the prime position

Steps:

createThe new node;
Looking for linked listsEnd node;
The new node points toFinally, some first;
The tail points to the new node;
Make the new node becomeThe head of the list.

The overall process is shown in the figure:

The insertion position is not in the prime position

Steps:

createThe new node;
To find the insertion positionFront nodes;
The new node points toThe next node of the leading node;
The leading node points to the new node. The overall process is shown in the figure:

Combining the two cases, the code is as follows:


// insert a new node into the list at the specified location
/// @param l linked list
/// @param index position
/// @param value New value
Status chainInsert(List *l, int index, int value){
    
    List temp;
    
    temp = (List)malloc(sizeof(Node));
    if(! temp) {return ERROR;
    }
    temp->data = value;
    
    // If the insertion position is the first element node, special treatment is required:
    // 1. Create a new node, temp, that points to the original header;
    // 2. The original endpoint points to the new endpoint;
    // 3. Change the new node to a new header.
    if (index == 1) {
        List tail;
        for(tail = *l; tail->next ! = *l; tail = tail->next) ; temp->next = *l; tail->next = temp; *l = temp; }else{
    // if the insertion position is not the first element :(note that if it is beyond the position, it is placed at the last node)
    // 1. Create a new node, temp, and insert it into the previous node.
    // 2. The front node points to the new node;
        int i;
        List front; // The front node
        for(i = 1, front = *l; front->next ! = *l && i ! = index -1; front = front->next, i++) ;
        
        if(i ! = index -1) {
             printf("Not in the right place! \n");
            return ERROR;
        }
        
        temp->next = front->next;
        front->next = temp;
        
    }
    return SUCCESS;
}

Copy the code

Delete nodes

Similar to insertion node, because the circular list does not add a header node, the deletion of the circular list needs to discuss whether the deletion position is in the first element of the list.

The delete location is in the prime location

Steps:

Write down the prime node for the moment. It’s justNode to be deleted;
Looking for linked listsEnd node;
The tail points to the node to be deletedNext node;
Of the node to be deletedNext nodeAs the head of a linked list;
Brings back the value union of the node to be deletedThe release ofThe node. The overall process is shown in the figure:

In the construction of…

The delete location is not in the first location

Steps:

To find the insertion positionFront nodes;
The next node that holds the front node, which isNode to be deleted;
The leading node points to the node to be deletedNext node;
Brings back the value union of the node to be deletedThe release ofThe node. The overall process is shown in the figure:

In the construction of…

Combining the two cases, the code is as follows:


/// delete the node at a specific position in the linked list
/// @param l linked list
/// @param index delete position
/// @param value returns the value of the deleted node
Status chainDelete(List *l, int index, int *value){
    List temp;
    
    if(! l) {return ERROR;
    }
    
// If you want to delete the first element, you need to do something special:
// 1. Use the temp pointer to mark the initial node and find the end node;
// 2. The end node is the next node of temp;
// 3. Make the next node of temp the head of the linked list;
// 4. Retrieve the value of temp to release temp.
    if (index == 1) {
        temp = *l;
        
        // If the list has only one element, delete it, release the header, and empty the list.
        if (temp->next == *l) {
            *value = temp->data;
            free(temp);
            *l = NULL;
            return SUCCESS;
        }
        
        List tail;
        
        for(tail = *l; tail->next ! = *l; tail = tail->next) ; tail->next = temp->next; *l = temp->next; *value = temp->data;free(temp);
        
    }else{
// Delete the first node of the list:
Temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp
// 2. Make the front end point to the next node of temp;
// 3. Delete and release the temp node.
        List front;
        int i;
        
        for (i = 1, front = *l; front->next ! = *l && i ! = index -1; front = front->next, i++) ;
        
        if(i ! = index -1) {
            printf("Not in the right place! \n");
            return ERROR;
        }
        
        temp = front->next;
        front->next = temp->next;
        *value = temp->data;
        free(temp);
        
    }
    return SUCCESS;
}

Copy the code

The query

Walk through the list looking for a specific location, if you find a return value. Notice the judgment of the endpoints, and the judgment that the end of the loop might not be found.


// find the value of the node at a specific position in the list
/// @param l linked list
/// @param index position
/// @param value returns the found value
Status chainGet(List l, int index, int *value){
    if(! l) {return ERROR;
    }
    List temp;
    int i;
    for (temp = l,i = 1; i < index && temp->next ! = l; temp = temp->next, i++) ;if (temp == l) {
// There is no loop at all, only the initial condition is assigned to verify that it is the first element to be found
        if (index == 1) {
            *value = temp->data;
            returnSUCCESS; }}else{
        if(temp->next == l && i ! = index) {// The loop ends and the last element is found
            return ERROR;
        }else{
// End the loop in the middle, that must be found
            
// bring back the record value
           *value = temp->data;
           returnSUCCESS; }}return ERROR;
}

Copy the code

change

In the construction of… (in fact, there is no need to achieve, if you understand the above nature will ha ha, no more, delete + insert = change 😊)

In fact, I have some personal views on the special treatment of the first node of the circular linked list:

Whether delete or insert, the main action of a linked list operation is to find the leading node of the operation position, but in the case of a circular list, the leading node of the primary node is the end node. Then insert or delete; After the operation is complete, if the operation location is the primary node, you need to replace the head of the list with the new head.

It can be found that the whole idea and linear linked list is consistent, from the idea can not consider whether the circular linked list 😊

mo4tech.com (Moment For Technology) is a global community with thousands techies from across the global hang out!Passionate technologists, be it gadget freaks, tech enthusiasts, coders, technopreneurs, or CIOs, you would find them all here.

One-way circular linked list 20200402

Circular linked list

Create and initialize

The output

Insert the node

The insertion position is in the prime position

The insertion position is not in the prime position

Delete nodes

The delete location is in the prime location

The delete location is not in the first location

The query

change

One-way circular linked list 20200402

Circular linked list

Create and initialize

The output

Insert the node

The insertion position is in the prime position

The insertion position is not in the prime position

Delete nodes

The delete location is in the prime location

The delete location is not in the first location

The query

change

Related Posts

Apache Flink Advanced (12) : Explore Flink SQL in depth

Github was acquired by Microsoft. Here are 16 alternatives

Finger Offter – Prints linked lists from end to end