链表及其操作

链表

一个双向链表（链表都是由一个个节点构成的），包含2个指针（实际就是2个节点的地址）：一个指向前一个节点，一个指向后一个节点

struct rt_list_node 
{
	struct rt_list_node *next; /* 指向后一个节点 */
	struct rt_list_node *prev; /* 指向前一个节点 */
};
typedef struct rt_list_node rt_list_t;

链表操作

初始化

初始化一个链表，首先创建头节点l：

rt_inline void rt_list_init(rt_list_t *l)
{
    l->next = l->prev = l;
}

从代码可以看出，节点l的next和prev指针均指向自己，如下

插入节点

在节点l后插入节点n

rt_inline void rt_list_insert_after(rt_list_t *l, rt_list_t *n)
{
    l->next->prev = n;  //1
    n->next = l->next;  //2

    l->next = n;  		//3
    n->prev = l;		//4
}

分析：

在初始化时 l->next=l, 所以l->next->prev就是l-prev，即l->prev指向n

初始化时 l->next=l, 所以n->next指向l

l->next指向n

n->prev指向l

两个节点可能不是很清晰，所以再插入一个节点n2，结果如下图

当然，节点不仅可以在最后插入，也可以在中间插入，如下

把一个节点n插入到2个节点l和n1之间，就是要把节点n1的prev指针指向n，n的next指针指向节点n1，然后把l的next指针指向n，n的prev指针指向l；

修改时要注意顺序，因为根据链表的特性，查找节点只能从前面往后遍历，因此必须先修改n和n1之间的指针，再修改l和n之间的指针。

整理一下，得

在链表表头前面插入一个节点

rt_inline void rt_list_insert_before(rt_list_t *l, rt_list_t *n)
{
    l->prev->next = n;  //1
    n->prev = l->prev;  //2

    l->prev = n;   		//3
    n->next = l;		//4
}

删除节点

从双向链表删除一个节点

rt_inline void rt_list_remove(rt_list_t *n)
{
    n->next->prev = n->prev;	//1
    n->prev->next = n->next;	//2

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