RT thread bidirectional linked list (learning notes)

This article references from [ Wildfire EmbedFire]《RT-Thread Actual combat of Kernel Implementation and application development —— be based on STM32》, For personal study notes only . Please refer to the original text for more detailed contents and steps （ Download to the wildfire center ）

The basic concept of two-way linked list

Double linked list is also called double linked list , It's a kind of linked list , It has two pointers in each data node , Direct successor and direct precursor respectively . therefore , Starting from any node in the double linked list , Can easily access its predecessor and successor nodes . In general, we construct a bidirectional circular list .

—— Baidu Encyclopedia

This form of data structure makes it more convenient to find bidirectional linked list , Especially the traversal of a large amount of data , Because of the symmetry of the two-way linked list , It can easily complete all kinds of insertion 、 Delete and other operations , But you need to pay attention to the front and back direction of operation .

Function interface of bidirectional linked list

Linked list node structure

First introduced RT-Thread Linked list node structure in , This is no different from the two-way linked list we usually define ourselves .

/** * Double List structure */
struct rt_list_node
{
    
    struct rt_list_node *next;           /**<  Tail pointer , Point to next node . */
    struct rt_list_node *prev;           /**<  The head pointer , Point to the previous node . */
};
typedef struct rt_list_node rt_list_t;   /**< Type for lists. */

Initialization of linked list rt_list_init()

The linked list must be initialized before use , Point the head and tail pointers of the linked list to yourself .

/** * @brief initialize a list * * @param l list to be initialized */
rt_inline void rt_list_init(rt_list_t *l)
{
    
    l->next = l->prev = l;
}

picture source ：《RT-Thread Actual combat of Kernel Implementation and application development 》

The initialization function does not apply for space for the chain header , This step requires manual use rt_malloc() To apply for , Refer to the following code for details （ Reference to the original ）.

head = rt_malloc(sizeof(rt_list_t)); //  Apply dynamic memory 
if(RT_NULL == head)
	rt_kprintf(" Dynamic memory request failed ！\n");
else
	rt_kprintf(" Dynamic memory request succeeded ");

rt_kprintf(" Two way linked list initialization ......\n");
rt_list_init(head);
if(rt_list_isempty(head)
	rt_kprintf(" The two-way linked list was initialized successfully ！\n");

Insert a node after the specified node in the linked list rt_list_insert_after()

Before inserting a node , You need to apply for node size memory first （ See below ）, Then insert a new node after the specified node .

/** * @brief insert a node after a list * * @param l list to insert it * @param n new node to be inserted */
rt_inline void rt_list_insert_after(rt_list_t *l, rt_list_t *n)
{
    
    l->next->prev = n;
    n->next = l->next;

    l->next = n;
    n->prev = l;
}

picture source ：《RT-Thread Actual combat of Kernel Implementation and application development 》

Insert a node before the specified node in the linked list rt_list_insert_before()

Before inserting a node , You need to apply for node size memory first , Then insert the new node before the specified node .

/** * @brief insert a node before a list * * @param n new node to be inserted * @param l list to insert it */
rt_inline void rt_list_insert_before(rt_list_t *l, rt_list_t *n)
{
    
    l->prev->next = n;
    n->prev = l->prev;

    l->prev = n;
    n->next = l;
}

picture source ：《RT-Thread Actual combat of Kernel Implementation and application development 》

Here is the sample code for the node insertion operation （ Reference from the original text ）：

//  Dynamically request the memory of the first node 
node1 = rt_malloc(sizeof(rt_list_t));

//  Dynamically request the memory of the second node 
node2 = rt_malloc(sizeof(rt_list_t));

//  take  node2  Insert into  head  Back 
rt_list_insert_after(head, node2);

//  take  node1  Insert into  node2  front 
rt_list_insert_before(node2, node1);

if((node1->prev == head) && (node2->prev == node1))
	rt_kprintf(" Node added successfully !\n");
else
	rt_kprintf(" Failed to add node !\n");

Delete a node from the linked list rt_list_remove()

Deleting a node is easier than adding a node , Just connect the two nodes before and after the node to be deleted , Release the memory of the node to be deleted .

/** * @brief remove node from list. * @param n the node to remove from the list. */
rt_inline void rt_list_remove(rt_list_t *n)
{
    
    n->next->prev = n->prev;
    n->prev->next = n->next;

    n->next = n->prev = n;
}

picture source ：《RT-Thread Actual combat of Kernel Implementation and application development 》

How to delete a node ：

//  The original linked list structure ：head ->> node1 ->> node2 ->> node3
rt_list_remove(node2);
rt_free(node2); //  Release  node2  Of memory 
if(node3->prev == node1) //  Whether the following node is connected to the previous node 
	rt_kprintf(" Node deleted successfully \n");

Bidirectional linked list experiment

#include "board.h"
#include "rtthread.h"


//  Define thread control block pointers 
static rt_thread_t test_thread = RT_NULL;


/****************************************************************************** * @  Function name  ： test_thread_entry * @  work   can  ：  Thread entry function  * @  ginseng   Count  ： parameter  Parameters passed in from outside  * @  Return value  ：  nothing  ******************************************************************************/
static void test_thread_entry(void *parameter)
{
    
	rt_list_t *head;  //  Two way chain header 
	rt_list_t *node1; //  Node of bidirectional linked list 1
	rt_list_t *node2; //  Node of bidirectional linked list 2
	
	head = rt_malloc(sizeof(rt_list_t)); //  Apply dynamic memory 
	if(RT_NULL == head) //  Failed to apply 
		rt_kprintf(" Dynamic memory request failed ！\n");
	else
		rt_kprintf(" Dynamic memory request succeeded , The header node address is %d !\n", head);
	
	rt_kprintf("\n Two way linked list initialization ......\n");
	rt_list_init(head);
	
	if(rt_list_isempty(head))
		rt_kprintf(" The two-way linked list was initialized successfully ！\n");
	
	// Dynamically request the memory of the first node 
	node1 = rt_malloc(sizeof(rt_list_t));
	
	//  Dynamically request the memory of the second node 
	node2 = rt_malloc(sizeof(rt_list_t));
	
	rt_kprintf("\n Add the first node and the second node ......\n");
	
	// Insert separately  node2  and  node1, The final effect is  head ->> node1 ->> node2
	rt_list_insert_after(head, node2);
	rt_list_insert_before(node2, node1);
	
	if((node1->prev == head) && (node2->prev == node1))
		rt_kprintf(" Node added successfully .\n");
	else
		rt_kprintf(" Failed to add node .\n");
	
	rt_kprintf("\n Delete node ......\n");
	rt_list_remove(node1);
	
	rt_free(node1);  //  Free the memory of the first node 
	if(node2->prev == head)
		rt_kprintf(" Node deleted successfully .\n");
	
	while(1)
	{
    
		LED0(ON);
		rt_thread_delay(500); // 500 individual tick（500ms）
		LED0(OFF);
		rt_thread_delay(500);
	}
}

int main(void)
{
    
	//  Hardware initialization and RTT The initialization of is already in component.c Medium rtthread_startup() complete 

	//  Create a dynamic thread 
	test_thread =                                 //  Thread control block pointer 
	rt_thread_create("list_test",                 //  Thread name 
	                test_thread_entry,            //  Thread entry function 
	                RT_NULL,                      //  Entry function parameters 
	                255,                          //  Thread stack size 
				    5,                            //  Thread priority 
					10);                          //  Thread timeslice 
	
	//  Turn on thread scheduling 
	if(test_thread != RT_NULL)
		rt_thread_startup(test_thread);
	else
		return -1;
							
}

Experimental phenomena