1, What is a linked list

The linked storage of linear lists is also called single linked lists. It stores data elements through any area in the memory. In order to establish a logical relationship between the elements of each block, we divide the data storage unit of each block into two parts. The first part is the data part, and the second part is the pointer to the next node. Therefore, the linked list does not need to move a large number of elements during insertion and deletion, Just modify the pointer.

2, Characteristics of linked list

1 It solves the problem that the sequential table needs a large amount of continuous space when storing data, which belongs to non random storage.

2 Due to the existence of pointer fields, the space consumed by the linked list will be relatively large.

3 The time complexity of deleting and inserting a linked list is O(1), because you only need to modify the pointer.

4 The cost of searching is relatively large, and it needs to traverse from the beginning. The time complexity is O(n).

In my opinion, the sequential list and the linked list are complementary. In some cases, they need to be combined to complete.

3, Head interpolation and tail interpolation of single linked list

In the header insertion method, the element is always inserted behind the header node. For example, the inserted element is 1, 2, 3, 4, 5, so it is 5, 4, 3, 2, 1 in the output

The header insertion code is as follows

LinkList InsertHead(LinkList L) {        //Head insertion
    LinkNode *s;
    int n;
    scanf("%d", &n);
    while (n != -1) {        //Input as-1 When, the input is terminated
        s = (LinkNode*)malloc(sizeof(LinkNode));
        s->data = n;
        s->next = L->next;
        L->next = s;
        scanf("%d", &n);
    }
    return L;
}

The tail interpolation method inserts elements at the end of the node every time, so the order of elements will not change.

The tail interpolation code is as follows

LinkList InsertTail(LinkList L) {        //Tail interpolation
    int n;
    LinkNode *s;
    LinkNode *end = L;        //Tail pointer
    scanf("%d", &n);

    while (n != -1) {        //input-1 Exit on
        s = (LinkNode*)malloc(sizeof(LinkNode));
        s->data = n;
        end->next = s;
        end = s;        //end Point to new tail node
        scanf("%d", &n);
    }
    end->next = NULL;        //Tail node pointer is set to null
    return L;
}

IV. adding, deleting, modifying, and querying single linked lists

Linklist H header file

#include<stdio.h>

typedef int Status; /* Status Is the type of function, and its value is the result of the function. If -1 is an error and 1 is a normal code, such as OK, etc */
typedef int Boolean; /* Boolean Is a boolean type whose value is TRUE or FALSE where 1 is TRUE and 0 is FALSE */

typedef int ElemType; /*ElemType Is the type of data. We use int type here*/

typedef struct {  //Defines the node type of a single linked list
    ElemType data;    //data
    struct LinkNode *next;  //Pointer field
}LinkNode, *LinkList;

LinkList InitLinkList(LinkList L); //Initialize single linked list
int LengthLink(LinkList L);//Returns the length of a single linked list
int LocateElemLink(LinkList L, ElemType e);//Find elements e Position in table
ElemType GetElemLink(LinkList L, int i);//Get the number of i Elements in positions and returns
Status InsertLinkList(LinkList L, int i, ElemType e);//In table L pass the civil examinations i Insert element at e
Status DeleteElemLink(LinkList L, int i, ElemType *e);//Delete No. in the table i Elements with e Return its value
void PrintLinkList(LinkList L);//Output all elements of the single linked list
Boolean IsEmptyLink(LinkList L);//Judge whether the single linked list is empty
Status DestroyLinkList(LinkList L);//Destroy the single linked list and free up the occupied space

Linklist C function file

#include<stdio.h>
#include"linkList.h"

LinkList InitLinkList(LinkList L) {  //Initialize single linked list
    LinkNode *s;
    s = (LinkList)malloc(sizeof(LinkNode));
    s->next = NULL;
    L = s;
    return L;
}

Status InsertLinkList(LinkList L, int i, ElemType e) { //In table L pass the civil examinations i Insert element at e，Head insertion
    
    LinkList p = L;

    int j = 0;
    while (j < i-1) {
        p = p->next;
        j++;
    }

    LinkNode *newNode = (LinkNode*)malloc(sizeof(LinkNode));
    newNode->data = e;
    newNode->next = p->next;        //The new node points to the next node of the original location node
    p->next = newNode;        //The original location node points to the new node
    return 1;

}


void PrintLinkList(LinkList L) {  //Output all elements of the single linked list
    LinkList p = L;

    p = p->next;
    if (p == NULL)
        printf("The linked list is empty");
    else {
        while (p != NULL) {
            printf(" %d ", p->data);
            p = p->next;
        }
    }
}

int LengthLink(LinkList L) {  //Returns the length of a single linked list
    int i = 0;
    LinkList p = L;

    p = p->next;

    while (p != NULL) {
        i++;
        p = p->next;
    }
    return i;
}

int LocateElemLink(LinkList L, ElemType e) {        //Find elements e Position in table
    LinkList p = L;
    int i = 0;

    while (p->next != NULL) {
        p = p->next;
        if (p->data == e)
            return i + 1;
        i++;
    }

    return -1;
    
}

ElemType GetElemLink(LinkList L, int i) {        //Get the number of i Elements in positions and returns
    LinkList p = L;
    int j = 0;
    
    if (i <= 0 || i > LengthLink(L))
        return NULL;
    
        while (p != NULL) {
        p = p->next;
        j++;
        if (j == i)
            return p->data;
    }
}

Status DeleteElemLink(LinkList L, int i, ElemType *e) {  //Delete No. in the table i Elements with e Return its value

    LinkList p = L;
    LinkNode *n;
    ElemType *temp;
    int j = 0;
    if (i <= 0 || i > LengthLink(L))
        return -1;

    while (p != NULL) {
        if (j == i-1) {
            n = p->next;
            p->next = n->next;
            *e = n->data;
            free(n);
            return 1;
        }
        p = p->next;
        j++;
    }
    return 1;
}

Boolean IsEmptyLink(LinkList L) {  //Judge whether the single linked list is empty
    if (L->next == NULL)
        return 1;
    else
        return 0;

}

Status DestroyLinkList(LinkList L) {  //Destroy the single linked list and free up the occupied space
    L->next = NULL;
    free(L);
    return 1;
}

Main C main function file

#include<stdio.h>
#include"linkList.h"

int main() {
    int i;
    int array[] = { 0,1,2,3,4,5 };
    ElemType e;
    LinkList L = InitLinkList(&L);
    
    for (i = 1; i < 6; i++) {
        InsertLinkList(L, i, array[i]);
    }

    PrintLinkList(L);
    printf("\n");
    printf("The length of the linked list is%d\n",LengthLink(L));
    printf("5 In the linked list%d Locations\n", LocateElemLink(L, 5));
    printf("The element at the fifth position is%d\n",GetElemLink(L, 5));
    DeleteElemLink(L, 5, &e);
    printf("Delete the second element. The deleted element is%d,Print deleted tables\n",e);
    PrintLinkList(L);
    printf("\n");
    if (IsEmptyLink(L) == 1)
        printf("This table is empty\n");
    else
        printf("This table is not empty\n");
    printf("Destroy linear table");
    if (DestroyLinkList(L) == 1)
        printf("Destroyed successfully!\n");
    else
        printf("Destroy failed");
}