C language: addition and deletion of linked list in structure

C The linked list in language is an important knowledge point , I think we should first understand that there are three kinds of linked lists , One way linked list 、 Double linked list 、 Circular linked list .

Although there are three , But the essence is the same , There are data fields and pointer fields in a structure , Information used to describe nodes in the data field , The pointer field is used to point to the previous node or the next node .

It is divided into adding by value and adding by position

explain ：

This add 、 Delete to add by value 、 Delete

Now look at the code ：

Add the insertion of header nodes in the linked list

Insert... In the middle

Tail insertion

Deletion is also divided into header deletion

Delete... In the middle

Tail delete

Some details ：

Reference time , If you want to change the header node , Just pass the secondary pointer , There is no need to change the header node , Just pass the first level pointer

  There are many functions in the single linked list that need classification Introduction , Consider the extreme case where it has only one node or no nodes

Note that when there is no need to change the header node , It is absolutely forbidden to dereference the header node and write two in succession ->next when , Because it's easy to have problems in this case

#include <stdio.h>
#include <stdlib.h>

typedef struct Node
{
	int id;
	char* name;
	struct Node* pNext;
}List;
void AddNode(List** pphead, List** ppend, int id, char* name)
{
	List* ptemp =(List*) malloc(sizeof(List));
	ptemp->id = id;
	ptemp->name = name;
	ptemp->pNext = NULL;
	if (*pphead == NULL)
	{
		*pphead = ptemp;
	}
	else
	{
		(*ppend)->pNext = ptemp;
	}
	*ppend = ptemp;
}
void InsertNode(List** pphead, List** ppend, List* pNode, int n)
{
	List* pmark = *pphead;
	if ((*pphead)->id == n)
	{
		pNode->pNext = *pphead;
		*pphead = pNode;
	}
	while (pmark != *ppend)
	{
		if (pmark->pNext->id == n)
		{
			pNode->pNext = pmark->pNext;
			pmark->pNext = pNode;
			return;
		}
		pmark = pmark->pNext;
	}
	(*ppend)->pNext = pNode;
	*ppend = pNode;
}
void DeletNode(List** pphead, List** ppend, int n)
{
	List* pDel = NULL;
	List* pmark = *pphead;
	if ((*pphead)->id == n)
	{
		pDel = *pphead;
		(*pphead) = (*pphead)->pNext;
		free(pDel);
		pDel = NULL;
		return;
	}
	while (pmark != (*ppend))
	{
		if (pmark->pNext->id == n)
		{
			pDel = pmark->pNext;
			pmark->pNext = pDel->pNext;
			free(pDel);
			pDel = NULL;
			if (pmark->pNext == NULL)
			{
				*ppend = pmark;
			}
			return;
		}
		pmark = pmark->pNext;
	}
}
int main()
{
	List* phead = NULL;
	List* pend = NULL;
	AddNode(&phead, &pend, 1, "aa");
	AddNode(&phead, &pend, 2, "bb");
	AddNode(&phead, &pend, 3, "cc");
	AddNode(&phead, &pend, 4, "dd");
	AddNode(&phead, &pend, 5, "ee");

	List* p =(List*) malloc(sizeof(List));
	p->id = 7;
	p->name = "gg";
	p->pNext = NULL;
	/*InsertNode(&phead, &pend, p, 9);*/
	DeletNode(&phead, &pend, 5);

	while (phead != NULL)
	{
		printf("%d    %s\n", phead->id, phead->name);
		phead = phead->pNext;
	}
	return 0;
}

Output ：

1    aa
2    bb
3    cc
4    dd

D:\c++\c Language \ Structure   Linked list \x64\Debug\ Structure   Linked list .exe ( process  15672) Exited , The code is  0.
 To automatically close the console when debugging stops , Please enable “ Tools ”->“ Options ”->“ debugging ”->“ Automatically close the console when debugging stops ”.
 Press any key to close this window . . .

summary ：

Linked list and array are the two basic data structures in the algorithm , In the process of programming, we often use . Although both structures can be used to store a series of data , But each has its own characteristics .

The advantages of arrays , It is convenient to traverse and search the required data . Specify the location in the query array （ Such as... In the query array 4 Data ） In operation , Just do it 1 One operation is enough , The time complexity is O(1). however , The convenience of time , Because arrays take up a continuous space in memory , When doing similar searches or traversals , The essence is the directional offset of the pointer in memory . However , When you need to add and delete array members , The time complexity of completing such operations in the array becomes O(n).