Single list
- Design ideas
- Preparatory work for adding, deleting, checking and modifying
- Head plug and tail plug
- Delete the head and delete the tail
- find and destroy
- Insert the node with data x after pos and delete the node after pos
- full code
Design ideas
The linked list is a non-sequential and non-sequential storage structure in the physical storage structure. The logical order of the data elements is through the linked list The pointers in link order are implemented in .

Preparatory work for adding, deleting, checking and modifying
There are two source files and one header file:
linked.h linked.c test.c
Node Type Definition
copy//linked.h typedef int type;//Redefine the name of the data type, so that it is convenient to replace the data type in the linked list typedef struct Chain_table//linked list type { type data;//data field struct Chain_table* next;//pointer field }ct;
define a head node
copy//test.c ct* head = NULL;//head node pointer
The default point is empty, if there is no data, it will be empty Open up node space
copy//linked.c ct* crunode(type x)//Create a node dynamically { ct* cur = (ct*)malloc(sizeof(ct)); if (cur == NULL) { perror("malloc fail"); exit(-1);//end of program } cur->data = x; cur->next = NULL; return cur;//Returns the address of the opened node }
print linked list function It cannot be asserted here whether it is a null pointer, because when there is no data, the point pointed to by the head node is a null pointer, so we also need to print the null pointer (because it is more vivid, and actually does not need to print NULL)
copy//linked.c void SListPrint(ct* phead)//print linked list { ct* cur = phead;//Let cur also point to the location of the head pointer while (cur) { printf("%d ", cur->data); cur = cur->next; } printf("NULL\n");//print the NULL at the end }
Head plug and tail plug
The following functions are all in the linked.c file tail plug
copyvoid SListPushBack(ct** phead, type x)//tail plug { assert(phead);//The assertion here is because phead points to the head node, so it cannot be empty ct* newnode = crunode(x); if (*phead == NULL)//head node pointer is null { *phead = newnode;//Let the head node point to the newly created node } else//Head node pointer is not null { ct* cur = *phead; while (cur->next)//find the last node { cur = cur->next; } cur->next = newnode;//Let the next area of the last node store the address of the newly created node } }
It should be noted here that the address of the head node is passed by the second-level pointer, otherwise it will cause the formal participation and actual parameters to open up two independent spaces, so that the head node will not move due to the transfer function.

In this way, the head can be controlled by phead. plug
copyvoid SListPushFront(ct** phead, type x)//plug { assert(phead); ct* newnode = crunode(x); newnode->next = *phead; *phead = newnode; }
The head insertion does not need to be divided into situations, because even if the linked list is empty, the head insertion is to store the position pointed to by the head node in the next of the newly created node.
Delete the head and delete the tail
tail delete
copyvoid SListPopBack(ct** phead)//tail delete { assert(phead); assert(*phead);//Check if it is an empty list ct* cur = *phead; if (cur->next == NULL)//Determine whether there is only one node left in the linked list { free(cur); cur = NULL; *phead = NULL; } else { while (cur->next->next)//Determine whether to come to the end { cur = cur->next; } free(cur->next);//cur->next->next is empty, it means that cur->next points to the last node, release it cur->next = NULL;//Set the next of the end node to a null pointer } }

head delete
copyvoid SListPopFront(ct** phead)//head delete { assert(phead); assert(*phead);//Check if the linked list is empty ct* cur = *phead; *phead = cur->next; free(cur);//Free up head node space cur = NULL; }
find and destroy
destroy
copyvoid SListDestory(ct** phead)//Destroy linked list { assert(phead); ct* cur = *phead; while (cur) { ct* tai = cur->next;//Keep the next node of cur free(cur); cur = tai; } *phead = NULL;//Finally, let the head node pointer become a null pointer }
look up When designing a search, if the return value is not equal to a null pointer, it exists
copyct* SListFind(ct* phead, type x)//search { ct* cur = phead; while (cur) { if (cur->data == x) { return cur;//Find the corresponding address } cur = cur->next; } return NULL;//Returns a null pointer if not found }
Insert the node with data x after pos and delete the node after pos
This works with our lookup The address after the returned pos is where we want to insert and delete insert
copyvoid SListInsertAfter(ct* pos, type x)//Insert a node with data x after pos { assert(pos); ct* newnode = crunode(x); newnode->next= pos->next; pos->next = newnode; }

