Before realizing the basic functions of single linked list, first introduce what is single linked list and the basic idea of adding, deleting, checking and modifying.

1, A brief introduction to linked list and single linked list

(1) Linked list

Overview: each element in the linear table has a unique precursor element and successor element.

When designing the chain storage structure, each logical element is stored separately with a node. In order to represent the logical relationship, the pointer field is added.

• Each physical node adds a pointer field - > single linked list pointing to subsequent nodes.
• Each physical node adds a pointer field to the successor node and a pointer field to the predecessor node - > double linked list.

(2) Single linked list

1. Statement of single linked list

typedef int SListType;//Declare data types in a single linked list
typedef struct SListNode //Declare single linked list node type
{
	SListType data;
	struct SListNode* next;//Point to subsequent nodes
}SListNode;

2. Characteristics of single linked list

After accessing a node, you can only access its successor node, but not its predecessor node.

3. Application for new node of single linked list

//Node addition or creation of single linked list
SListNode* BuySListNode(SListType x) {
	SListNode* NewNode = (SListNode*)malloc(sizeof(SListNode));//Apply for a space as a new node
	if (NewNode == NULL) {
		printf("Memory request failed!");
		return;
	}
	NewNode->data = x;//Import data
	NewNode->next = NULL;//Initialize successor
	return NewNode;//Return to new node
}

4. Insert single linked list

Insert operation: insert the new node s with the value of x after the p node.

Features: you only need to modify the pointer field of relevant nodes without moving nodes.

//Insert after any insertion position of single linked list
void SListInsertAfter(SListNode** ppSList, int pos, SListType x) {
	//1. Find pos node. 2. Judge whether next is equal to NULL in pos position. If it is, an error will be reported. 3. Insert x after pos.
	SListNode* cur = *ppSList;
	int i = 1;
	while (cur!=NULL && i<pos) {
		//Find pos node
		cur = cur->next;
		i++;
	}
	if (cur==NULL || i>pos) {
		return;
	}
	else {
		SListNode* NewNode=BuySListNode(x);
		NewNode->next = cur->next;
		cur->next = NewNode;
	}
}

Head insertion and tail insertion of single linked list (the above code can also be realized)

//Single chain meter insertion
void SListPushFront(SListNode** ppSList, SListType x) {
	SListNode* NewNode = BuySListNode(x);
	if (*ppSList == NULL) {
		*ppSList = NewNode;
	}
	else {
	NewNode->next = *ppSList;
	*ppSList = NewNode;
	}
}

//Single chain table tail insertion
void SListPushBack(SListNode** ppSList, SListType x) {
	SListNode* NewNode = BuySListNode(x);
	if (*ppSList == NULL) {
		NewNode->data = x;
		*ppSList = NewNode;
	}
	else {
		SListNode* cur = *ppSList;
		while (cur->next != NULL) {
			cur = cur->next;
		}
		cur->next = NewNode;
	}
}

5. Deletion of single linked list node

Delete: deletes a node after the p node.

Features: you only need to modify the pointer field of relevant nodes without moving nodes.

//Delete any position in the single linked list
void SListEraseAfter(SListNode** ppSList, int pos) {
	int i=1;
	SListNode* next = NULL;
	SListNode* cur = *ppSList;
	if (cur == NULL)
		return;
	while (cur->next != NULL && i < pos) {
		cur = cur->next;
		i++;
	}
	if (cur->next==NULL||i>pos) {
		return;
	}
		next= cur->next;
		cur->next = next->next;
		free(next);
}

Header deletion and tail deletion of single linked list (the above code can also be implemented)

//Single chain header deletion
void SListPopFront(SListNode** ppSList){
	//1. The header pointer is null. 2. There is only one node. 3. There is more than one node.
	if (*ppSList == NULL) {
		return;
	}
	else if ((*ppSList)->next == NULL) {
		free(*ppSList);
		*ppSList = NULL;
	}
	else {
		SListNode* top = *ppSList;
		*ppSList = top->next;
		free(top);
	}
}

//Single chain tail deletion
void SListPopBack(SListNode** ppSList) {
	//1. The header pointer is null. 2. There is only one node. 3. There is more than one node.
	if (*ppSList == NULL)
		return;
	else if((*ppSList)->next == NULL) {
		free(*ppSList);
		*ppSList = NULL;
	}
	else {
		SListNode* prev = NULL;
		SListNode* cur = *ppSList;
		while (cur->next!= NULL) 
		{							//You need to find the last node and the penultimate node
			prev = cur;
			cur = cur->next;
		}
		free(cur);
		prev->next = NULL;
	}
}

6. Single linked list element search and replacement

//Check the value of the single linked list to find out whether the single linked list contains i. If yes, return ok and assign the value to e. otherwise, return error
int SListGet(SListNode* pSList, SListType i, SListType* e) {
	if (pSList == NULL)
		return error;
	SListNode* cur = pSList;
	while (cur) {
		if (cur->data == i) {
			*e = cur->data;
			return ok;
		}
		cur = cur->next;
	}
}

//Check the value of the single linked list to find out whether the single linked list contains i. if there is an address that returns i, otherwise it returns NULL
SListNode* SListGetPos(SListNode* pSList, SListType i) {
	if (pSList == NULL)
		return NULL;
	SListNode* pos = pSList;
	while (pos) {
		if (pos->data == i) {
			return pos;
		}
		pos = pos->next;
	}
}

//For the replacement of single linked list values, first find out whether the single linked list contains i. if it exists, replace i with e, otherwise return NULL
int SListReplace(SListNode* pSList, SListType i, SListType e) {
	SListNode* pos=SListGetPos(pSList, i);
	pos->data = e;
}

7. Printing of single linked list

//Single linked list printing
void SListPrint(SListNode* pSList) {
	SListNode* cur = pSList;
	if (cur == NULL)
		return;
	while (cur != NULL) {
		printf("%d->", cur->data);
		cur = cur->next;
	}
}

If you find an error, please be sure to tell the blogger. The blogger is just a student who has just started learning data structure. Please! This is really important, thank you!

Please look forward to the subsequent updates of the overall creation and destruction of the single linked list!