The foundation is weak and the understanding is still shallow. If there are mistakes, please correct them.
Linear list single chain list (Ⅲ)

Various basic operations of headless node and headless node in single linked list (complete code)

Node with head

#include<stdio.h>
#include<malloc. h> / / this header file is required when opening a new cell with malloc function
typedef int ElemType;
typedef struct LNode //Define single linked list node type
{
	ElemType data; //Data domain
	struct LNode *next; //Pointer field
}LNode, * LinkList;

bool ListEmpty(LinkList &L)  //Judge whether the linear table is empty
{
	return(L->next == NULL); //Return 0 or 1 in C language and true or false in C + +
}

void InitList(LNode * &L) //Initialize linear table
{
	L = (LNode *)malloc(sizeof(LNode)); //Create header node
	L->next = NULL; //Its next field is set to NULL
}

void HeadInsert(LinkList &L) //Reverse creation of single linked list
{
	LNode *s;
	for (int i = 1; i <= 5; i++)  
	{
		s = (LNode *)malloc(sizeof(LNode));
		s->data = i; //Assign values to data fields
		s->next = L->next;
		L->next = s;
	}
}

void DispList(LinkList &L) //Output linear table
{
	LNode *p = L->next; //p points to the first node
	while (p)
	{
		printf("%d ", p->data); //data field of output p node
		p = p->next; //p move to the next node
	}
}

int ListLength(LinkList &L) //Find the length of linear table
{
int n = 0; //n is used for counting, and the initial value is 0
	LNode * p = L->next; //p points to the first node
	while (p!= NULL) //Loop when the pointer field of p is not NULL
	{
		n++; //Count value + 1
		p = p->next; //p move to the next node
	}
	return n;
}

bool GetElem(LinkList &L, int i, ElemType &e) //Find the value of a data element in the linear table
{
	LNode *p = L; //p refers to the head node, and j is set to 0 (that is, the serial number of the head node is 0)
	int j = 0;
	if (i <= 0) return false; //i error return false
	while (p != NULL && j < i)
	{
		j++;
		p = p->next; //p move to the next node
	}
	if (p == NULL) return false; //If the ith data node does not exist, false is returned
	else //If the ith data node exists, return true
	{
		e = p->data;
		return true;
	}
}
 
bool LocateElem(LinkList &L, ElemType e) //Find by element value
{
	LNode *p = L->next; //p points to the first node, and i is set to i (that is, the serial number of the first node is 1)
	ElemType i = 1;
	while (p != NULL && p->data != e) //Find the node whose data value is e, and its sequence number is i
	{
		p = p->next; //p move to the next node
		i++;
	}
	if (p == NULL) return 0; //There is no node with value e, and 0 is returned
	else return i; //If there is a node with value e, return its logical sequence number i
}

bool ListInsert(LinkList L, int i, ElemType e) //Insert data element
{
	LNode *p = L, *s; //p refers to the head node, and j is set to 0 (that is, the serial number of the head node is 0)
	int j = 0;
	if (i <= 0) return false; //i error returns false
	while (p != NULL && j < i - 1) //Find node i-1
	{
		j++;
		p = p->next; //p move to the next node
	}
	if (p == NULL) //The i-1 node is not found, and false is returned
		return false;
	else //Find the i-1 node p, insert a new node and return true
	{
		s = (LNode *)malloc(sizeof(LNode));
		s->next = p->next;
		s->data = e; //Create a new node s and set its data field to e
		p->next = s; //Insert node s after node p
		return true; //Return true to indicate successful insertion of the ith node
	}
}

bool ListDelete(LinkList &L, int i, ElemType &e) //Delete data element
{
	LNode *p = L, *q; //p refers to the head node, and j is set to 0 (that is, the serial number of the head node is 0)
	int j = 0;
	if (i <= 0) return false; //i error returns false
	while (p != NULL && j < i - 1) //Find node i-1
	{
		j++;
		p = p->next; //p move to the next node
	}
	if (p == NULL) return false; //The i-1 node is not found, and false is returned
	else //Find the i-1 node p
	{
		q = p->next; //q points to the ith node
		if (q == NULL) //If the ith node does not exist, false is returned
			return false;
		e = q->data;
		p->next = q->next; //Delete q node from single linked list
		free(q); //Release q node
		return true; //Returning true indicates that the ith node has been deleted successfully
	}
}

void DestoryList(LinkList &L) //Destroy linear table
{
	LNode* pre = L, * p = L->next; //pre points to the precursor node of node p
	while (p != NULL) //Scan single linked list L
	{
		free(pre); //Release free node 
		pre = p; //Move one node after pre and p synchronization
		p = pre->next;
	}
	free(pre); //At the end of the loop, p is NULL, pre points to the tail node and releases it
}

