catalogue	catalogue
Sequence table	Single linked list (without additional header node)

preface

• In the previous section, we implemented the basic operations of the sequence table. In this section, we will learn about the single linked list (not the leading node), and realize some basic operations and precautions of the single linked list.

1. Definition of single linked list

1. Single linked list is the simplest linked list representation in the linked list, also known as linear linked list. The linked list is discontinuous. The relationship between nodes is represented by pointers. A node contains two fields:
   
   Data field: generally represented by data, which stores a data element
   Pointer field: store a pointer to the starting storage address of the next node, which plays the role of linking two nodes

2. Structure of single linked list
   
   Head: head pointer, pointing to the first node
   datan: tail node, no successor, and next points to NULL
   If head=NULL, the linked list is empty.

Relationship between each node:
First node and head pointer: a1=head;
The first and second nodes: A2 = A1 - > next;
...
The last node: a (n) = a (n-1) - > next, a (n) - > next = null

2. Characteristics of single linked list

1. The length is easy to expand
2. The logical order may not be consistent with the physical order
3. Data can be stored continuously or discontinuously
4. Each node has a pointer field, which consumes a lot of storage space

3. Basic operation of single linked list

1. Header file

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool. h> / / bool header file
typedef int SLTDataType;//Rename to facilitate changing the data type
typedef struct SListNode
{
	SLTDataType data; //Data domain
	struct SListNode* next; //Pointer field
}SLTNode;

2. Initialization

1. Initialization, open up space for the header pointer, and set it to null after successful development.

void SListInit(SLTNode** phead)
{
	assert(phead);
	*phead = (SLTNode*)malloc(sizeof(SLTNode));
	if (*phead == NULL)
	{
		perror("SListInit");
		return;
	}
	(*phead) = NULL;
}

3. Print

1. Traverse according to the structure of the single linked list. Remember not to traverse with the head pointer. Rename the head pointer to p for traversal, which is highly readable

//ergodic
void SListPrint(SLTNode* phead)
{
	SLTNode* p = phead;
	while (p)
	{
		printf("%d->", p->data);//print data
		p = p->next;//Point to the next node and know that the node is NULL
	}
	printf("NULL\n");
}

4. Create a new node

1. malloc opens up memory to node. If the development fails, exit. If the development succeeds, set node - > data to x and node - > next to null

//Create node
SLTNode* BuySListNode(SLTDataType x)
{
	SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode));
	if (node == NULL)
	{
		perror("BuySListNode");
		exit(-1);
	}
	node->data = x;
	node->next = NULL;
	return node;
}

5. Tail insertion

1. When it is an empty table, it is equivalent to inserting a node at the head of the linked list. The pointer needs to be modified: newnode - > next = * pphead* pphead = newnode;
2. In case of non empty table, insert a new node newnode after the next node of current, and the pointer needs to be modified:
   newnode->next = tail->next; tail->next = newnode;
3. Here, the BuySListNode function is used to create a new node, so only write current - > next = newnode; Readers can change according to their own implementation methods

void SListPushBack(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	if (*pphead == NULL)//If the linked list is NULL, the first node address is given to the head node
	{
		SLTNode* newnode = BuySListNode(x);//Create a new node
		*pphead = newnode;//Give the new node address to the head node
	}
	else
	{
		SLTNode* tail = *pphead;
		//When a node exists
		while (tail->next)//Here, you can judge whether the next node is empty. You cannot judge whether the node is empty. Otherwise, you will directly find the end. If the end is NULL, the insertion will fail
		{
			tail = tail->next;
		}
		SLTNode* newnode = BuySListNode(x);//Call the function to create a new node
		tail->next = newnode;
	}
}

6. Tail deletion

1. When there is only one node, save the initial node with tail, and modify the pointer: tail = *pphead; free(tail); tail=NULL;
2. When there are multiple nodes, save the precursor node with prev, and tail is the successor node. Traverse the linked list, find the tail node, and modify the pointer: prev = tail; tail = tail->next; free(tail); prev->next = NULL;

