Data structure and algorithm (1) linear table implementation

Data structure and algorithm (2) unidirectional circular linked list creation insert delete implementation

Data structure and algorithm (3) Implementation of bidirectional linked list and bidirectional cyclic linked list

Data structures and algorithms (4) Linked list related interview questions

Data structures and algorithms (5) Stack and queue operation and implementation

Data structures and algorithms (6) The operation and implementation of queues

@TOC

The previous blog, linear Tables, covered the basic operations of sequential and singly linked lists in detail. This blog post focuses on the basic operation of circular linked lists.

1. Linear table outline

Let’s take a general look at the main operations of a linear table, as shown below:

The content in the red box is the main content of this blog, and the following blog will continue to cover bidirectional lists, circular bidirectional lists, etc.

Let’s review the singly linked list

A linked list is a linear list and a data structure that stores data. As shown in the figure below: a node of this kind contains its own data and the location pointing to the next node, one nested with the next node. This structure is called a linked list.

2. One-way circular linked lists

Click here to download this blog demo: one-way loop linked list demo

A one-way circular linked list node is defined in the same way as a single linked list, except that the tail node executes the head node to form a loop. Figure (1) below represents a one-way cyclic linked list, from tail node to head node:

Let’s review the structure diagram of one-way linked list again: figure 2

By comparison, it can be seen that the only difference between a one-way circular linked list and a one-way linked list is that there is an additional tail pointer to the process of the head node, and their node definitions are the same.

• Unidirectional circular linked list nodes are defined as follows:

typedef int KStatus;
typedef int KElementType;
typedef struct KNode {
    KElementType data;// Store an int (the data type depends on the development situation, int is used here)
    struct KNode *next; // pointer to next node}Node;
typedef struct KNode * LinkList;

Copy the code

Table 2.1 built

The process of creating a one-way circular list is very similar to that of a single list. We generally use the tail insertion method, which is more consistent with our business logic. The data obtained by the tail insertion method is the same as the order defined by us. If the head insertion method is adopted, the table obtained is in reverse order.

If we initialize a linked list with only one header and its next pointer pointing to itself, figure 3 shows an empty list:

We use the tail insertion method to insert data 9, 16, 18, and 20 respectively to obtain the following linked list, as shown in Figure 4:

We insert the table as follows:

There are two cases: (1) the first time to create; (2) If it has been created, add data to it

Create a list for the first time

YES-> Create a new node and make the next point to itself; (*L)->next = (*L); NO-> find the end of the list and place next = new. Next = (*L);

Let’s break down the process as follows:

1. We initialize an empty linked list as follows:
   

   

2. Insert 1 node as follows:

The code implementation is as follows:

• Method 1:

//1. Create a circular list
//2 cases :① The first time to create; (2) If it has been created, add data to it
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); * /
KStatus createCircleList(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, create a new node and make its next pointer to itself (*head)->next=*head;
        if(NULL= = *L) {*L = (LinkList)malloc(sizeof(Node));
            if(!L) return ERROR;
            (*L)->data = item;
            (*L)->next = *L;
        } else {
            // If the input list is not empty, find the tail of the list, which is next= new node. The next of the new node points to the head node
            for (target = *L; target->next ! = *L; target = target->next);

            temp = (LinkList)malloc(sizeof(Node));
            if(! temp)return ERROR;

            // the node is assigned and inserted into the tail
            temp->data = item;
            //1. The new node points to the head node
            temp->next = *L;
            //2. The tail node points to the new nodetarget->next = temp; }}return OK;
}
Copy the code

In this example, we use a for loop to find the end of the list. In fact, when we initialize the list, we can use a pointer r to find the end of the list, so that we do not need to loop to find the end of the list.

• Method 2:

KStatus createCircleList2(LinkList *L) {

    int item;
    LinkList temp = NULL;
    //LinkList target = NULL;
    // Add an assignment pointer to the end
    LinkList r = *L;

    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, create a new node and make its next pointer to itself (*head)->next=*head;
        if(NULL= = *L) {*L = (LinkList)malloc(sizeof(Node));
            if(!L) return ERROR;
            (*L)->data = item;
            (*L)->next = *L;
            // Record the endpoints
            r = *L;
        } else {
            // If the input list is not empty, find the tail of the list, which is next= new node. The next of the new node points to the head node
            //for (target = *L; target->next ! = *L; target = target->next);
            // there is no need to find the end node.

            temp = (LinkList)malloc(sizeof(Node));
            if(! temp)return ERROR;

            // the node is assigned and inserted into the tail
            temp->data = item;
            //1. The new node points to the head node
            temp->next = *L;
            //2. The tail node points to the new node
            r->next = temp;

            // Move the r pointer to keep it pointing to the endr = temp; }}return OK;
}

Copy the code

2.2 traversal

A do while statement is used to iterate over the list as follows:

// 2. Loop through the list
void traverseCircleList(LinkList L) {
    // Check whether the list is empty
    if(!L) {
        printf("The linked list is empty! \n");
        return;
    }

    LinkList temp;
    temp = L;
    do {
        printf("%6d", temp->data);
        temp = temp->next;
    }while(temp ! =L); printf("\n");
}
Copy the code

2.3 insert

The insertion of a one-way circular list is similar to the insertion of a one-way list, except for the special handling of the tail pointer.

The insertion of a one-way circular list can be divided into two cases:

• The first case: the insertion position is at the head node and requires a separate special treatment
• The second case: the other positions (not the first node) can be handled uniformly

For a better understanding, let’s use a diagram to distinguish between the two cases of insertion.

In the first case, the insertion position is at the beginning node, as shown in the following figure (Figure 2.3.1) :

First, we create a new node and assign it a value of 2. Then, we insert node 2 in the following three steps: 1. We point the newly created node next to the original initial node. (the figure above corresponds to node 2. We use the next pointer of node X to point to node A.) (The figure above corresponds to label 3, and next pointer of tail node C points to new head node X) (The figure above corresponds to label 4, and L points to the new first node X)

After completing the insert, we get:

Note: the order of step 1 and step 2 cannot be changed. If we point to step 2 first and then execute Step 1, our original first node 1 will be lost and cannot be found. The most important rule for list insertion is to ensure that the list does not lose nodes. Before disconnecting a node, there must be a pointer to the node to be disconnecting, so as not to lose the node.

The second case: other positions (not the first node), as shown below:

In the second case, insert the newly created node X at the non-first node as shown in the figure above, we also create a new node X. Suppose we want to insert between B and C, we first need to find the previous node B of C, and then do the same 3 steps. Insertion process: Next = next (X->next = C); next= next (X->next = X);

After insertion we have the following:

The implementation code of insert node is as follows:

// 3. Insert elements into the loop list
// L: list pointer
// place: the position to insert
// data: data to be inserted
KStatus insertElement(LinkList *L, int place, int data) {

    LinkList temp, target;
    int I;

    // Check whether the position is the first node, the first node needs to be handled separately
    if (place == 1) {
        // create a new node
        temp = (LinkList)malloc(sizeof(Node));
        // Check whether the memory is allocated successfully
        if (! temp) return ERROR;
        / / assignment
        temp->data = data;

        //2. Find the last node in the list, the last node
        for(target = *L; target->next ! = *L ; target = target->next);

        //3. Find the end node and insert it after the end node
        // make next of the new node point to the new header
        temp->next = *L;
        // next points to the new node, so that the new node becomes the new node.
        target->next = temp;
        //3.3 Let the header pointer point to the new endpoint
        *L = temp;

    } else { // Other locations
        // create a new node
        temp = (LinkList)malloc(sizeof(Node));
        // Check whether the memory is allocated successfully
        if (! temp) return ERROR;
        / / assignment
        temp->data = data;

        //2. Find the place-1 position in the list
        for(i = 1, target = *L; target->next ! = *L&& i ! = place -1 ; target = target->next, i++);

        //3. Insert the new node into place
        // next points to target's original next position;
        temp->next = target->next;
        // the precursors of inserted nodes point to new nodes
        target->next = temp;
    }
    return OK;
}
Copy the code

2.4 delete

Deletion, like insertion, falls into two categories:

• The first case: deleting the first node requires special treatment.
• The second case: delete other nodes, not the first node, can be handled uniformly.

For the first case (delete the header) :

Let’s analyze the process: in the figure above, we want to delete the first node, A, and we want to find the last node, C. Then, next, which ends at C, points to the new start at B. (C->next = B) Then, point L to the new start node B. (*L = B) Finally free the memory of node A.

The second case is to delete a non-first node:

If we delete a node that is not the first node, as shown in the figure above, if we delete node X, we first need to find the last node of X, B. And then I’m going to execute the next node of X, which is NEXT of B, which is C. (B->next = C or B->next = B->next->next) Finally we free the memory of node X.

The implementation code is as follows:

// 4. Loop the list to delete elements
// Remove the element in place
// L: list pointer
// place: the position to delete
KStatus deleteElement(LinkList *L, int place) {

    LinkList temp, target;
    int I;
    //temp points to the first node of the list
    temp = *L;
    // If it is an empty list, end
    if(! temp)return ERROR;

    // Check whether it is the first node. If it is the first node, separate special treatment is required
    if (place == 1) {
         // select *L from *L;
        if((*L)->next == (*L)) {*L = NULL;
            return OK;
        }

        // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
        // find the end node.
        for (target = *L; target->next ! = *L; target = target->next) ;
        Target ->next = (*L)->next;
        temp = *L;
        *L = (*L)->next;
        // 2.3 If the new node is used as a header, the original header is released
        target->next = *L;
        // Release resources
        free(temp);
    } else { // Other positions, unified processing
        // find the place-1 position
        for (i = 1, target = *L; target->next ! = *L&& i ! = place -1; target = target->next, i++) {
            // Find the target before deleting the target
            // Use temp to point to the element to be deleted at place
            temp = target->next;
            // make target->next point to the next node
            target->next = temp->next;

            // Free memoryfree(temp); }}return OK;
}
Copy the code

2.5 the query

Query very node, a while loop to complete, implementation code is as follows:

//5
// Returns the index value of the location
int queryValue(LinkList L , int value) {
    int i = 1;
    LinkList p = L;

    // Find the node in the list data == value
    while(p->data ! = value) {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; // Not found
    // Find the element, return the subscript
    return I;
}
Copy the code

2.6 Unit Tests

// unit test
void test() {
       LinkList head;
        int place,num;
        int iStatus;

        iStatus = createCircleList(&head);
        //iStatus = createCircleList2(&head);
        printf("Original linked list: \n");
        traverseCircleList(head);

    // printf(" Enter the position and data to insert separated by Spaces: ");
    // scanf("%d %d",&place,&num);
    // iStatus = insertElement(&head,place,num);
    // traverseCircleList(head);

        printf("Enter the location to delete:");
        scanf("%d",&place);
        deleteElement(&head,place);
        traverseCircleList(head);


        printf("Enter the value you want to find :");
        scanf("%d",&num);
        place = queryValue(head,num);
        if(place! = -1)
            printf("Place = %d\n",place);
        else
            printf("No value \n found");
}
Copy the code

2.7 Complete code implementation

//
// main.c
// 004_CircularLinedList
//
// Created by bog on 2020/4/5
// Copyright © 2020 Apple. All rights reserved
//

#include <stdio.h>
#include "string.h"
#include "ctype.h"
#include "stdlib.h"
#include "math.h"
#include "time.h"

#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OK 1

#define MAXSIZE 20 /* Initial allocation of storage space */

typedef int Status;/* Status is the type of the function, and its value is the Status code of the function result, such as OK */
typedef int ElemType;/* ElemType specifies the value of the value. The value is assumed to be int */

// Define the node
typedef struct Node{
    ElemType data;
    struct Node *next;
}Node;

typedef struct Node * LinkList; /* 4.1 Creating a looping list! There are two scenarios: (1) The system is created for the first time. 1. Check whether the linked list is created for the first timeYES-> Create a new node and make the new nodenextTo oneself; (*L) - >next = (*L);
    NO-> Find the end of the list, add the end of the listnext= new node. New nodenext = (*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)
    {
        scanf("%d",&item);
        if(item==0) break;
        
          // If the input list is empty. (*head)->next=*head;
        if(*L= =NULL) {*L = (LinkList)malloc(sizeof(Node));
            if(!L)exit(0);
            (*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. The next of the new node points to the head 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 head node
            target->next=temp;// The tail node points to the new node}}return OK;
}

Status CreateList2(LinkList *L){
    
    int item;
    LinkList temp = NULL;
    LinkList target = NULL;
    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;
            r = *L;
        }else{
            
            temp = (LinkList)malloc(sizeof(Node));
            if(! temp)return  ERROR;
            temp->data = item;
            temp->next = *L; r->next = temp; r = temp; }}return OK;
}



A do while statement is best used to iterate over a list, since the head node has a value
void show(LinkList p)
{
    // If the list is empty
    if(p == NULL){
        printf("The printed list is empty! \n");
        return;
        
    }else{
        LinkList temp;
        temp = p;
        do{
            printf("%5d",temp->data);
            temp = temp->next;
        }while(temp ! = p); printf("\n"); }}//4.3 Circular list insert data
Status ListInsert(LinkList *L, int place, int num){
    
    LinkList temp ,target;
    int I;
    if (place == 1) {
        
        // If the insertion position is 1, it belongs to the initial node insertion point, so special processing is required
        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.
        //2. Find the last node of the list.
        //3. Let the next of the new node execute the header.
        //4. Next points to the new header;
        //5. Let the header pointer point to temp(temporary 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;
        target->next = temp;
        *L = temp;
        
    }else
    {
        
        // 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.
        If the list length is longer, the queue will be automatically inserted into the end of the queue.
        // set target->next = temp;
        //4. Insert node precursor to new node, new node next to target next;
        
        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;
}

//4.4 Loop the list to delete elements
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;
        }
        
        
        // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
        Target ->next = (*L)->next;
        //2. If the new node is used as a header, the old header is released
        
        for (target = *L; target->next ! = *L; target = target->next);
        temp = *L;
        
        *L = (*L)->next;
        target->next = *L;
        free(temp);
    }else
    {

        // If you delete other nodes -- other nodes
        //1. Locate the target before deleting the target
        //2. Make target->next point to the next node
        //3. Release the temp node to be deleted
        for(i=1,target = *L; target->next ! = *L&& i ! = place -1; target = target->next,i++) ; temp = target->next; target->next = temp->next; free(temp); }return OK;
    
}


//4.5 Loop linked list query value
int findValue(LinkList L,int value){
    
    int i = 1;
    LinkList p;
    p = L;
    
    // Find the node in the list 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;
    
}

int main(int argc, const char * argv[]) {
    // insert code here...
    printf("Hello, World! \n");
    
    LinkList head;
    int place,num;
    int iStatus;
    
    //iStatus = CreateList(&head);
    iStatus = CreateList2(&head);
    printf("Original linked list: \n");
    show(head);
    
// printf(" Enter the position and data to insert separated by Spaces: ");
// scanf("%d %d",&place,&num);
// iStatus = ListInsert(&head,place,num);
// show(head);

    printf("Enter the location to delete:");
    scanf("%d",&place);
    LinkListDelete(&head,place);
    show(head);
    
    
    printf("Enter the value you want to find :");
    scanf("%d",&num);
    place=findValue(head,num);
    if(place! = -1)
        printf("Place = %d\n",place);
    else
        printf("No value \n found");
    
    return 0;
}
Copy the code

Output result:

Hello, kongyulu! Please enter a new node, end when 0 is entered! 1 2 3 4 5 6 0 The original list: 1 2 3 4 5 6 Enter the location to delete: 1 2 3 4 5 6 Enter the value you want to find :4 The location to find the value is place = 3 Program ended with exit code: 0Copy the code