int main()
{
	LNode *L;

	InitList(L); //Initialize the linear table and create an empty single linked table
	printf("Is it an empty chain now%d\n\n", ListEmpty(L)); //If 1 is returned, the current linear table is empty

	HeadInsert(L); //Call the function and create a single linked list by head interpolation
	printf("Is it an empty chain now%d\n\n", ListEmpty(L));

	LNode *p = L;
	printf("Output values in linear table:");
	DispList(L); //Call the function to output the single linked list
	printf("\n\n");

	printf("The length of the established linear table is:%d\n\n", ListLength(L)); //Call the function to receive the length of the returned linear table

	int num;
	printf("The values for this location are:%d\n Did you find it successfully?:%d\n\n", num, GetElem(L, 4, num));
	//Call the function to judge whether there is the ith data node in the single linked list L. if so, return the value

	
	printf("The first logical sequence number equal to this value is:%d\n\n",LocateElem(L, 3));
	//Call the function to find the node with the first value field equal to e from the beginning in the single linked list L, and return the logical sequence number if any
	
	printf("Insert an element into a location. Did you insert it successfully%d\n",ListInsert(L, 3, 4)); 
	printf("The length of the linear table after insertion is:%d\n", ListLength(L));
	printf("Output the values in the linear table after insertion:");
	DispList(L);
	printf("\n\n");

	ElemType e;
	printf("Delete the element at a certain location. Are you successful%d\n",ListDelete(L, 2, e));
	printf("The deleted element values are:%d\n", e);
	printf("The length of the deleted linear table is:%d\n", ListLength(L));
	printf("Output the values in the linear table after deletion:");
	DispList(L);
	printf("\n\n");

	DestoryList(L); //Destroy linear table
	return 0;
}

Program analysis:

• Emphasize that this is a linked list - use LinkList;
• Emphasize that this is a node - use LNode *;
• Operation results:
  

Headless node

#include<iostream>
using namespace std;
#include<malloc. h> / / this header file is required when opening a new cell with malloc function
typedef int ElemType;
typedef struct LNode //Define single linked list node type
{
	ElemType data; //Data domain
	struct LNode *next; //Pointer field
}LNode, * LinkList;

bool ListEmpty(LinkList &L)  //Judge whether the linear table is empty
{
	return(L == NULL); 
}

void InitList(LNode * &L) //Initialize linear table
{
	L  = NULL; 
}

void HeadInsert(LinkList &L) //Reverse creation of single linked list
{
	LNode *s;
	int i;
	for (i = 1; i <= 5; i++)
	{
		s = (LNode *)malloc(sizeof(LNode));  //Create a new node
		s->data = i;
		if (L == NULL)
		{
			L = s;
			s->next = NULL;
		}
		else
		{
			s->next = L;
			L = s;
		}
	}
}

void DispList(LinkList &L) //Output linear table
{
	LNode *p = L; //p points to the first node
	while (p != NULL)
	{
		cout<<p->data<<' '; //data field of output p node
		p = p->next; //p move to the next node
	}
}

int ListLength(LinkList& L) //Find the length of linear table
{
int n = 0; //n is used for counting, and the initial value is 0
	LNode * p = L; //p points to the first node
	while (p != NULL) 
	{
		n++; //Count value + 1
		p = p->next; //p move to the next node
	}
	return n;
}

bool GetElem(LinkList& L, int i, ElemType& e) //Find the value of a data element in the linear table
{
	LNode* p = L; //p refers to the head node
	int j = 1; //j set to 1 (i.e. the serial number of the head node is 1)
	if (i <= 0) return false; //i error return false
	while (p != NULL && j < i)
	{
		j++;
		p = p->next; //p move to the next node
	}
	if (p == NULL) return false; //If the ith data node does not exist, false is returned
	else //If the ith data node exists, return true
	{
		e = p->data;
		return true;
	}
}
 
bool LocateElem(LinkList &L, ElemType e) //Find by element value
{
	LNode *p = L; //p points to the first node
	int i = 1; //I is set to I (i.e. the serial number of the first node is 1)
	while (p != NULL && p->data != e) //Find the node whose data value is e, and its sequence number is i
	{	
		i++;
		p = p->next; //p move to the next node
	}
	if (p == NULL) return 0; //There is no node with value e, and 0 is returned
	else return i; //If there is a node with value e, return its logical sequence number i
}

bool ListInsert(LinkList &L, int i, ElemType e) //Insert data element
{
	LNode *p = L, *s; //p refers to the head node
	int j = 1; //j is set to 1 (i.e. the serial number of the head node is 1)
	if (i <= 0) return false; //i error returns false
	while (p != NULL && j < i - 1) //Find node i-1
	{
		j++;
		p = p->next; //p move to the next node
	}
	if (p == NULL) //The i-1 node is not found, and false is returned
		return false;
	else //Find the i-1 node p, insert a new node and return true
	{
		s = (LNode *)malloc(sizeof(LNode));
		s->data = e; //Create a new node s and set its data field to e
		if (i == 1)
		{
			s->next = L;
			L = s;
		}
		else
		{
			s->next = p->next;
			p->next = s;
		}//Insert node s after node p
		return true; //Return true to indicate successful insertion of the ith node
	}
}

