# Data structure -- chain storage of linear table

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.

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.

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
int n;
scanf("%d", &n);
while (n != -1) {        //Input as-1 When, the input is terminated
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 *end = L;        //Tail pointer
scanf("%d", &n);

while (n != -1) {        //input-1 Exit on
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;
}```

```#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

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

```#include<stdio.h>

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

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

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;

}

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

int i = 0;

p = p->next;

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

int LocateElemLink(LinkList L, ElemType e) {        //Find elements e Position in table
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
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

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;
}

if (L->next == NULL)
return 1;
else
return 0;

}

L->next = NULL;
free(L);
return 1;
}```

Main C main function file

```#include<stdio.h>

int main() {
int i;
int array[] = { 0,1,2,3,4,5 };
ElemType e;

for (i = 1; i < 6; i++) {
}

printf("\n");
printf("The element at the fifth position is%d\n",GetElemLink(L, 5));
printf("Delete the second element. The deleted element is%d,Print deleted tables\n",e);
printf("\n");
printf("This table is empty\n");
else
printf("This table is not empty\n");
printf("Destroy linear table");