Guoguo took you to write a linked list, and the primary school students said it was good after reading it

Abstract ： Obviously, we have touched arrays before , I feel that array is already a versatile data storage location . however , If we have been using more complex data （ That is, when there is more data ）, We must feel very disgusted , Because for data structures like arrays , Before you use it yourself , Be sure to define its size , thus , Its storage space is extremely inconvenient in the process of data processing , Because no one wants to make a space budget for the data to be processed , This is a taboo for every programmer , And make it big enough , Only in this way can we meet our requirements ( But if you allocate too much , It will inevitably waste memory ).
So that's why you use linked lists , Learn linked list .

A linked list is a data structure , It makes up for many inconveniences caused by arrays , Let's allocate space for some data at will , Develop memory units as needed .

When it comes to linked lists, we must mention a more important knowledge point is The pointer , Because the data before and after should be related , There must be a series of connection and pointing processing , Then the pointer plays this role , also , In today's programming languages , Nothing can replace the pointer .

If you don't understand pointers , I strongly suggest you read this article ： Teach you to write the pointer of single chip microcomputer hand in hand .

Of course, before learning the linked list , You also need to have basic concepts and knowledge of structure , Why? ？ Because linked lists are multiple structures connected by pointers . Each structure has a member variable that stores pointers , also , The type of this member is the structure type . Every linked list , Each has its own node , These nodes are variables of the structure , Of course , They are also variables of structure type .

If you don't understand the structure , I strongly suggest you read this article ： Teach you to write the structure of single chip microcomputer hand in hand .

When you finish reading and understand the pointer and structure , So if you want to improve and learn the linked list , Then read this article , You must have a feeling of enlightenment , You'll find that , The pointer 、 Structure 、 The linked list is not really difficult .

Don't talk much , Start ：

One 、 Linked list

1、 Basic knowledge of linked list

Let's assume that there are three spies ,ABC.A The offline of is B,B The offline of is C. let me put it another way , Namely A Yes B The address of ,B Yes C The address of . That's what code is like ：

// notes ：: If you don't understand this structure , Go back and fill in the knowledge of structure 
typedef struct spy 
{
    
	char *name;
	struct spy *next;
}spy, *p_spy;

spy A = {
    "A", NULL};
spy B = {
    "B", NULL};
spy C = {
    "C", NULL};
spy D = {
    "D", NULL};

int main( void )
{
    
	p_spy pHead = NULL;// Define a header node , But there is no data stored in these points , For sentinel nodes 
	
	A.next = &B;//A The offline of is B
	B.next = &C;//B The offline of is C
	C.next = NULL;//C No offline 
	
	pHead = &A;	// Let the head node point to the first node A
	while (pHead )
	{
    
		printf("%s\r\n", pHead ->name);
		pHead = pHead ->next; Keep the first item running backwards , Traverse the list 
	}// until pHead  Run to the last item in the list , The next item of the last item is empty , Naturally, I quit 
	while (1);	
}

Draw a picture for everyone

First, we define three structures ,ABC. There must be these three structures in memory . Take another look at the following sentence , What will happen to him ：A.next_addr=&B

Remember the picture above , Structure A Inside next_address, be equal to B The address of . I drew the blue arrow , It just gives us an understanding of the image , Structure A There are B The address of . The core of the linked list is ：

There is a pointer in the linked list structure , This pointer , Equal to the address of other structures .

In terms of human visualization , It's the structure A A pointer inside , Point to the structure B.

First, as a linked list , There must be a head , How can we determine the head of this linked list ？ In fact, we use a pointer to represent the chain header , The code is as follows :

typedef struct spy {
    
	char *name;
	struct spy *next;
}spy, *p_spy;
p_spy pHead = NULL;

Take a look at this code , We define three structures , There is also a structure pointer . They are all variables , There are corresponding spaces in the memory .

In the picture above , In the red box , We use that pointer to represent the chain header , Now this chain header , Its value is empty , That is to say, the address saved in it is empty ： This is an empty list .