void SListPopBack(SLTNode** pphead)
{
	assert(pphead);
	//Violent way
	assert(*pphead);//Check whether the linked list is empty
	//Gentle way
	/*if (*pphead == NULL)
	{
		return;
	}*/
	SLTNode* prev = NULL;
	SLTNode* tail = *pphead;
	if (tail->next == NULL)
	{
		free(tail);
		tail = NULL;
	}
	else
	{
		while (tail->next != NULL)
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail);
		prev->next = NULL;
	}
}

7. Head insert

1. As the name suggests, the header is inserted before the first node to become the first node. Modify the pointer: newnode - > next = head; head = newnode;

void SListPushFront(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* newnode = BuySListNode(x);
	newnode->next = *pphead;//Point to the first node
	*pphead = newnode;//The newnode address is given to pphead to become the first node
}

8. Header deletion

1. Header deletion: delete the first node, make the header pointer point to the second node, and modify the pointer: next = head - > next; head = next;

void SListPopFront(SLTNode** pphead)
{
	assert(pphead);
	assert(*pphead);
	SLTNode* nextnode = (*pphead)->next;
	*pphead = nextnode;
	free(*pphead);
	*pphead = NULL;
}

9. Insert

1. A single linked list is usually inserted into a node after the pos position
2. Header, modify the direction: newnode - > next = head; head = newnode;
3. It is neither the first node nor the last node. Modify the direction: newnode - > next = current - > next; current->next = newnode;
4. The last node is modified to point to: newnode - > next = current - > next; current->next = newnode;

//Insert after pos position
void SListInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);
	SLTNode* newnode = BuySListNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

10. Delete

1. Delete at the first node and modify the direction: del = head; head = head->next;
2. Delete in the middle or tail, and modify to: del = current - > next; current->next = del->next;
   

void SListEraseAfter(SLTNode* pos)
{
	assert(pos);
	assert(pos->next);
	SLTNode* nextnode = pos->next;
	pos->next = pos->next->next;
	free(nextnode);
	nextnode = NULL;
}

11. Search

1. Find a node with a value equal to x one by one, find and return the node, otherwise return NULL, and modify the pointer: cur = cur - > next;

SLTNode* SListFind(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* cur = *pphead;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		else
		{
			cur = cur->next;
		}
	}
	return NULL;
}

12. Destroy

1. Release one node by one and modify the pointer: next = cur - > next; free(cur); cur = next;

void SListDestory(SLTNode** pphead)
{
	assert(pphead);
	SLTNode* cur = *pphead;
	while (cur)
	{
		SLTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	*pphead = NULL;
}

13. Get the number of linked list nodes

1. There is a node, size+1, modify pointer: cur = cur - > next;

size_t SListSize(SLTNode* phead)
{
	size_t size = 0;
	SLTNode* cur = phead;
	while (cur)
	{
		size++;
		cur = cur->next;
	}
	return size;
}

4. Precautions for single linked list

matters needing attention:

1. Try not to operate with the head pointer. You can use type renaming to prevent the head pointer from being found and the linked list from being lost. It is very troublesome to not find the head pointer. Each operation involves the head node, such as head plug deletion, traversal, reversing the linked list, etc. the head pointer is required. The purpose of this is to enhance readability
2. When traversing the linked list, check whether the tail of the linked list is empty
3. When inserting and deleting a node, you need to find the node before the insertion point or deletion point
4. When inserting nodes, you need to pay attention to malloc
5. To delete a node, you need to use free to release the opened memory to prevent memory leakage (often forgotten)

5. Expand

Questions about insertion and deletion:

1. Why not insert the node before the pos position: the single linked list is one-way. It is relatively easy to find the successor node of a node. On the contrary, it is more troublesome to choose to find the successor node of a node.
2. Why not delete the node at the pos location: like the first question, deleting the node at the pos location also needs to find the precursor node at the pos location. It is troublesome to let the precursor node point to the next node at the pos location to delete the node at the pos location.

Solution: the following circular double linked list can solve this problem

6. Source code

• If you need the source code, click the following link to view it:
  gitee: https://gitee.com/deng_yuniubi/data-structure.
  GitHub: https://github.com/yuxuanniu6/Data-Struct.