1, Basic concept of linked list

According to the introduction of data structure, a linear table is a finite sequence of n data elements, its length can be increased or shortened as required, and there are a series of operations on the linear table.

Linear table can be divided into two types: sequential storage structure and chain storage structure.

The characteristic of sequential storage structure is that two adjacent elements in logical relation are also adjacent in physical position.

The characteristic of chain storage structure is that there is no need for logically adjacent elements to be physically adjacent.

The following focuses on the linear linked list of chain storage structure, which can be divided into single linked list, circular linked list and double linked list.

Linear table is characterized by using a set of arbitrary storage units to store the data elements of linear table, and at the same time, it also stores the information pointing to the subsequent information. These two parts of information are composed of nodes. The node consists of two parts: data field and pointer field. The pointer domain stores information as a pointer or chain. A linked list contains only one pointer field, so it is called a single linked list.

The basic operation of single chain table is realized by c language as follows:

#define MAXSIZE 20
#define OK 1
#define ERROR 0
typedef int ElemType;
typedef int Status;
//Here are some renames and macro definitions
//Storage structure of single chain table
typedef struct LNode{
    ElemType data;  //Data domain
    struct Node *next; //Pointer domain
}LNode，*LinkList;

Read the data of the ith element of the linked list:

Status GetElem(LinkList L, int i, ElemType *e){
    LinkList p;
    int j;
    p = L->next;
    j=1;
    while(p && j<i){
        p = p->next;
        ++j;
    }
    if(!p || j>i){
        return ERROR;
    }
    *e = p->data;
    return OK;
}

Insert the element e before the ith position of the linked list L of the leading node

Status ListInsert(LinkList &L, int i, ElemType e){
    LNode p;
    int j;
    p = L;
    j=0;
    while(p && j<i-1){
        p = p->next;
        ++j;
    }
    if(!p || j>i-1){
        return ERROR;
    }
    LinkList s;
    s = (LinkList)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next =s;
    return OK;
}

In the link list L of the leading node, delete the element at the ith position and return its value by e

Status ListDelete(LinkList &L, int i, ElemType &e){
    LNode p;
    int j;
    p = L;
    j=0;
    while(p && j<i-1){
        p = p->next;
        ++j;
    }
    if(!(p->next) || j>i-1){
        return ERROR;
    }
    LinkList q;
    q = p->next;
    p = q->next;
    e = q->data;
    free(q);
    return OK;
}

Circular linked list is another kind of storage structure, which is characterized by the pointer domain of the last node in the list pointing to the head node.

Bidirectional linked list: refers to the pointer field pointing to the predecessor node and the successor node.

The storage structure is:

typedef struct DuLNode{
    ElemType data;
    struct DuLNode *prior;
    struct DuLNode *next;
}DuLNode, *DuLinkList;