0   order

All the books on the Internet I saw before were Struct directly creating nodes.

I remember typedef struct is a method used to declare linked list nodes in the data structure textbook in college. This method makes it easy for people to operate the linked list. Later, I threw away the books and bought pirated books. I don't know whether it was a version problem or something. Most blogs on the Internet are directly declared by struct. Struct directly declares that the addition, deletion, modification and query of the following linked list have slightly increased the difficulty.

Today, I suddenly saw this writing method when checking the data. After operating it again, I found that it is easy to realize some basic operations of the linked list, so I improved it and posted it

one   code

The code is relatively simple, and the important parts are annotated

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>

typedef struct List
{
    int val;
    struct List *next;
} link;

/*------------------------------Initialize node--------------------------------*/
link *InitNode()
{
    printf("Start initializing node\n");
    link *head = (link *)malloc(sizeof(link)); //Initialize header node
    head->next = NULL;                         //During initialization, the next node of the header node must point to null, otherwise it will point to a random address
    printf("Initialization node completed\n");
    return head;
}

/*------------------------------Traversal node--------------------------------*/
void PrintNode(link *head)
{
    while (head->next != NULL)
    {
        head = head->next; //Because there is a head node, but the head node does not store data, it starts traversal from the next node of the head node
        printf("%d\n", head->val);
    }
}

/*------------------------------Adding nodes by tail interpolation--------------------------------*/
void AppendNodeR(link *head, int t)
{
    link *a = (link *)malloc(sizeof(link));
    a->val = t;
    a->next = NULL;
    printf("Start tailing to add nodes %d\n", t);
    while (head->next != NULL)
    {
        head = head->next;
    }
    head->next = a;
    printf("Adding nodes by tail interpolation has been completed\n");
}

/*------------------------------Add node by head interpolation--------------------------------*/
void AppendNodeL(link *head, int t)
{
    link *a = (link *)malloc(sizeof(link));
    a->val = t;
    a->next = NULL;
    printf("Start adding nodes by header interpolation %d\n", t);
    a->next = head->next;
    head->next = a;
    printf("Header interpolation node addition completed\n");
}

/*------------------------------Delete node--------------------------------*/
void DeleteNode(link *head, int t)
{
    link *temp = (link *)malloc(sizeof(link)); //Initialize header node
    link *d = head;
    printf("Start deleting target node: %d\n", t);
    while (d->next != NULL)
    {
        temp = d;
        d = d->next; //Because there is a head node, but the head node does not store data, it starts traversal from the next node of the head node
        if (d->val == t)
        {
            temp->next = d->next; //d has moved back one bit here
            printf("Deleted node: %d\n", d->val);
        }
    }
}

int main()
{
    link *head = InitNode(); //Because this header node is used later, you need to return a header node

    AppendNodeR(head, 0); //Because we pass it by pointer, that is, address, we don't need to return the linked list again
    AppendNodeR(head, 1);
    AppendNodeR(head, 2);
    AppendNodeR(head, 3);
    AppendNodeR(head, 4);
    AppendNodeR(head, 5);
    AppendNodeR(head, 6);
    AppendNodeR(head, 7);
    AppendNodeR(head, 8);
    AppendNodeR(head, 9);
    AppendNodeR(head, 10);
    PrintNode(head);

    DeleteNode(head, 3);
    PrintNode(head);

    AppendNodeL(head, 20);
    AppendNodeL(head, 21);
    AppendNodeL(head, 22);
    PrintNode(head);

    system("pause"); //The shell pauses the function. If it is not added, the black box flashes. Calling system requires adding stdlib header file
}

  result

two   Schematic diagram of head inserting method

Because the head insertion method took a slight turn, I didn't understand it before. Just draw a picture

  The head node of the linked list points to the next node. Therefore, when inserting a new node, first point the node to be inserted to the next node of the head node, and then point the head node address to the node to be inserted.

As follows, a is the node to be inserted, and head is the next node of head.

    a->next = head->next;
    head->next = a;

  three   About many head s in my code

Maybe many of them are heads here, but this is the address of the incoming head. Therefore, although they have been redeclared many times, the same head is passed in the main function, so the head address here is actually the same.

I'll talk about traversing the head later. It may be clearer

  four   About head in traversal function

I deliberately wrote the head here. If you can understand the head, it means you really understand the linked list

Our head=head.next here is to move the pointer.

And because the head here is actually a new local address (pointer) variable, changing the value here has no effect on the head in the main function.

five   Address of linked list

  In fact, when we apply for memory with malloc, we have already opened up an address in the memory.

Whether to save in the heap or in the stack will be discussed next time.

As shown in the figure, we can see three addresses, which are the positions of head, p and t.

  When we assign next to the address of the node that points to (let next be equal to the address of the pointing node), the address becomes the address of the pointing node. Novices are often confused when pointing to the address and don't know who refers to whom.

It is clearly stated here that next = the address of the node you want to point to.

As shown in the figure below, the next node is pointed to

  The following figure shows the address values after pointing to the node

  six   About next pointing to NULL

In this figure, we can see that after we use malloc to create a structure pointer variable, its value is an explicit address. The structure pointer in our structure does not use malloc, so it points to a random value. As shown in the figure below, it is the same value before pointing to the address, and they all point to the same place.

Therefore, it is very important for the next node to point to NULL when initializing and adding nodes. If it does not point to NULL, we will not find where the tail node is when traversing. By the way, let's explain here that the way we judge the tail node is to judge whether the next of the current node points to NULL. If it points to NULL, it means that it is the tail node.

  Therefore, it must be noted that the next of the new node must point to NULL