How can we judge whether a linked list is empty ？

if(pHead == NULL)
printf("it is empty list");

So how can we add an element to this linked list ？ Let's use a graph to show , Suppose the structure A Put it on the list ：

Again, it's very simple to insert the first item , I make this chain header directly equal to the structure A The address of . We use arrows to indicate , Let's understand the linked list more vividly ：

Add this arrow to this figure , There are no arrows in the code , It's just pHead This variable , Its value is equal to the structure A The address of .

2、 Insertion of linked list

Now put another structure B Put it in the list . There are two ways , You put it at the head of the list ？ Or at the end of the linked list ？
We draw a picture ：

There are only elements in the linked list A. We can do it in A Insert this new element to the left of B, It can also be in A Insert this new element to the right of B. in other words , We can insert new nodes in the head of the linked list , You can also insert a new node at the end of the list . In the picture on the right , The above one is B Insert it at the end of the linked list , Here is a B Insert it at the head of the linked list .
How to write code ？
Let's take a look first , hold B Insert it at the head of the linked list ：

void InsertNodeToHead(spy newNode）
{
    
	/* Insert it at the front of the linked list */
	newNode->next_addr = pHead;// The next node of the newly inserted node is empty 
	pHead = newNode; // The header node points to the newly inserted node 
}

Draw a picture to demonstrate

In this picture , On the left is the code , On the right is the result . Suppose you first insert the structure A, The label in the execution diagram is 2 When it comes to code , Namely ：A.next_addr=pHead Equal to the initial value NULL. Execute the label in the above figure as 3 When it comes to code , Namely ：pHead=A The address of . The result is on the right side of the figure above , The label is also written in the figure 2、 label 3. label 2 Where? A Of next.address be equal to NULL, label 3 Where? pHead Equal to structure A The address of .

Next, let's add a number 2 Elements B, We insert elements at the head of the linked list B.

Use blue labels in this picture , Mark the calling process . On the left is the code , See the label as 4 Code for , You use this function to put elements B Insert the list . How to do it? ？ There are also two steps ：

• The first 1 Step
  Don't you insert it into the head ？ Then I'll let B Point to the head

But the head is equal to A, In fact, it is B Yes A

So now B Yes A, The head also points A.

• The second step ：
  Keep your head pointing B：

This is a complete insertion process .
This figure needs to be supplemented , Let the end point to NULL

Put the linked list , Want to be a team holding hands , It's easy to understand . Just now we talked about inserting an element into the head of the linked list , Then how to insert an element at the end of a linked list ？

Let's assume that there are several elements in this diagram , We are on the right of the last element , And insert new elements

The results are as follows ：

tmp Suppose it's the last element ,B It's a new element .

tmp->next.addr=&B;
B.next addr = NULL;

The key to the problem is , How can I find the last element in the original list .

Take a look at this code , Use one while loop ：

void insertNodeToTail(p_spy newNode)
{
    
	p_spy  temp;// Define a temporary node 
	temp = head;// Let the head node point to the temporary node , Now? temp It is the first item of the whole linked list 
	while(temp)// Find the last element in the original list 
	{
    
		if (temp ->next == NULL)// Found the last node  temp It's the last node 
			break;
		else
			temp = temp ->next;// Keep the first item running backwards , Traverse the list 
	}
	temp ->next = newspy;// The last node inserts a new node 
	newspy->next = NULL;// The next node of the new node is empty , This will insert the new node into the last 
}

The red circle in the picture , What are its characteristics ： its next.addr be equal to NULL. If it's not the last item , Let's take out the one with edge ：temp = temp -> next.addr. This sentence may be difficult for some students to understand , Draw a picture here to explain ：

Insert the code at the end

void InsertNodeToTail(p_spy newNode）
{
    
	p_spy  temp;// Define a temporary node 
	if(pHead == NULL)// If the list is empty 
	{
    
		pHead = newNode;
		newNode->next = NULL;
	}
	else
	{
    
		temp= pHead ;// Let the head node point to the temporary node 
		while (temp)
		{
    
			if (temp->next == NULL) // Found the last node  temp It's the last node 
				break;
			else
				temp= temp->next;
		}
		temp->next = newNode;// The last node inserts a new node 
		newNode->next = NULL;// The next node of the new node is empty , This will insert the new node into the last 
	}
}

void InitInputDevices(void)
{
    
	PInputDevice pDev = g_ptInputDevices;//PInputDevice pDev = &g_tNetInputDevice

	while (pDev)
	{
    
		pDev->DeviceInit();
		pDev = pDev->pNext;// This sentence may be difficult to understand , Understand well , Look at the explanation below 
	}
}


/** PInputDevice pDev = &g_tNetInputDevice;  The first cycle begins  pDev = &g_tNetInputDevice;  because g_tNetInputDevice The node was last added to the linked list  pDev->DeviceInit(); <==>&g_tNetInputDevice->DeviceInit(); The execution is the equipment g_tNetInputDevice Initialization function for  pDev = pDev->pNext; <==> On the right ：&g_tNetInputDevice->pNext  be equal to &g_tKeyDevice  On the left ：pDev  After executing this sentence is  pDev = &g_tKeyDevice  The first cycle is over , here  pDev = &g_tKeyDevice;  The second cycle because  pDev！=NULL; So there will be a second cycle  pDev->DeviceInit(); <==>&g_tKeyDevice->DeviceInit(); The execution is the equipment g_tKeyDevice Initialization function for  pDev = pDev->pNext; <==> On the right ：&g_tKeyDevice->pNext  be equal to NULL( Because there are only two devices ,g_tKeyDevice Is the last added device )  On the left ：pDev  After executing this sentence is  pDev = NULL;  The second cycle is over , here  pDev = NULL;  The second cycle because  pDev！=NULL; So I'm not satisfied while (pDev), The program will not be executed anymore . */

3、 Deletion of linked list

In the list , How to delete an element ?

Look at this picture again , In the linked list, we want to delete this node in the red box

Imagine again , In a team holding hands , A man is leaving , Is the person in front of him holding hands with the person behind him ？

So we need to find out the person in front and the person behind . hypothesis temp It's the person in front , Who is the man behind ？needDeleteNode->next,needDeleteNode Represents the node to delete . How to write the code ：temp->next = People behind = needDeleteNode->next So the key is how we find the person in front ：temp. It's also relatively simple , Traversing the linked list ：

void RemoveNode(p_spy needDeleteNode)
{
    
	p_spy temp;// Define a temporary node , Used to traverse the 
	if (pHead == needDeleteNode)// If the deleted node is exactly the node pointed to by the head node 
	{
    
		pHead = needDeleteNode->next;// Directly let the head node point to the next node of the deleted node 
		return;// return 
	}
	else
	{
    
		/*  find NeedDeleteNode The previous node of  */
		temp = pHead;// Let the head node point to the temporary node temp
		while(temp)
		{
    
			if (temp->next == needDeleteNode)// eureka , The node to be deleted is temp The next node of 
				break;
			else
				temp= temp->next;// Keep looking 
		}		
		if (temp)
		{
    
			temp->next = needDeleteNode-> next;// Let the last node deleted temp The next node of points to the next node of the deleted node , Then delete the original node to be deleted from the linked list .
		}
	}
}

It's also a cycle , If my next item is equal to yours , I'm your last one . After finding it , Just execute this instruction ：temp->next= People behind =needDeleteNode->next.

4、 The use of linked list

Now understand the insertion and deletion of linked lists , So how do we use the linked list ？ For example, in the last class, we said , The head teacher needs to count the information of each student , How to operate with a linked list ？ How to print out all these information , You can traverse the linked list from the chain header ：

void PrintList(void)
{
    
	p_spy temp;	// Define a temporary node , Used to traverse the 
	temp = pHead;// Let the head node point to the temporary node 
	while (tmp)// Loop traversal , until temp==NULL( The next node of the last node is NULL, Exit loop )
	{
    
		printf("%s\r\n", tmp->name);
		tmp = tmp->next;
	}	
}

Now back to our video , Our video also talks about the operation of linked lists
I'll draw this picture for you ：

/*------------------------1. Definition of linked list and node ----------------------------*/

/* Node structure */
typedef struct LIST_NODE {
    
	int data;                        /* Used to store node data */
	struct LIST_NODE *pxNext;        /* Used to point to the next node */
	struct LIST_NODE *pxPrevious;    /* Used to point to the previous node */
}ListNode;


/* List structure */
typedef struct LIST {
    
	unsigned int NumberOfNodes;      /* Used to record the number of linked list nodes */
	ListNode RootNode;               /* Used as the reference point of the circular linked list */
}List;

/*------------------------2. Initialization of linked lists and nodes ---------------------------*/
/* Node initialization */
void ListInitialiseItem(ListNode *pxListNode, int value)
{
      
	pxListNode->data = value;       /* Node data assignment */
}

/* Initialization of linked list */
void ListInitialise(List *pxList)
{
    
	pxList->RootNode.pxNext = &(pxList->RootNode);     /* Because there are no nodes in the linked list at this time , The first node points to itself */
	pxList->RootNode.pxPrevious = &(pxList->RootNode); /* Because there are no nodes in the linked list at this time , The first node points to itself */
	
	pxList->NumberOfNodes = 1;                         /* The linked list node count is initialized to 1, That is, there is only one root node */     
}

/*------------------------3.1 The node is inserted into the linked list ---------------------------*/
void ListInsertEnd(List *pxList, ListNode *pxInsertListNode)
{
    
	ListNode *pxNextNode = &(pxList->RootNode);                /* Insert the back node of the node */
	ListNode *pxPreviosNode = pxList->RootNode.pxPrevious;     /* Insert the front node of the node */

	
    pxInsertListNode->pxNext = pxNextNode;                     /* The inserted node points to the back node */
	pxInsertListNode->pxPrevious = pxPreviosNode;              /* The insertion node refers to the forward node */ 
	
	pxPreviosNode->pxNext = pxInsertListNode;                  /* The front node points to the insertion node */   
    pxNextNode->pxPrevious = pxInsertListNode;                 /* The back node points to the insertion node */   

   (pxList->NumberOfNodes)++;                                  /* List node count plus 1*/
}

/*------------------------3.2 List delete node ---------------------------*/
void ListRemove(List *pxList, ListNode *pxIListToRemove)
{
    
	ListNode *pxPreviosNode = pxIListToRemove->pxPrevious;     /* Delete the front node of the node */
	ListNode *pxNextNode = pxIListToRemove->pxNext;            /* Delete the post node of the node */
	
    pxNextNode->pxPrevious = pxPreviosNode;                    /* The back node refers to the front node */
    pxPreviosNode->pxNext = pxNextNode;                        /* The front node points to the back node */

	(pxList->NumberOfNodes)--;                                 /* The node count of the linked list minus 1*/
}


int main(void)
{
    
	/*1. Define linked list 、 node */
	List      list;         // Define linked list 
	ListNode  list_node1;   // Defining nodes 1
	ListNode  list_node2;   // Defining nodes 2

	/*2. Initialize linked list 、 node */
	ListInitialise(&list);
	
	ListInitialiseItem(&list_node1, 100);
	ListInitialiseItem(&list_node2, 200);
	
	/*3. Insert the list */
	ListInsertEnd(&list, &list_node1);
	ListInsertEnd(&list, &list_node2);
	
	/*4. Delete node */
	ListRemove(&list, &list_node1);
	
	return 0;
}

First, we define a structure ：List list. It's a variable , There must be a corresponding space in the memory . After initializing the linked list , Its result is like the figure above . Because this linked list has a root node , So set the number of nodes to 1. At the beginning of this list, there was only one element , Its next element is itself , Its last element is itself . This is a two-way circular linked list , The two-way circular linked list is a little more complicated , But how complicated , It is composed of two one-way linked lists , I'm not going to expand on that .