# 1. Basic concepts:

Linked list: a non continuous and non sequential storage structure in the physical storage structure. The logical order of data elements is realized through the pointer link order in the linked list.

The linked list has 8 structures:

In practice, the most commonly used are:

## 2.1 preparation:

First, reference the header file and create a structure. This structure is the node of the linked list. A node contains data items and pointer items. The pointer item stores the address of the next node. (assuming the stored data is of type int)

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

typedef int DataType;
typedef struct SListNode
{
DataType data;
struct SListNode* next;
}SLNode;

```

## 2.2 basic operation of linked list

### 2.2. 1 tail interpolation function (insert data at the end of the linked list)

As long as you insert data, you have to malloc a new node. The data item is assigned the value you want, and the pointer item is assigned null. So first encapsulate a function that generates a new node.

```SLNode* BuyNewNode(DataType x)
{
SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));
if (newnode == NULL)
{
printf("malloc fail\n");
exit(-1);
}
else
{
newnode->data = x;
newnode->next = NULL;
}
return newnode;
}```

Tail interpolation function: after the new node is created. To find the tail of the linked list, insert it. There are two cases: the linked list is empty and the linked list is not empty. If it is not empty, find the tail node and then link.

```void SListPushBack(SLNode** pphead, DataType x)
{
//Tail finding
//1. When the linked list is empty
{
}
//2. The linked list is not empty
else
{
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = newnode;
}
}```

Why pass the secondary pointer (* * pphead): because phead is a pointer type, it stores the address of the first node. If the linked list is empty, the value of phead needs to be changed during tail insertion. Therefore, to pass the address of phead, the address must use the secondary pointer.

### 2.2. 2 head insertion function (insert data at the front of the linked list)

Create a new node. If the linked list is empty, insert it directly.

The linked list is not empty:

The red arrow is the link process of else.

code:

```void SListPushFront(SLNode** pphead, DataType x)
{
{
}
else
{
}
}```

### 2.2. 3 tail deletion function

There are three situations: 1. If the linked list is empty, it will be returned directly.

2. When there is only one node, free this node directly* pphead=NULL. At first I wrote tail=NULL, which is wrong. The code comments are explained.

3. There is at least one node. To find the penultimate node and the last node, you need to find the penultimate node because after free loses the last node, the penultimate node becomes the last node, and its pointer should be set to null.

```void SListPopBack(SLNode** pphead)
{
SLNode* prev = NULL;
//1. The linked list is empty
{
return;
}
//2. There is only one node
else if (tail->next== NULL)
{
free(tail);
//tail=NULL;// Both tail and * pphead point to the same block of memory. After passing the function free, this block
//The memory is returned to the operating system, tail=NULL, but * pphead still points to this memory,
//So * pphead becomes a wild pointer, so the program will report an error.
}
//3. There is at least one node
else
{

while (tail->next != NULL)
{
prev = tail;
tail = tail->next;
}
free(tail);
prev->next = NULL;
}
}```

### 2.2. 4 header deletion function

When the linked list is empty, it returns directly.

When the linked list is not empty, define a next node to save the address of the second node, then free the first node, and finally point * pphead to the next node.

```void SListPopFront(SLNode** pphead)
{
{
return;
}
else
{
}
}```

### 2.2. 5 search function (find the address of the node according to the data item and return it)

```SLNode* SListFind(SLNode** pphead, DataType x)
{
while (cur != NULL)//Cannot be cur - > next= Null. When cur==NULL, the program null - > next error occurs
{
if (cur->data == x)
{
return cur;
}
else
{
cur = cur->next;
}
}
return NULL;
}```

### 2.2. 6 pre interpolation function (insert data at pos position)

2,else. At this time, you need to find the address of the previous node in the pos location (cur here). (the red arrow in the figure shows the link process)

```void SListInsert(SLNode** pphead, SLNode* pos, DataType x)
{
{
SListPushFront(pphead,x);//When inserting at the first node, the header insertion function is called directly
}
else
{
//Find the previous node of pos
while (cur->next != pos)
{
cur = cur->next;
}
cur->next = newnode;
newnode->next = pos;
}
}```

### 2.2. 7 delete function (delete the node at pos position)

1. If pos=*pphead is to delete the first node, call the header deletion function

2.else. Find the previous node of pos (cur here), and then link.

When linking, you should pay attention to cur - > next = pos - > next, then free (POS), pos=NULL. If you first free (POS), you can't find the next node of POS.

code:

```void SListErase(SLNode** pphead, SLNode* pos)
{
{
}
else
{
while (cur->next != pos)
{
cur = cur->next;
}
cur->next = pos->next;
free(pos);
pos = NULL;
}
}```

### 2.2. 8. Modify pos position data

You can traverse it once

```void SListModify(SLNode** pphead, SLNode* pos, DataType x)
{
while (cur != pos)
{
cur = cur->next;
}
cur->data = x;
}
```

### 2.2. 9 destroy function

```void SListDestory(SLNode** pphead)
{
while (cur != NULL)
{
SLNode* next = cur->next;
free(cur);
cur = next;
}
}```

### 2.2. 10 print function

Because it is printing, there is no need to change the value of phead. So there is no need to pass the secondary pointer.

```void SListPrint(SLNode* phead)
{
while (cur != NULL)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\n");
}
```

# 3. Total code

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

typedef int DataType;
typedef struct SListNode
{
DataType data;
struct SListNode* next;
}SLNode;

{
while (cur != NULL)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\n");
}

{
SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));
if (newnode == NULL)
{
printf("malloc fail\n");
exit(-1);
}
else
{
newnode->data = x;
newnode->next = NULL;
}
return newnode;
}
{

//Tail finding
//1. When the linked list is empty
{
}
//2. The linked list is not empty
else
{
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = newnode;
}
}

{
{
}
else
{
}
}

{
SLNode* prev = NULL;
//1. The linked list is empty
{
return;
}
//2. There is only one node
else if (tail->next == NULL)
{
free(tail);
}
//3. There is at least one node
else
{

while (tail->next != NULL)
{
prev = tail;
tail = tail->next;
}
free(tail);
prev->next = NULL;
}
}

{
{
return;
}
else
{
}
}

{
while (cur != NULL)
{
if (cur->data == x)
{
return cur;
}
else
{
cur = cur->next;
}
}
return NULL;
}

void SListInsert(SLNode** pphead, SLNode* pos, DataType x)
{
{
SListPushFront(pphead, x);//When inserting at the first node, the header insertion function is called directly
}
else
{
//Find the previous node of pos
while (cur->next != pos)
{
cur = cur->next;
}
cur->next = newnode;
newnode->next = pos;
}
}

{
{
}
else
{
while (cur->next != pos)
{
cur = cur->next;
}
cur->next = pos->next;
free(pos);
pos = NULL;
}
}

void SListModify(SLNode** pphead, SLNode* pos, DataType x)
{
while (cur != pos)
{
cur = cur->next;
}
cur->data = x;
}

{
while (cur != NULL)
{
SLNode* next = cur->next;
free(cur);
cur = next;
}
}

{
printf("************    1,Head insert      2. Tail insertion    ************\n");
printf("************    3,stay pos Insert data from location    ************\n");
printf("************    4,Header deletion      5. Tail deletion    ************\n");
printf("************    6,delete pos Location data    ************\n");
printf("************    7,Modify data 8. Print data ************\n");
printf("********************* -1,sign out *********************\n");
}
int main()
{
int option = 1;
DataType x = 0;
SLNode* pos = NULL;
while (option != -1)
{
scanf("%d", &option);
switch (option)
{
case 1:
printf("Please enter the data to insert to-1 end\n");
do
{
scanf("%d", &x);
if (x != -1)
} while (x != -1);
break;
case 2:
printf("Please enter the data to insert to-1 end\n");
do
{
scanf("%d", &x);
if (x != -1)
} while (x != -1);
break;
case 3:
//Insert data in pos position
printf("Please enter the name before inserting pos Location data\n");
scanf("%d", &x);
if (!pos)
{
printf("No such data\n");
}
else
{
printf("Please enter the data to insert\n");
scanf("%d", &x);
}
break;
case 4:
break;
case 5:
break;
case 6:
printf("Please enter the name before deleting pos Location data\n");
scanf("%d", &x);
if (!pos)
{
printf("No such data\n");
}
else
{
}
break;
case 7:
printf("Please enter the value of the modified position\n");
scanf("%d", &x);
if (!pos)
{
printf("No such data\n");
}
else
{
printf("Please enter the value you want\n");
scanf("%d", &x);
}
break;
case 8:
break;
case -1:
printf("sign out\n");
break;
default: