1. Basic structure of linked list

The linked list is connected by nodes. The node here is a structure, which is composed of data field and pointer field.

typedef int SListDateType

typedef struct SListNode
{
	SListDataType data；//The data variable is used to store data
	struct SListNode* next；//Next points to the next node;
}SListNode；
//Redeclare the node type with SListNode

Unlike the sequential list, the storage of nodes in the linked list is not continuous, and each node is decentralized. Find the next node through the next pointer.

The next of the tail node in the linked list points to NULL, and a header pointer phead points to the first node in the linked list. If the header pointer is empty, the linked list is empty.

2. Tail insertion of linked list

There are two cases

1.The linked list is empty
2.Linked list is not empty

1. Create a new node, make its pointer field point to NULL, and put the data field into the data to be put. Finally, let the header pointer point to the node.
2. When the linked list is not empty, a node should also be created. Then find the tail pointer (the node whose pointer field is empty) and make it point to the new node.

First encapsulate the function to create a new node

SListNode* CreatSListNode(SListDataType x)
{
	SListNode* newNode = (SListNode*)malloc(sizeof(SListNode));
	if (newNode == NULL)
	{
		printf("Failed to apply for space\n:);
		return 0;
	}
	else
	{
		newNode->next = NULL;
		newNode->data = x;
	}
	return newNode;
}

Create a new node and fill its data field with data. Then find the tail node (create a pointer cur, cur initially points to the first node. If the pointer pointed to by cur's next is not empty, cur should continue to go back and know that cur's next points to NULL, indicating that cur currently points to the tail node), and point the pointer of the tail node to the new node.

When the linked list is empty, the head pointer points to the new node, and the value of the head pointer needs to be changed from NULL to the address of the new node, so the address transfer operation is required here.

There are two cases

void SListPushBack(SListNode** pphead,SListData x)
{
	SListNode* newNode = CreatSListNode(x);
	if (*pphead == NULL)
	{
		*phead = newNode;
		return;
	}
	else
	{
		SListNode* cur = *phead;
		while (cur->next != NULL)
			cur = cur->next;
		cur->next = newNode;
	}

3. Tail deletion of linked list

To delete the tail node of the linked list, you should also find the location of the tail node, release the tail node, and point the pointer of the previous node of the tail node to null. With two pointers, a tail will finally point to the tail node, and prev will finally point to the previous node of the tail node.

1. The linked list is empty and cannot be deleted
2. There is only one node. At this time, the header pointer after deletion needs to point to null, so it is an address transfer operation
3. There is more than one node

void SListPopBack(SListNode** pphead)
{
	if (*pphead == NULL)
		return;
	else if ((*pphead)->next == NULL)//Only one node
	{
		free((*pphead)->next);
		*pphead = NULL;
	}
	else
	{
		SListNode* prev = NULL;
		SListNode* tail = *pphead;
		while (tail->next)
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail);
		prev->next = NULL;
	}		

4. Header insertion and deletion of linked list

Head insert

Create a new node and point the pointer of the new node to phead.

If the linked list is empty and the pointer points to phead, it also points to NULL. At this time, the linked list has a node, but the header pointer needs to be changed, so it is an address transfer operation.

If the linked list has one or more nodes, the operation is the same as that of the empty linked list.

void SListPushFront(SListNode** pphead, SListDara x)
{
	SListNode* newNode = CreatSListNode(x);
	newNode->next = *pphead;
	*pphead = newNode;
}

Header deletion

Similarly, header deletion also changes the header pointer, so the address transmission operation. Implement the header pointer to the second node and release the first node.

If the linked list is empty, it will not be deleted

void SListPopFront(SListNode** pphead)
{
	if (*pphead == NULL)
		return;
	SListNode* first = *pphead;
	*pphead = (*ppehad)->next;
	free(first);
}

5. Search and modify linked list

lookup

The lookup function returns a pointer. Point to the node to be found, find the node through the data field, and define a pointer cur. If the data of cur is equal to the data to be found, the function returns, otherwise cur points to the next node. NULL returned when not found.

SListNode* SListNodeFind(SListNode* phead,SListData x)
{
	if (phead == NULL)
		return NULL; 
	SListNode* cur = phead;
	while (cur)
	{
		if (cur->data == x)
			return cur;
		else
			cur = cur->next;
	}
	return NULL；
}	

modify

The lookup function returns the pointer of the node. Dereferencing the pointer can modify the data in it.

SListNode* pos = SListNodeFind(pList, 2);
if (pos != NULL)
	pos->data = 20;
//Operate like this

6. Node insertion and deletion of linked list

insert

The insertion of a single linked list is after inserting a node into another node. First create a new node, insert the node into the back of the pos pointer pointing to the node, so that the next pointed to by the pos points to the new node, and the next of the new node points to the next pointed to before the pos. Therefore, first point the next of newNode to the next of pos, and then point the next of pos to newNode.
viod SListInsertAfter(SListNode* pos, SListData x)
{
assert(pos);
SListNode* newNode = CreatSListNode(x);
newNode->next = pos->next;
pos->next = newNode;
}

delete

Deleting a number deletes not the memory but the pointer to the memory, that is, releasing the pointer.

The node behind the pos is deleted. First save the node as a next pointer. You need to make the pointer of the pos point to nextnext.

If pos is the tail node and there is no node behind it, do not delete it. If there is only one node after the pos, the pointer of the pos will point to the null pointer after deleting the node, and the pos will become the tail node.

void SListEraseAfter(SListNode* pos)
{
	assert(pos);
	if (pos->next)
	{
		SListNode* next = pos->next;
		SListNode* nextnext = next->next;
		free(next);
		pos->next = nextnext;
	}
}