Recently, I have been using python and so on. I haven't written C for a long time. hhh, suddenly, I have a whim. I want to consolidate the foundation and write a simple reproduction of the linked list operation. It should be regarded as a practice or review. For xdm who is not familiar with the linked list, I can roughly refer to it. If there is a problem, you are also welcome to criticize and correct it

(this article focuses on the code part, and the detailed linked list principle part can be moved to other videos / articles. The author will also consider the opportunity to explain hhh more in the future.)

Linked list structure definition

Here, the simplest structure (data + address pointer) is taken as an example to define linked list nodes.

struct node{
    int data;	// Data field
    node* next = nullptr;	// Pointer field
};

// Create node head
node* head = new node;

Find the length of the linked list

// Length of linked list
int node_length(node* head){
    node* p = head;
    int length = 0;
    while(p){
        length++;
        p = p->next;
    }
    
    return length;
}

Insert elements by tail interpolation

Here, it is directly encapsulated into a tail interpolation function. Because the single linked list needs to determine the location of the precursor node before inserting the node, here, if you want to insert a node every time, you need to traverse from the beginning of the node to the end to confirm the current precursor node. The time complexity is O ( n ) O(n) O(n).

// Insert elements by tail interpolation
void insert_at_tail(node* head, int dat){
    node* point = new node;
    point -> data = dat;
    node* p = head;
    while(p -> next != nullptr){
        p = p -> next;
    }
    
    p -> next = point;
    point -> next = nullptr;
}

Insert elements by head interpolation

Unlike the tail interpolation method, the head interpolation method only needs to know the position of the head node, and the new node can be directly inserted into the head node, and the time complexity is O ( 1 ) O(1) O(1).

// Insert elements by head interpolation
void insert_at_head(node* head, int dat){
    node* point = new node;
    point -> data = dat;
    // If there is only a header node, insert it directly
    if(head -> next == nullptr){
        head -> next = point;
        point -> next = nullptr;
        return;
    }
    
    else{
        node* p = head -> next;
        point -> next = p;
        head -> next = point;
    }
}

Insert element at specified position

Compared with the previous insertion method, you need to enter the position information of the inserted element here.

// Insert the element at the specified position, and loc is the index of the insertion position
void insert_at_loc(node* head, int loc, int dat){

	// To judge the rationality of the insertion position, the function of finding the length of the linked list is used here
    if(loc < 0 || loc >= node_length(head)) return;
    
    node* p = head;
    for(int i = 0;i < loc;i++){
        p = p -> next;
    }
    
    node* point = new node;
    point -> data = dat;
    point -> next = p -> next;
    p -> next = point;
}

Delete elements by value

If the value to be deleted is found, the corresponding node of the value will be deleted in the linked list. If it is not found, no operation will be performed.

// Delete the specified value element. If the specified value is not found, it will remain intact
void delete_node(node* head, int dat){
    node* p = head;
    node* q = head -> next;
    
    while(q){
        if(q -> data == dat){
            p -> next = q -> next;
            delete(q);
            break;
        }
        
        else{
            if(q -> next == nullptr && q -> data != dat) return;
            p = p -> next;
            q = q -> next;
        }
    }
}

Modify element

Modify the node value of the specified element to the new specified value. If the specified element is not found, it will remain unchanged.

// Modify the node value of the specified element to the new specified value. If the specified element is not found, it will remain unchanged
void revise(node* head, int src, int dst){
    node* p = head;
    while(p){
        if(p -> data == src){
            p -> data = dst;
            return;
        }
        
        else{
            if(p -> next == nullptr && p -> data != src) return;
            p = p -> next;
        }
    }
}

Find elements

Output the position of the specified element value, and return -1 if it is not found.

// Output the position of the specified element value. If it is not found, -1 is returned
int find_node(node* head, int dat){
    if(head -> next == nullptr)return -1;
    node* p = head;
    int loc = 0;
    while(p){
        if(p -> data == dat)return loc;
        else{
            if(p -> next == nullptr && p -> data != dat) return -1;
            p = p -> next;
            loc++;
        }
    }
}