delete
copyvoid SListEraseAfter(ct* pos)//Delete the node after pos { assert(pos); if (pos->next == NULL) { return;//If the node behind pos is empty, just return it directly } else { ct* cur = pos->next; pos->next = cur->next; free(cur); cur = NULL; } }
As for inserting and deleting in front of pos, I don’t need to write it, just add a pointer to find the node in front of pos.
full code
linked.h
copy#include <stdio.h> #include <stdlib.h> #include <assert.h> typedef int type;//Redefine the name of the data type, so that it is convenient to replace the data type in the linked list typedef struct Chain_table//linked list type { type data;//data field struct Chain_table* next;//pointer field }ct; //function declaration ct* crunode(type x);//The development of the head node void SListPrint(ct* phead);//print linked list void SListPushBack(ct** phead, type x);//tail plug void SListPushFront(ct** phead, type x);//plug void SListPopBack(ct** phead);//tail delete void SListPopFront(ct** phead);//head delete void SListDestory(ct** phead);//Destroy linked list ct* SListFind(ct* phead, type x);//look up void SListInsertAfter(ct* pos, type x);//Insert a node with data x after pos void SListEraseAfter(ct* pos);//Delete the node after pos
linked.c
copy#include "linked.h" ct* crunode(type x)//Create a node dynamically { ct* cur = (ct*)malloc(sizeof(ct)); if (cur == NULL) { perror("malloc fail"); exit(-1);//end of program } cur->data = x; cur->next = NULL; return cur;//Returns the address of the opened node } void SListPrint(ct* phead)//print linked list { ct* cur = phead; while (cur) { printf("%d ", cur->data); cur = cur->next; } printf("NULL\n");//print the NULL at the end } void SListPushBack(ct** phead, type x)//tail plug { assert(phead); ct* newnode = crunode(x); if (*phead == NULL)//head node pointer is null { *phead = newnode; } else//Head node pointer is not null { ct* cur = *phead; while (cur->next) { cur = cur->next; } cur->next = newnode; } } void SListPushFront(ct** phead, type x)//plug { assert(phead); ct* newnode = crunode(x); newnode->next = *phead; *phead = newnode; } void SListPopBack(ct** phead)//tail delete { assert(phead); assert(*phead); ct* cur = *phead; if (cur->next == NULL) { free(cur); cur = NULL; *phead = NULL; } else { while (cur->next->next) { cur = cur->next; } free(cur->next); cur->next = NULL; } } void SListPopFront(ct** phead)//head delete { assert(phead); assert(*phead);//Check if the linked list is empty ct* cur = *phead; *phead = cur->next; free(cur);//Free up head node space cur = NULL; } void SListDestory(ct** phead)//Destroy linked list { assert(phead); ct* cur = *phead; while (cur) { ct* tai = cur->next; free(cur); cur = tai; } *phead = NULL; } ct* SListFind(ct* phead, type x)//search { ct* cur = phead; while (cur) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL; } void SListInsertAfter(ct* pos, type x)//Insert a node with data x after pos { assert(pos); ct* newnode = crunode(x); newnode->next= pos->next; pos->next = newnode; } void SListEraseAfter(ct* pos)//Delete the node after pos { assert(pos); if (pos->next == NULL) { return; } else { ct* cur = pos->next; pos->next = cur->next; free(cur); cur = NULL; } }
test.c
copy#include "linked.h" void test() { ct* head = NULL;//head node pointer SListPushBack(&head, 1);//tail plug SListPushBack(&head, 2); SListPushFront(&head, 3);//plug SListPushFront(&head, 4); SListPopFront(&head);//head delete SListPopBack(&head);//tail delete ct* pos = SListFind(head, 1);//look up if (pos) { printf("YES\n"); SListInsertAfter(pos, 9); SListPrint(head);//print linked list SListEraseAfter(pos); } else { printf("NO\n"); } SListPrint(head); SListDestory(&head);//Destroy linked list SListPrint(head); } int main() { test(); return 0; }
Code running results
