# 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. 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
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;
}```

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

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

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>

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

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

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

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

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));
printf("Delete the second element. The deleted element is%d,Print deleted tables\n",e);
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");
}```

Tags: data structure

Posted by vicky57t on Wed, 01 Jun 2022 00:51:13 +0530