bool ListDelete(LinkList &L, int i, ElemType &e) //Delete data element
{
	LNode *p = L, *q; 
	int j = 1; //p refers to the head node, and j is set to 1 (that is, the serial number of the head node is 1)
	if (i <= 0) return false; //i error returns false
	while (p != NULL && j < i - 1) //Find node i-1
	{
		j++;
		p = p->next; //p move to the next node
	}
	if (p == NULL) return false; //The i-1 node is not found, and false is returned
	else //Find the i-1 node p
	{
		if (i == 1)
		{
			e = p->data;
			L = p->next;
			free(p);
			return true;
		}
		else 
		{
			q = p->next; //q points to the ith node
			if (q == NULL) //If the ith node does not exist, false is returned
				return false;
			e = q->data;
			p->next = q->next; //Delete q node from single linked list
			free(q); //Release q node
			return true; //Returning true indicates that the ith node has been deleted successfully
		}
	}
}

void DestoryList(LinkList &L) //Destroy linear table
{
	LNode* pre = L, * p = L->next; //pre points to the precursor node of node p
	while (p != NULL) //Scan single linked list L
	{
		free(pre); //Release free node 
		pre = p; //Move one node after pre and p synchronization
		p = pre->next;
	}
	free(pre); //At the end of the loop, p is NULL, pre points to the tail node and releases it
}

int main()
{
	LNode * L;
	InitList(L); //Initialize the linear table and create an empty single linked table
	cout<<"Is it an empty chain now?-"<<' ' <<boolalpha<< ListEmpty(L) << endl; //If true is returned, the current linear table is empty
	
	HeadInsert(L); //Call the function and create a single linked list by head interpolation
	cout << "Is it an empty chain now?-" << ' ' << boolalpha << ListEmpty(L) << endl;
	LNode * p=L;
	printf("Output values in linear table:");
	DispList(L); //Call the function to output the single linked list
	printf("\n\n");

	printf("The length of the established linear table is:%d\n\n", ListLength(L)); //Call the function to receive the length of the returned linear table

	int num;
	cout << "Did you find it successfully?- " << boolalpha << GetElem(L, 6, num)<<endl;
	printf("The values for this location are:", num);
	printf("\n");
	//Call the function to judge whether there is the ith data node in the single linked list L. if so, return the value

	printf("The first logical sequence number equal to this value is:%d\n\n",LocateElem(L, 7));
	//Call the function to find the node with the first value field equal to e from the beginning in the single linked list L, and return the logical sequence number if any
	
	cout<<"Insert an element into a position. Did you insert it successfully?-"<<boolalpha<<ListInsert(L, 1, 6)<<endl; 
	printf("The length of the linear table after insertion is:%d\n", ListLength(L));
	printf("Output the values in the linear table after insertion:");
	DispList(L);
	printf("\n\n");

	ElemType e;
	cout<<"Delete the element at a certain location. Are you successful"<<boolalpha<<ListDelete(L, 1, e)<<endl;
	printf("The deleted element values are:%d\n", e);
	printf("The length of the deleted linear table is:%d\n", ListLength(L));
	printf("Output the values in the linear table after deletion:");
	DispList(L);
	printf("\n\n");

	DestoryList(L); //Destroy linear table
	
	return 0;
}

Program analysis:

• It can be seen from the running results of the header node that when the return value type of the function is bool, only 1 can represent true and 0 can represent false in C language. Therefore, in the headless node program, some lines use the cout output of C + +, because C + + can make the bool type return true or false, just add "boolalpha".
• ! In some functions with and without head nodes, the loop condition should first write "P! = null", because if p=NULL, the logic and operation will not continue to perform the following operations. At this time, it indicates that the traversal of the linked list has ended, and the value is not found in the whole linked list. In this case, false should be returned.
  

Comparison of headless and headless nodes

-The differences between a single linked list with a header node and a single linked list without a header node are: different points, different data fields, and different brevity.

• Different points
  1. Single linked list with header node: the header pointer points to the header node.
  2. Single linked list without header node: the header pointer points to the first primitive node.
• Different data fields
  1. Single linked table with header node: no information can be set in the data field, or information such as table length can be recorded.
  2. Single linked list without header node: no information can be stored in the data field.
• Different simplicity
  1. Single linked list with header node: it reduces the judgment of special cases when adding and deleting single linked list, and reduces the complexity of the program.
  2. Single linked list without header node: you need to judge the first node when deleting or adding.