精华内容
下载资源
问答
  • 链表list
    万次阅读 多人点赞
    2016-05-19 14:53:58


    链表

    存储方式离散存储

    定义

    特点

    ① n个节点离散分布。

    ② 彼此通过指针相联系。

    ③ 除头节点和尾节点外,每个节点只有一个前驱节点和一个后续节点。

    ④ 头节点没有前驱节点,尾节点没有后继节点。

    尾节点最后一个有效节点。

    首节点:第一个有效节点。

    头节点第一个有效节点之前的那个节点

    注意

    头节点并不存放有效数据

    ② 加头节点的目的是方便对链表的操作,比如在链表头部进行节点的删除、插入。

    ③ 头节点的数据类型和首节点类型一样。

    头指针:指向头节点的指针变量。

    尾指针:指向尾节点的指针变量。

    如果希望通过一个函数来对链表进行处理,我们至少需要获取链表的哪些参数?

    只需要一个参数:头指针。因为通过头指针可以推算出链表的其他所有参数。

    分类方式1

    ① 单链表:每一个节点只有一个指针域,指向后继节点。

    ② 双链表:每一个节点有两个指针域,分别指向前驱节点和后继节点。

    分类方式2

    ① 循环链表:首尾相连,能通过任何一个几点找到其他所有节点。

    ② 非循环链表:首尾不相连。


    下面介绍链表的各个 成员函数的实现方法
    链表是由有限个节点通过指针线性链接所形成的一种线性数据结构,每个节点包括两部分: 数据域指针域。数据域存储数据,指针域存储指针变量,用该指针变量来存储下一个节点所在的内存地址,从而可以利用该指针来访问下一个节点。
    节点的结构如下:
    // structure of Node
    typedef struct Node
    {
    	int data;		// data field
    	struct Node * next; 	// pointer field
    } NODE, * PNODE;
    



    // delete a node
    struct Node * temp;
    temp = p->next;
    p->next = p->next->next;
    delete temp;

    // add a node in the rear
    q->data = val;
    pTail->next = q;
    q->next = NULL;
    pTail = q;

    // traverse a list
    void traverse_list(PNODE pHead)
    {
    	PNODE p = pHead->next;
    	while (p)
    	{
    		cout << p->data << ", ";
    		p = p->next;
    	}
    	printf("\n");
    }

    // judge whether the list is_empty
    bool is_empty(PNODE pHead)
    {
    	return (pHead->next == NULL);
    }

    // get the length of a list, which calculate the number of valid nodes 
    unsigned length(PNODE pHead)
    {
    	PNODE p = pHead->next;
    	unsigned len = 0;
    	while (p)
    	{
    		len++;
    		p = p->next;
    	}
    	return len;
    }

    // sort the elements in a list
    void sort(PNODE pHead)
    {
    	PNODE p, q, temp;
    	for (p = pHead->next; p != NULL; p = p->next)
    	{
    		for (q = p->next; q != NULL; q = q->next)
    		{
    			if (p->data > q->data)
    			{
    				temp->data = q->data;
    				q->data = p->data;
    				p->data = temp->data;
    			}
    		}
    	}
    }

    // insert a node from list
    bool insert(PNODE pHead, int pos, int val)
    {
    	int n = 0;
    	PNODE p = pHead;
    	/ *
    	// this is another way
    	for (n = 0; n < pos; n++)
    	{
    		if (pHead != NULL)
    		{
    			p = p->next;
    		}
    	}
    	if (n != pos)
    	{
    		return false;
    	}
    	*/
    	while (n < pos && p != NULL)
    	{
    		i++;
    		p = p->next;
    	}
    	if (n != pos || NULL == p)
    	{
    		return false;
    	}
    	
    	PNODE pNew = (PNODE)malloc(sizeof(PNODE));
    	if (NULL == pNew)
    	{
    		printf("Error in dynamic allocating memory!");
    	}
    	pNew->data = val;
    	pNew->next = p->next;
    	p->next = pNew;
    	return true;
    }

    // delete a node from list
    bool delete_list(PNODE pHead, int pos, int * pData)
    {
    	int n = 0;
    	PNODE p = pHead;
    	while (n < pos && p != NULL)
    	{
    		n++;
    		p = p->next;
    	}
    	if (n != pos || NULL == p)
    	{
    		
    		return false;
    	}
    	else if (NULL == p->next)
    	{
    		return false;
    	}
    	PNODE temp = p->next;
    	*pData = temp->data;
    	p->next = p->next->next;
    	free(temp);
    	// q = NULL;
    	return true;
    }
    




    更多相关内容
  • 双向链表List模板类(模拟STL容器中的list),提供插入删除,清空,获取链表长度,判断链表是否为空等操作,内置了迭代器类型
  • 一、双向链表接口函数及相关宏定义分析 0、list_head 结构体 1、offsetof(TYPE, MEMBER) 宏 2、ontainer_of(ptr, type, member) 宏 3、LIST_HEAD_INIT 宏 4、LIST_HEAD 宏 5、INIT_LIST_HEAD 函数 6、LIST_...

    目录

    一、双向链表接口函数及相关宏定义分析

    0、list_head 结构体

    1、offsetof(TYPE, MEMBER) 宏

    2、ontainer_of(ptr, type, member) 宏

    3、LIST_HEAD_INIT 宏

    4、LIST_HEAD 宏

    5、INIT_LIST_HEAD 函数

    6、LIST_HEAD 和 INIT_LIST_HEAD 的区别

    7、list_add 函数

    8、list_add_tail 函数

    9、list_del函数

    10. list_empty函数

    11、list_entry 宏

    12、list_first_entry 宏

    13、list_for_each 宏函数

    14、list_for_each_safe 宏函数

    15、list_for_each_entry 宏函数

    16、list_for_each_entry 宏函数的使用示例

    17、list_for_each_entry_safe函数

    18、list_for_each_entry_reverse 函数

    19、其他

    二、单向链表接口函数及相关宏定义

    三、双向链表综合应用案例-增、减、删、清空操作


       最近在学习链表数据结构,开始是想找个库来使用,后来发现linux内核的链表list.h本身就是一个特别好的库,本文着重的分析list.h文件中功能、重要接口,然后结合实际的应用程序来具体分析。

    下面的条目都是最常用的 宏 和 函数,一些不常用的宏没有列出,有兴趣的可以直接查看源码。

    一、双向链表接口函数及相关宏定义分析

    0、list_head 结构体

        结构体定义原型如下:

    struct list_head {
    	struct list_head *next, *prev;
    };

        这是一个双链表结构,这个结构体定义的相当巧妙,里面并没有 数据元素,只有2个链表指针,分别指向前一个链表点地址和后一个链表点地址,之所以这么定义是为了通用,linux是提供了链表管理接口,并不提供具体的数据结构链表,我们在定义自己的链表的时候,增加一个struct list_head 指针就可以使用list.h提供的所有接口了。

        这个双链表结构,进一步理解,是一个双向循环链表,或者说是双向环形链表,环形链表相比单向链表,优点是头尾相连,这一点对于   遍历 整个链表的 代码实现是很重要也是很方便的,因为最后一个节点的next一定是指向 链表头 head的,而链表头head的prev一定是指向最后一个节点的。链表结构如下:

       从上图可知,使用list_head链表,是需要一个head 指针的,这个指针就相当于一根引线,head本身没有任何数据内容,只有两个方向指针prev和next,而自定义的数据结构中只要包含了list_head指针就可以使用 list提供的所有接口函数了,自定义链表结构如下:

    typedef struct userType{
        void *data;
        struct list_head list
    } USR_LIST_TYPE;

     

    1、offsetof(TYPE, MEMBER) 宏

        该宏的代码原型如下: 

    #define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
    
    //其中 TYPE 为结构体类型,MEMBER为该结构体的 元素,

       该宏的功能是获取 MEMBER在该结构体中的 偏移地址。举例来说: 

    struct test{
     int a;
     int b;
    };

     则执行  offsetof(strtuct test, a) = 0;  offsetof(struct test, b) = 4; 

      具体的解释,可以参考文章《container of 分析

    2、ontainer_of(ptr, type, member) 宏

       该宏的代码原型如下:

    #define container_of(ptr, type, member) ({			\
    	const typeof(((type *)0)->member) * __mptr = (ptr);	\
    	(type *)((char *)__mptr - offsetof(type, member)); })
    
    //其中 type 是结构体类型, member是结构体中的元素,ptr是指向memeber的指针,是个地址

      该宏的功能是:通过结构体类型type中memeber的地址(ptr)获取这个结构体的入口地址。  测试代码如下:

    /*
     * Get offset of a member variable.
     *
     * @param[in]	type	the type of the struct this embedded in
     * @param[in]	member	the name of the variable within the struct.
     */
    #define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
    
    
    /*
     * Get the struct for this entry.
     *
     * @para[in]	ptr 	the list head to take the element from.
     * @para[in]	type 	the type of the struct this is embedded in.
     * @para[in]	member	the name of the variable within the struct.
     */
    #define container_of(ptr, type, member) ({			\
    	const typeof(((type *)0)->member) * __mptr = (ptr);	\
    	(type *)((char *)__mptr - offsetof(type, member)); })
    
    typedef struct 
    {
    	int data1;
    	int data2;
    }TEST_TYPE;
    
    int main(int argc, char *argv[]) {
    
    	TEST_TYPE tests = {1,2};
    	int *ptr = &tests.data2;
    	
    	printf("data1 offset:%d\n", offsetof(TEST_TYPE, data1));
    	printf("data2 offset:%d\n", offsetof(TEST_TYPE, data2));
    	printf("ptr:%d\n", ptr);
    	printf("tests addr:%d\n", container_of(ptr, TEST_TYPE, data2));
    	return 0;
    }
    

     运行结果如下:

    data1 offset:0
    data2 offset:4
    ptr:6487556
    tests addr:6487552
    

      结果验证了所属功能,data2的地址为 ptr也就是 6487556,而data2的偏移地址是4, 所以 结构体tests的地址是 

       6487556 - 4 = 6587552

    3、LIST_HEAD_INIT 宏

      宏原型如下:

    #define LIST_HEAD_INIT(name) {&(name), &(name)}

      先说功能: 该宏的作用是初始化链表节点,将prev和next指针都指向结构体变量name本身。第一次看到这个宏的时候,我是有些蒙圈的,怎么还有这种操作?这是嘛意思?理解这个宏,我们要有这么几个前提:

    ① name 的类型一定是 struct list_head,所以name中自然是包含2个元素的,分别为struct list_head *prev,和struct list_head *next.这连个元素是指针,换言说就是“地址值”

    ② 我们对结构体变量进行赋值或者初始化的时候,可以逐个元素的赋值,也可以通过{ },进行一次性赋值。

    有了 上面2个前提,我们对这个宏展开,功能如下:

    LIST_HEAD_INIT(name) 替换成 {&(name), &(name)} 
    
    其实就是 将 name 本身的地址(&取地址符)分别赋值给 name的两个元素 struct list_head *prev和 *next
    

      所以该宏是不能单独使用的,需要将结果返回给一个 struct list_head 类型的变量。

    4、LIST_HEAD 宏

       该宏的原型如下:

    #define LIST_HEAD(name) \
    	struct list_head name = LIST_HEAD_INIT(name)

       通过 前面的分析,可知该宏的功能:定义1个struct list_head 类型头指针,并且初始化。

    5、INIT_LIST_HEAD 函数

     该函数原型如下:

    static inline void INIT_LIST_HEAD(struct list_head *list)
    {
    	list->next = list;
    	list->prev = list;
    }

     该函数是一个内联函数,内联函数一般都是定义在 头文件中的,调用内联函数时,相当于将内联函数嵌入到被调用函数中了,这样就节省了函数调用所需的栈空间,所以执行效率比较高,list.h中的所有接口函数都是内联函数。

    该函数的功能:初始化 链表头指针head,将其prev和next元素都 指向list 本身。

    6、LIST_HEAD 和 INIT_LIST_HEAD 的区别

        第一次接触这两者的时候,还有点蒙,怎么定义了两个一样 功能的东西,后来一琢磨发现还真完全一样,区别是:

       LIST_HEAD 宏 有2个动作:定义一个struct list_head 变量,然后初始化该变量。

       INIT_LIST_HEAD 只有1个动作:初始化已经定义过的 变量。

       所以在使用INIT_LIST_HEAD 函数时,需要先定义好变量,然后再调用该函数,而LIST_HEAD则不用,一次就 完成了,具体怎么使用,就看 自己的习惯了。

    7、list_add 函数

      函数原型:

    static inline void __list_add(struct list_head *new,
    			      struct list_head *prev,
    			      struct list_head *next)
    {
    	next->prev = new;
    	new->next = next;
    	new->prev = prev;
    	prev->next = new;
    }
    
    /**
     * list_add - add a new entry
     * @new: new entry to be added
     * @head: list head to add it after---此处就是特制链表头 head
     *
     * Insert a new entry after the specified head.
     * This is good for implementing stacks.
     */
    static inline void list_add(struct list_head *new, struct list_head *head)
    {
    	__list_add(new, head, head->next);
    }

      功能:将新链表节点指针 new 添加到 节点 head之后,而且从双链表的设计架构上看,此处的head就是链表头,所以该功能是 插入到 链表头head之后。

    8、list_add_tail 函数

      函数原型:

    /**
     * list_add_tail - add a new entry
     * @new: new entry to be added
     * @head: list head to add it before---此处就是特指链表头。
     *
     * Insert a new entry before the specified head.
     * This is useful for implementing queues.
     */
    static inline void list_add_tail(struct list_head *new, struct list_head *head)
    {
    	__list_add(new, head->prev, head);
    }

      其中 __list_add函数其实是插入功能,将节点new插入到 head之后。

    功能:将 new节点 插入到链表头head节点之前,源码的注释说的很清楚:在head之前 插入一个新的 节点,由于list_head是双向循环链表,也就是一个环形链表,所以这里的 tail 十分形象,就是在链表的 末尾处增加一个新的节点。

    9、list_del函数

      函数原型:

    /*
     * Delete a list entry by making the prev/next entries
     * point to each other.
     *
     * This is only for internal list manipulation where we know
     * the prev/next entries already!
     */
    static inline void __list_del(struct list_head * prev, struct list_head * next)
    {
    	next->prev = prev;
    	prev->next = next;
    }
    
    static inline void list_del(struct list_head *entry)
    {
    	__list_del(entry->prev, entry->next);
    	entry->next = LIST_POISON1;
    	entry->prev = LIST_POISON2;
    }

     功能:删除链表中的一个节点entry,链表节点的删除,其实是删除掉该节点在 链表中的逻辑链接接关系,让该节点的 前一个节点 next直接指向 该节点的后一个节点,而后一个节点的 prev直接指向 该节点的前一个节点。而对于被删除的这个节点指针,并没有进行进行物理删除,而是将其指向了所谓 的 毒指针,这样如果后面再使用这个节点,就可以认为这个节点指针是空的了。我们也可以对list_del进行修改,方便我们的理解。修改如下:

    static inline void list_del(dlist_t *node)
    {
        dlist_t *prev = node->prev;
        dlist_t *next = node->next;
    
        prev->next = next;
        next->prev = prev;
    }

      这个list_del理解起来更容易,不过确实要承认,不如linux中的实现,更加稳定。

    10. list_empty函数

      函数原型:

    /**
     * list_empty - tests whether a list is empty
     * @head: the list to test.
     */
    static inline int list_empty(const struct list_head *head)
    {
    	return head->next == head;
    }
    

      功能:判断 该链表是否为空,这里判断的逻辑,一定是判断这个链表的 头指针 head的next是否指向它自己,如果是,则说明为空,这里其实可以判断链表中任意一个节点是否为空。

    11、list_entry 宏

        原型:

    /**
     * list_entry - get the struct for this entry
     * @ptr:	the &struct list_head pointer.
     * @type:	the type of the struct this is embedded in.
     * @member:	the name of the list_struct within the struct.
     */
    #define list_entry(ptr, type, member) \
    	container_of(ptr, type, member)

      功能:获取链表中某个 节点的地址,这里调用了container_of 宏函数,即通过结构体元素 member的 地址计算出 整个结构体的起始地址,这个函数很重要,主要用于链表的遍历,通过链表中某个节点的某个元素的地址,计算出这个 节点的地址。

    12、list_first_entry 宏

       原型:

    /**
     * list_first_entry - get the first element from a list
     * @ptr:	the list head to take the element from.
     * @type:	the type of the struct this is embedded in.
     * @member:	the name of the list_struct within the struct.
     *
     * Note, that list is expected to be not empty.
     */
    #define list_first_entry(ptr, type, member) \
    	list_entry((ptr)->next, type, member)

      功能:如字面意思,获取链表中第一个元素(节点)的地址,这里已经限定了,一定是  链表的第一个节点的地址,注意,不是head的地址,链表的head中并不会有内容,head的下一个节点才是有效的数据节点,该函数也是 获取第一个first节点的入口地址,但是ptr一般是head,因为使用的时候是ptr->next。

    13、list_for_each 宏函数

       函数 原型:

    /**
     * list_for_each	-	iterate over a list
     * @pos:	the &struct list_head to use as a loop cursor.
     * @head:	the head for your list.
     */
    #define list_for_each(pos, head) \
    	for (pos = (head)->next; prefetch(pos->next), pos != (head); \
            	pos = pos->next)

     功能:正如注释里所说:nterate(迭代、重复),从头遍历整个链表。这里特别注意,pos只是一个临时的变量,该宏函数 一定是从链表的头部head 遍历整个链表,而prefetch 定义为 static inline void prefetch(void *a __attribute__((unused))) { },这个太高级了,我们可以简单的想,一定是判断 pos不是 NULL,只要是 pos->next为空,就说明到了 链表的结尾了。对于一些 工程案例中,没有使用prefetch, 也是可以的,直接判断pos与head是否相等,因为该链表结构为双向循环的。所以如果自己写代码,不想实现prefetch,完全可以删掉, 如下所示:

    #define list_for_each(pos, head) \
    	for (pos = (head)->next;  pos != (head); pos = pos->next)

      注:上面的代码中只有 for(xxx;xxx;xxx),并没有执行的内容,所以真正用的时候,用的 方式如下:

    list_for_each(pos, head){
        /* 循环执行代码 */
    }

    14、list_for_each_safe 宏函数

       原型:

    /**
     * list_for_each_safe - iterate over a list safe against removal of list entry
     * @pos:	the &struct list_head to use as a loop cursor.
     * @n:		another &struct list_head to use as temporary storage
     * @head:	the head for your list.
     */
    #define list_for_each_safe(pos, n, head) \
    	for (pos = (head)->next, n = pos->next; pos != (head); \
    		pos = n, n = pos->next)

       功能:也是遍历链表函数,只不过如果我们在遍历的过程中涉及到节点的删除操作,则需要使用这个函数,从这个函数中也可以发现,有了一个中间节点 n 作为临时存储区,这也契合了 函数名中 safe的含义,更加安全。

    15、list_for_each_entry 宏函数

      原型:

    /**
     * list_for_each_entry	-	iterate over list of given type
     * @pos:	the type * to use as a loop cursor.//用作循环遍历的 游标指针(临时指针)
     * @head:	the head for your list.            //我们自己的链表 头 head
     * @member:	the name of the list_struct within the struct. // 链表结构体的 元素,一般就是
     *                                                         那个struct list_head 的指针元素
     */
    #define list_for_each_entry(pos, head, member)				\
    	for (pos = list_entry((head)->next, typeof(*pos), member);	\
    	     &pos->member != (head); 	\
    	     pos = list_entry(pos->member.next, typeof(*pos), member))

     功能: 通过给定类型(member) 遍历链表,通常用于遍历查找某个节点,这个给定类型member就是我们自定义的链表结构中的struct list_head list 元素,这个函数对于遍历链表,尤其是自定义数据链表结构的遍历,非常方便。

     我们来分析一下这个for循环体的实现原理:

     ①  

    pos = list_entry((head)->next, typeof(*pos), member);
    
    其中:(head)->next    :  链表头head的next元素,指向了整个链表的 第一个含数据的有效 节点。
          typeof(*pos)   : 获取 *pos 的数据类型。这个一般是我们自定义的数据结构。
          member         : 我们自定义的数据结构 member元素,一般就是那个 struct head_list 类型元素
    
          list_entry     : 通过结构体中的 member 的地址计算出该链表节点的地址。
    
    所以该条命令是:获取 链表节点地址,然后赋值给 pos

    ② 

    pos->member != (head); 	//判断该节点 是否是 链表头节点head,这是遍历for循环中的条件判断部分,
                            //由于链表是双链表循环结构,如果pos->member == head, 说明已经遍历到最
                            //后,或者该链表为空

     ③

    pos = list_entry(pos->member.next, typeof(*pos), member))  
    
    这里的方式跟①中一样,只不过取的 pos->member.next,也就是更新pos为当前节点的下一个节点,
    到这里我们第一次感受到了struct list_head 数据结构的设计巧妙,可以很方便(尽管理解起来难)
    的找到任意一个节点。

    16、list_for_each_entry 宏函数的使用示例

         前面讲解了list_for_each_entry 宏函数功能(遍历查找)以及实现原理,但是怎么用,还是会有点抽象,下面我们来用代码举例:

    typedef struct usrList
    {
    	int index;
    	int data;
        struct list_head list;
    } USR_LIST_TYPE;
    
    int main(int argc, char *argv[]) {
    
    	USR_LIST_TYPE msg, *pmsg;
    	LIST_HEAD(msg_head);
    	int *ptr = &msg.data;
    	int i;
    
    	/* insert the 10 msgs */
    	for(i = 0; i < 10; i++){
    		pmsg = (USR_LIST_TYPE *)malloc(sizeof(USR_LIST_TYPE));
    	
    		pmsg->index = i + 1;
    		pmsg->data =  (i + 1)*10;
    		list_add_tail(&pmsg->list, &msg_head);
    	}
    	/* 根据list 遍历 整个链表,并打印信息 */
    	list_for_each_entry(pmsg, &msg_head, list){
    		printf("msg index:%d  data:%d\n", pmsg->index, pmsg->data);
    	}
    
    	return 0;
    }
    

     运行结果如下:

    msg index:1  data:10
    msg index:2  data:20
    msg index:3  data:30
    msg index:4  data:40
    msg index:5  data:50
    msg index:6  data:60
    msg index:7  data:70
    msg index:8  data:80
    msg index:9  data:90
    msg index:10  data:100

    17、list_for_each_entry_safe函数

    原型:

    /**
     * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
     * @pos:	the type * to use as a loop cursor.
     * @n:		another type * to use as temporary storage
     * @head:	the head for your list.
     * @member:	the name of the list_struct within the struct.
     */
    #define list_for_each_entry_safe(pos, n, head, member)			\
    	for (pos = list_entry((head)->next, typeof(*pos), member),	\
    		n = list_entry(pos->member.next, typeof(*pos), member);	\
    	     &pos->member != (head); 					\
    	     pos = n, n = list_entry(n->member.next, typeof(*n), member))

      功能:list_for_each_entry的安全版,当遍历过程中涉及到 删除节点的时候,使用该宏函数。

    18、list_for_each_entry_reverse 函数

    原型:

    /**
     * list_for_each_entry_reverse - iterate backwards over list of given type.
     * @pos:	the type * to use as a loop cursor.
     * @head:	the head for your list.
     * @member:	the name of the list_struct within the struct.
     */
    #define list_for_each_entry_reverse(pos, head, member)			\
    	for (pos = list_entry((head)->prev, typeof(*pos), member);	\
    	     &pos->member != (head); 	\
    	     pos = list_entry(pos->member.prev, typeof(*pos), member))

     功能:反向遍历整个链表。

    19、其他

       双向链表的其他接口参考源码list.h

    二、单向链表接口函数及相关宏定义

        通过对双向链表的学习,我们了解了链表的相关操作,双向链表功能比较全,但是也有一点点缺点,就是每个链表节点都包含2个 方向指针,所以如果可以定义一种单向链表,对于内存来讲,不仅能够节省内存,而且对于一些简单的结构,遍历的效率也会更高,,这里参考阿里云IOT- C SDK中单向链表的 实现方式,就不一一的解释了,毕竟能够理解双向链表,再去看单向链表,就很简单了。该链表结构是单向不循环数据结构,如下图所示:

    代码如下:

    /* for single link list */
    typedef struct slist_s {
        struct slist_s *next;
    } slist_t;                
    
    static inline void slist_add(slist_t *node, slist_t *head)
    {
        node->next = head->next;
        head->next = node;
    }
    
    static inline void slist_add_tail(slist_t *node, slist_t *head)
    {
        while (head->next) {
            head = head->next;
        }
    
        slist_add(node, head);
    }
    
    static inline void slist_del(slist_t *node, slist_t *head)
    {
        while (head->next) {
            if (head->next == node) {
                head->next = node->next;
                break;
            }
    
            head = head->next;
        }
    }
    
    static inline int slist_empty(const slist_t *head)
    {
        return !head->next;
    }
    
    static inline void slist_init(slist_t *head)
    {
        head->next = 0;
    }
    
    /*
    * Iterate over list of given type.
    *
    * @param[in]   queue   he head for your list.
    * @param[in]   node    the type * to use as a loop cursor.
    * @param[in]   type    the type of the struct this is embedded in.
    * @param[in]   member  the name of the slist_t within the struct.
    */
    #define slist_for_each_entry(queue, node, type, member)        \
        for (node = container_of((queue)->next, type, member); \
             &node->member;                                        \
             node = container_of(node->member.next, type, member))
    
    /*
     * Iterate over list of given type safe against removal of list entry.
     *
     * @param[in]   queue   the head for your list.
     * @param[in]   tmp     the type * to use as a temp.
     * @param[in]   node    the type * to use as a loop cursor.
     * @param[in]   type    the type of the struct this is embedded in.
     * @param[in]   member  the name of the slist_t within the struct.
     */
    #define slist_for_each_entry_safe(queue, tmp, node, type, member) \
        for (node = container_of((queue)->next, type, member),    \
             tmp = (queue)->next ? (queue)->next->next : NULL;        \
             &node->member;                                           \
             node = container_of(tmp, type, member), tmp = tmp ? tmp->next : tmp)
    
    /*
     * Initialise the list.
     *
     * @param[in]   name    the list to be initialized.
     */
    #define SLIST_HEAD_INIT(name) {0}
    
    /*
     * Initialise the list.
     *
     * @param[in]   name    the list to be initialized.
     */
    #define SLIST_HEAD(name) \
        slist_t name = SLIST_HEAD_INIT(name)
    
    /*
     * Get the struct for this entry.
     * @param[in]   addr     the list head to take the element from.
     * @param[in]   type     the type of the struct this is embedded in.
     * @param[in]   member   the name of the slist_t within the struct.
     */
    #define slist_entry(addr, type, member) (                                   \
            addr ? (type *)((long)addr - offsetof(type, member)) : (type *)addr \
                                            )
    
    /*
    * Get the first element from a list.
    *
    * @param[in]   ptr     the list head to take the element from.
    * @param[in]   type    the type of the struct this is embedded in.
    * @param[in]   member  the name of the slist_t within the struct.
    */
    #define slist_first_entry(ptr, type, member) \
        slist_entry((ptr)->next, type, member)
    
    /*
     * Get the list length.
     *
     * @param[in]   queue    the head for your list.
     */
    static inline int slist_entry_number(slist_t *queue)
    {
        int num;
        slist_t *cur = queue;
        for (num = 0; cur->next; cur = cur->next, num++)
            ;
    
        return num;
    }

    三、双向链表综合应用案例-增、减、删、清空操作

    示例代码如下:

    typedef struct usrList
    {
    	int index;
    	int data;
        struct list_head list;
    } USR_LIST_TYPE;
    
    int main(int argc, char *argv[]) {
    
    	USR_LIST_TYPE msg, *pmsg, *pos,*n;
    	//struct list_head *pos, *n;   //用于遍历 临时用
    	LIST_HEAD(msg_head);
    	int *ptr = &msg.data;
    	int i;
    
    	/* insert the 10 msgs 插入10个节点 */
    	printf("*** now,we will insert 10 msgs into list ******\n");
    
    	for(i = 0; i < 10; i++){
    		pmsg = (USR_LIST_TYPE *)malloc(sizeof(USR_LIST_TYPE));
    	
    		pmsg->index = i + 1;
    		pmsg->data =  (i + 1)*10;
    		list_add_tail(&pmsg->list, &msg_head);
    	}
    	printf("*** print the list ****************************\n");
    	list_for_each_entry(pmsg, &msg_head, list){
    		printf("msg index:%d  data:%d\n", pmsg->index, pmsg->data);
    	}
    
    	/* modify the index:5 node,and data is 55, 修改某个节点*/
    	printf("*** now,we will modify the index=5 msg ********\n");
    	list_for_each_entry(pmsg, &msg_head, list){
    		if(pmsg->index == 5){
    			pmsg->data = 55;
    			break;
    		}
    	}
    	//print all the list
    	printf("*** print the list ****************************\n");
    	list_for_each_entry(pmsg, &msg_head, list){
    		printf("msg index:%d  data:%d\n", pmsg->index, pmsg->data);
    	}
        
        //删除某个节点
    	printf("*** now,we will delete the index=5 msg ********\n");
    	list_for_each_entry_safe(pos,n, &msg_head, list){
    		if(pos->index == 5){
    			list_del(&(pos->list));
    			free(pos);
    			break;
    		}
    	}
    	printf("*** print the list ****************************\n");
    	list_for_each_entry(pmsg, &msg_head, list){
    		printf("msg index:%d  data:%d\n", pmsg->index, pmsg->data);
    	}
    	/* 使用list_for_each_safe 进行删除节点操作
    	list_for_each_safe(pos, n, &msg_head){
    			pmsg = list_entry(pos, USR_LIST_TYPE, list);  //获取节点指针
    			if(pmsg->index == 5){
    				list_del(pos);
    				free(pmsg);						//务必释放该节点所占的物理内存
    				break;
    			}
    	}
    	printf("*** print the list ****************************\n");
    	list_for_each_entry(pmsg, &msg_head, list){
    		printf("msg index:%d  data:%d\n", pmsg->index, pmsg->data);
    	}
    	*/
        
        //删除全部节点
    	printf("*** now,we will delete all msg ********\n");
    	list_for_each_entry_safe(pos, n, &msg_head, list){
    		list_del(&(pos->list));
    		free(pos);
    	}
        //判断链表是否为空
    	if(list_empty(&msg_head))
    		printf("the list is empty.\n");
    	else printf("the list is not empty.\n");
    
    	return 0;
    }
    

    运行结果如下:

    *** now,we will insert 10 msgs into list ******
    *** print the list ****************************
    msg index:1  data:10
    msg index:2  data:20
    msg index:3  data:30
    msg index:4  data:40
    msg index:5  data:50
    msg index:6  data:60
    msg index:7  data:70
    msg index:8  data:80
    msg index:9  data:90
    msg index:10  data:100
    *** now,we will modify the index=5 msg ********
    *** print the list ****************************
    msg index:1  data:10
    msg index:2  data:20
    msg index:3  data:30
    msg index:4  data:40
    msg index:5  data:55
    msg index:6  data:60
    msg index:7  data:70
    msg index:8  data:80
    msg index:9  data:90
    msg index:10  data:100
    *** now,we will delete the index=5 msg ********
    *** print the list ****************************
    msg index:1  data:10
    msg index:2  data:20
    msg index:3  data:30
    msg index:4  data:40
    msg index:6  data:60
    msg index:7  data:70
    msg index:8  data:80
    msg index:9  data:90
    msg index:10  data:100
    *** now,we will delete all msg ********
    Now,the list is empty.

     

    展开全文
  • 2) 拷贝构造函数List(const List& list),根据一个给定的链表构造当前链表(10分) 3) 析构函数~List(),释放链表中的所有节点(10分) 4) Push_back(T e)函数,往链表最末尾插入一个元素为e的节点(10分) 5...
  • Linux内核中经典链表 list_head 常见使用方法解析

    万次阅读 多人点赞 2018-07-03 17:49:07
    做内核驱动开发经常会使用linux内核最经典的双向链表 list_head, 以及它的拓展接口(或者宏定义): list_add , list_add_tail, list_del , list_entry ,list_for_each , list_for_each_entry ...... 每次看到这些...

          做内核驱动开发经常会使用linux内核最经典的双向链表 list_head, 以及它的拓展接口(或者宏定义): list_add , list_add_tail, list_del , list_entry ,list_for_each , list_for_each_entry ...... 

          每次看到这些接口,感觉都很像,今天专门研究了一下内核,对它们做一些总结,希望为后续开发提供方便。

    首先找到list_head 结构体定义,kernel/inclue/linux/types.h  如下:  

    struct list_head {
    	struct list_head *next, *prev;
    };

           然后就开始围绕这个结构开始构建链表,然后插入、删除节点 ,遍历整个链表等等,其实内核已经提供好了现成的接口,接下来就让我们进入 kernel/include/linux/list.h中:

    一. 创建链表

        内核提供了下面的这些接口来初始化链表:

    #define LIST_HEAD_INIT(name) { &(name), &(name) }
    
    #define LIST_HEAD(name) \
    	struct list_head name = LIST_HEAD_INIT(name)
    
    static inline void INIT_LIST_HEAD(struct list_head *list)
    {
    	WRITE_ONCE(list->next, list);
    	list->prev = list;
    }

    如:  可以通过 LIST_HEAD(mylist) 进行初始化一个链表,mylist的prev 和 next 指针都是指向自己。


       struct list_head mylist = {&mylist,  &mylist} ;   

           但是如果只是利用mylist这样的结构体实现链表就没有什么实际意义了,因为正常的链表都是为了遍历结构体中的其它有意义的字段而创建的,而我们mylist中只有 prev和next指针,却没有实际有意义的字段数据,所以毫无意义。

          综上,我们可以创建一个宿主结构,然后在此结构中再嵌套mylist字段,宿主结构又有其它的字段(进程描述符 task_struct,页面管理的page结构,等就是采用这种方法创建链表的)。为简便理解,定义如下:

    struct  my_task_list {
        int val ;
        struct list_head mylist;
    }

    创建第一个节点

    struct my_task_list first_task = 
    { .val = 1,
      .mylist = LIST_HEAD_INIT(first_task.mylist)
    };

    这样mylist 就prev 和 next指针分别指向mylist自己了,如下图:



    二. 添加节点

    内核已经提供了添加节点的接口了

    1.  list_add 

        如下所示。 根据注释可知,是在链表头head后方插入一个新节点new。

        并且还说了一句:这个接口利用实现堆栈  (why? 稍后再做分析)

    /**
     * list_add - add a new entry
     * @new: new entry to be added
     * @head: list head to add it after
     *
     * Insert a new entry after the specified head.
     * This is good for implementing stacks.
     */
    static inline void list_add(struct list_head *new, struct list_head *head)
    {
    	__list_add(new, head, head->next);
    }

    list_add再调用__list_add接口

    /*
     * Insert a new entry between two known consecutive entries.
     *
     * This is only for internal list manipulation where we know
     * the prev/next entries already!
     */
    static inline void __list_add(struct list_head *new,
    			      struct list_head *prev,
    			      struct list_head *next)
    {
    	if (!__list_add_valid(new, prev, next))
    		return;
    
    	next->prev = new;
    	new->next = next;
    	new->prev = prev;
    	WRITE_ONCE(prev->next, new);
    }

    其实就是在head 链表头后和链表头后第一个节点之间插入一个新节点。然后这个新的节点就变成了链表头后的第一个节点了。

    依然用上面的my_task_list结构体举例子

    首先我们创建一个链表头   header_task 

     LIST_HEAD(header_task);

       

    然后再创建实际的第一个节点

    struct my_task_list my_first_task = 
    { .val = 1,
      .mylist = LIST_HEAD_INIT(my_first_task.mylist)
    };

    接着把这个节点插入到header_task之后

    list_add(&my_first_task.mylist,  &header_task);



    然后在创建第二个节点,同样把它插入到header_task之后

    struct my_task_list my_second_task = 
    { .val = 2,
      .mylist = LIST_HEAD_INIT(my_second_task.mylist)
    };
    其实还可以用另外一个接口 INIT_LIST_HEAD 进行初始化(参数为指针变量), 如下:
    struct my_task_list my_second_task;
    my_second_task.val = 2;
    INIT_LIST_HEAD(&my_second_task.mylist);

    list_add(&my_second_task.mylist, &header_task)


    以此类推,每次插入一个新节点,都是紧靠着header节点,而之前插入的节点依次排序靠后,那最后一个节点则是第一次插入header后的那个节点。最终可得出:先来的节点靠后,而后来的节点靠前,“先进后出,后进先出”。所以此种结构类似于 stack“堆栈”, 而 header_task就类似于内核stack中的栈顶指针esp, 它都是紧靠着最后push到栈的元素。

    2. list_add_tail 接口 

    上面所讲的list_add接口是从链表头header后添加的节点。 同样,内核也提供了从链表尾处向前添加节点的接口list_add_tail. 让我们来看一下它的具体实现。

    /**
     * list_add_tail - add a new entry
     * @new: new entry to be added
     * @head: list head to add it before
     *
     * Insert a new entry before the specified head.
     * This is useful for implementing queues.
     */
    static inline void list_add_tail(struct list_head *new, struct list_head *head)
    {
    	__list_add(new, head->prev, head);
    }

    从注释可得出:(1)在一个特定的链表头前面插入一个节点

    (2)这个方法很适用于队列的实现 (why?)

    进一步把__list_add ()展开如下:

    /*
     * Insert a new entry between two known consecutive entries.
     *
     * This is only for internal list manipulation where we know
     * the prev/next entries already!
     */
    static inline void __list_add(struct list_head *new,
    			      struct list_head *prev,
    			      struct list_head *next)
    {
    	if (!__list_add_valid(new, prev, next))
    		return;
    
    	next->prev = new;
    	new->next = next;
    	new->prev = prev;
    	WRITE_ONCE(prev->next, new);
    }

        所以,很清楚明了, list_add_tail就相当于在链表头前方依次插入新的节点(也可理解为在链表尾部开始插入节点,此时,header节点既是为节点,保持不变)

        利用上面分析list_add接口的方法可画出数据结构图形如下。

    (1)创建一个 链表头(实际上应该是表尾), 同样可调用 LIST_HEAD(header_task);

        


    (2)插入第一个节点 my_first_task.mylist , 调用 list_add_tail(& my_first_task.mylist,  & header_task);

        

    (3) 插入第二个节点my_second_task.mylist,调用list_add_tail(& my_second_task.mylist,  &header_task);



    依此类推,每次插入的新节点都是紧挨着 header_task表尾,而插入的第一个节点my_first_task排在了第一位,my_second_task排在了第二位,可得出:先插入的节点排在前面,后插入的节点排在后面,“先进先出,后进后出”,这不正是队列的特点吗(First in First out)!

    三. 删除节点

          内核同样在list.h文件中提供了删除节点的接口 list_del(), 让我们看一下它的实现流程

    static inline void list_del(struct list_head *entry)
    {
    	__list_del_entry(entry);
    	entry->next = LIST_POISON1;
    	entry->prev = LIST_POISON2;
    }
    /*
     * Delete a list entry by making the prev/next entries
     * point to each other.
     *
     * This is only for internal list manipulation where we know
     * the prev/next entries already!
     */
    static inline void __list_del(struct list_head * prev, struct list_head * next)
    {
    	next->prev = prev;
    	WRITE_ONCE(prev->next, next);
    }
    
    /**
     * list_del - deletes entry from list.
     * @entry: the element to delete from the list.
     * Note: list_empty() on entry does not return true after this, the entry is
     * in an undefined state.
     */
    static inline void __list_del_entry(struct list_head *entry)
    {
    	if (!__list_del_entry_valid(entry))
    		return;
    
    	__list_del(entry->prev, entry->next);
    }
        利用list_del(struct list_head *entry) 接口就可以删除链表中的任意节点了,但需注意,前提条件是这个节点是已知的,既在链表中真实存在,切prev,next指针都不为NULL。

        

    四. 链表遍历

         内核是同过下面这个宏定义来完成对list_head链表进行遍历的,如下 :

    /**
     * list_for_each	-	iterate over a list
     * @pos:	the &struct list_head to use as a loop cursor.
     * @head:	the head for your list.
     */
    #define list_for_each(pos, head) \
    	for (pos = (head)->next; pos != (head); pos = pos->next)
        上面这种方式是从前向后遍历的,同样也可以使用下面的宏反向遍历:
    /**
     * list_for_each_prev	-	iterate over a list backwards
     * @pos:	the &struct list_head to use as a loop cursor.
     * @head:	the head for your list.
     */
    #define list_for_each_prev(pos, head) \
    	for (pos = (head)->prev; pos != (head); pos = pos->prev)

       而且,list.h 中也提供了list_replace( 节点替换)  list_move(节点移位)  ,翻转,查找等接口,这里就不在一一分析了。

    五. 宿主结构

    1.找出宿主结构  list_entry(ptr, type, member)

        上面的所有操作都是基于list_head这个链表进行的,涉及的结构体也都是:

    struct list_head {
    	struct list_head *next, *prev;
    };

            其实,正如文章一开始所说,我们真正更关心的是包含list_head这个结构体字段的宿主结构体,因为只有定位到了宿主结构体的起始地址,我们才能对对宿主结构体中的其它有意义的字段进行操作。

    struct  my_task_list {
        int val ;
        struct list_head mylist;
    }
          那我们如何根据mylist这个字段的地址而找到宿主结构my_task_list的位置呢???

          做linux驱动开发的同学是不是想到了LDD3这本书中经常使用的一个非常经典的宏定义呢!那就是:

    container_of(ptr, type, member)

        没错就是它,在LDD3这本书中的第三章字符设备驱动,以及第十四章驱动设备模型中多次提到,所以我觉得这个宏应该是内核最经典的宏之一。 那list.h中使用什么接口实现的这个转换功能呢?

    /**
     * list_entry - get the struct for this entry
     * @ptr:	the &struct list_head pointer.
     * @type:	the type of the struct this is embedded in.
     * @member:	the name of the list_head within the struct.
     */
    #define list_entry(ptr, type, member) \
    	container_of(ptr, type, member)
        list.h中提供了list_entry宏来实现对应地址的转换,但最终还是调用了container_of宏,所以container_of宏的伟大之处不言而喻。 那接下来让我们揭开她的面纱:

        此宏在内核代码 kernel/include/linux/kernel.h中定义(此处kernel版本为3.10;新版本4.13之后此宏定义改变,但实现思想保持一致)

    /** 
     * container_of - cast a member of a structure out to the containing structure 
     * @ptr:    the pointer to the member. 
     * @type:   the type of the container struct this is embedded in. 
     * @member: the name of the member within the struct. 
     * 
     */  
    #define container_of(ptr, type, member) ({          \  
        const typeof( ((type *)0)->member ) *__mptr = (ptr); \  
        (type *)( (char *)__mptr - offsetof(type,member) );})  

    而offsetof定义在 kernel/include/linux/stddef.h ,如下:

    #define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)

    看下container_of宏的注释:

    (1)根据结构体重的一个成员变量地址导出包含这个成员变量mem的struct地址。

    (2)参数解释:

             ptr  : 成员变量mem的地址    

            type: 包含成员变量mem的宿主结构体的类型

            member: 在宿主结构中的mem成员变量的名称

            如果用我们之前定义的结构体struct my_task_list举例

    struct  my_task_list {
        int val ;
        struct list_head mylist;
    }
    struct my_task_list first_task = 
    { .val = 1,
      .mylist = LIST_HEAD_INIT(first_task.mylist)
    };

        ptr   :    &first_task.mylist

        type  :  struct my_task_list

        member :  mylist

    而container_of宏的功能就是根据 first_task.mylist字段的地址得出first_task结构的其实地址。

    把上面offsetof的宏定义代入container_of宏中,可得到下面定义:

    #define container_of(ptr, type, member) ({          \  
        const typeof( ((type *)0)->member ) *__mptr = (ptr); \  
        (type *)( (char *)__mptr - ((size_t) &((type *)0)->member) );})  

    再把宏中对应的参数替换成实参:

       const typeof( ((struct my_task_list *)0)->mylist ) *__mptr = (&first_task.mylist); \  
        (struct my_task_list *)( (char *)__mptr - ((size_t) &((struct my_task_list *)0)->mylist) );})  

    typeof 是 GNU对C新增的一个扩展关键字,用于获取一个对象的类型 ,比如这里((struct my_task_list *)0)->mylist 是把0地址强制转换成struct my_task_list 指针类型,然后取出mylist元素。 然后再对mylist元素做typeof操作,其实就是获取 my_task_list结构中mylist字段的数据类型struct list_head,所以这行语句最后转化为:

    const struct list_head *__mptr  = (&first_task.mylist);

    第二条语句中在用 __mptr这个指针 减去 mylist字段在 my_task_list中的偏移(把0地址强制转换成struct my_task_list指针类型,然后取出mylist的地址,此时mylist的地址也是相对于0地址的偏移,所以就是mylist字段相对于宿主结构类型struct my_task_list的偏移) 正好就是宿主结构的起始地址。C语言的灵活性得到了很好的展示!!!


    2. 宿主结构的遍历

            我们可以根据结构体中成员变量的地址找到宿主结构的地址, 并且我们可以对成员变量所建立的链表进行遍历,那我们是不是也可以通过某种方法对宿主结构进行遍历呢?    

            答案肯定是可以的,内核在list.h中提供了下面的宏:

    /**
     * list_for_each_entry	-	iterate over list of given type
     * @pos:	the type * to use as a loop cursor.
     * @head:	the head for your list.
     * @member:	the name of the list_head within the struct.
     */
    #define list_for_each_entry(pos, head, member)				\
    	for (pos = list_first_entry(head, typeof(*pos), member);	\
    	     &pos->member != (head);					\
    	     pos = list_next_entry(pos, member))

     其中,list_first_entry 和  list_next_entry宏都定义在list.h中,分别代表:获取第一个真正的宿主结构的地址; 获取下一个宿主结构的地址。它们的实现都是利用list_entry宏。

    /**
     * list_first_entry - get the first element from a list
     * @ptr:	the list head to take the element from.
     * @type:	the type of the struct this is embedded in.
     * @member:	the name of the list_head within the struct.
     *
     * Note, that list is expected to be not empty.
     */
    #define list_first_entry(ptr, type, member) \
    	list_entry((ptr)->next, type, member)
    
    /**
     * list_next_entry - get the next element in list
     * @pos:	the type * to cursor
     * @member:	the name of the list_head within the struct.
     */
    #define list_next_entry(pos, member) \
    	list_entry((pos)->member.next, typeof(*(pos)), member)

    最终实现了宿主结构的遍历

    #define list_for_each_entry(pos, head, member)				\
    	for (pos = list_first_entry(head, typeof(*pos), member);	\
    	     &pos->member != (head);					\
    	     pos = list_next_entry(pos, member))
     首先pos定位到第一个宿主结构地址,然后循环获取下一个宿主结构地址,如果查到宿主结构中的member成员变量(宿主结构中struct list_head定义的字段)地址为head,则退出,从而实现了宿主结构的遍历。如果要循环对宿主结构中的其它成员变量进行操作,这个遍历操作就显得特别有意义了。

            我们用上面的 my_task_list结构举个例子:

    struct my_task_list *pos_ptr = NULL ; 
    list_for_each_entry (pos_ptr, & header_task, mylist ) 
        { 
             printk ("val =  %d\n" , pos_ptr->val); 
        }

        

    参考文档:https://kernelnewbies.org/FAQ/LinkedLists

                    《Understanding linux kernel》

                    《Linux device drivers》

    
                                            
    展开全文
  • 双向循环链表list(C++)

    千次阅读 2016-05-20 17:52:22
    双向循环链表list(C++)

    lists将元素按顺序储存在链表中与向量(vectors)相比, 它允许快速的插入和删除,但是随机访问却比较慢

       list是双向循环链表,每一个元素都知道前面一个元素和后面一个元素。在STL中,list和vector一样,是两个常被使用的容器。和vector不一样的是,list不支持对元素的任意存取。list中提供的成员函数与vector类似,不过list提供对表首元素的操作push_front、pop_front,这是vector不具备的。和vector另一点不同的是,list的迭代器不会存在失效的情况,他不像vector会保留备份空间,在超过容量额度时重新全部分配内存,导致迭代器失效;list没有备份空间的概念,出入一个元素就申请一个元素的空间,所以它的迭代器不会失效。


    assign() 给list赋值 

    back() 返回最后一个元素 

    begin() 返回指向第一个元素的迭代器 

    clear() 删除所有元素 

    empty() 如果list是空的则返回true 

    end() 返回末尾的迭代器 

    erase() 删除一个元素 

    front() 返回第一个元素 

    get_allocator() 返回list的配置器 

    insert() 插入一个元素到list中 

    max_size() 返回list能容纳的最大元素数量 

    merge() 合并两个list 

    pop_back() 删除最后一个元素 

    pop_front() 删除第一个元素 

    push_back() 在list的末尾添加一个元素 

    push_front() 在list的头部添加一个元素 

    rbegin() 返回指向第一个元素的逆向迭代器 

    remove() 从list删除元素 

    remove_if() 按指定条件删除元素 

    rend() 指向list末尾的逆向迭代器 

    resize() 改变list的大小 

    reverse() 把list的元素倒转 

    size() 返回list中的元素个数 

    sort() 给list排序 

    splice() 合并两个list 

    swap() 交换两个list 

    unique() 删除list中重复的元素

     

    实例请参照:http://blog.csdn.net/lskyne/article/details/10418823

    展开全文
  • 深入浅出linux内核源代码之双向链表list_head pdf文档和代码
  • Redis List链表类型详解

    千次阅读 2022-05-03 13:11:27
    作为一种常用的数据结构,链表内置在很多高级的编程语言里面, 因为 Redis 使用的 C 语言没有内置这种数据结构, 所有 Redis 构建了自己的链表实现。 Redis链表节点和链表的实现 typedef struct listNode { // ...
  • C/C++ list链表的理解以及使用

    万次阅读 2021-09-01 16:22:40
    今天我们来一起深入学习一下非常重要以及基础的数据结构——链表(list) 链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(...
  • 双向链表list

    万次阅读 2015-04-23 10:10:47
    //list容器可以在任意位置插入、获取、移动元素,不能通过下标获取元素 #include #include #include #include #include using namespace std; int main() { typedef list LISTINT;//别名 LISTINT lis;//创建...
  • C++ 链表list)使用简述

    千次阅读 2022-03-28 11:29:08
    C++ STL 库的 list 容器是一个双向链表。包含在头文件 <list> 中 1、有关函数的作用 list 本身: list<type> li; 定义一个参数类型为 type 的链表 li.push_back(val) 在尾节点后插入...
  • title: '数据结构——链表List、ArrayList、LinkedList ’ date: 2019-11-16 10:42:41 categories: 数据结构 tags: 数据结构 链表 抽象数据类型ADT 是带有一组操作的一些对象的集合 一种特别的抽象类型——表...
  • 众所周知,在链表上进行插入操作所需要的时间为固定时间,只需要修改几个指针便可以完成插入操作,C++ 的STL为我们提供了list容器,当然也少不了合并两个list的方法,不是使用merge,而是使用list的方法splice,函数...
  • linux内核提供了一个经典通用的双向循环链表list的实现,任何模块都可以借助该接口实现自己的内部循环链表。因为是通用的,可以直接移植到用户态中使用,下面介绍相关的接口与一个简单操作例子,包括链表的插入、...
  • 为了代码简介高效,可以方便的被多个链表连接起来,而且这个链表可以很方便的被各种不同类型数据域复用,我们实现单双链表时候(链表节点中不需要数据域),可以像下面这样子: typedef struct List { struct ...
  • QT代码实现list链表结构,资源中包含单向链表和双向链表
  • 链表和线性表的关系? 链表的分类?是根据什么划分的? 线性表 线性表中数据元素之间的关系是一对一的关系,即除了第一个和最后一个数据元素之外,其它数据元素都是首尾相接的。 线性表分类:顺序存储结构、链.....
  • C语言之list_head双向链表

    千次阅读 2017-09-17 22:42:57
    对于嵌入式开发者来说,双向链表是用的非常多的一种数据结构之一,在linux内核里面有一个叫做list_head的结构体,专门用来做双向链表的种种操作,掌握并理解双向链表以及list_head的实现方式对于嵌入式开发来说是...
  • redis list ( 链表 )

    万次阅读 2018-09-25 17:02:47
    list类型其实就是一个双向链表。通过push,pop操作从链表的头部或者尾部添加删除元素。 这使得list既可以用作栈,也可以用作队列。 上进上出是 栈 ,特点:数据 先进后出 下进上出是 队列,特点:数据 先进先出 ...
  • 双向链表list.h升序排序

    千次阅读 2016-10-20 12:57:37
    前一篇文章《整理一个双向链表list.h》介绍了自实现的双向链表list.h,在Linux内核中,常见的是维护全局链表(如i2c板级有一个全局链表),基本上都是在尾部插入、模块退出时删除,不会涉及到链表中间插入、删除,——...
  • 在《Redis学习笔记》系列的前面几篇文章中,我们分别讲述了Redis的几种常用数据结构(分别是string、hash、list、set、zset)和事务处理。在接下来的文章中,我们就要深入到Redis的源码层,了解Red...
  • 链表(Linked list)是一种常见的基础数据结构,是一种线性表,但是并不会按线性的顺序存储数据,而是在每一个节点里存到下一个节点的地址。 链表可分为单向链表和双向链表。 基础操作 创建链表 //
  • C++标准模板库之链表list

    千次阅读 2020-01-20 12:41:28
    List 链表数据插入速度快
  • List是每个节点包含前驱指针、后继指针和数据域三个部分的双向链表List不提供随机存取,访问元素需要按顺序走到需存取的元素,时间复杂度为O(n),在list的任何位置上执行插入或删除操作都非常迅速,只需在list内部...
  • Linux内核链表list_entry解析

    千次阅读 2018-01-07 21:23:39
    链表是一些包含数据的独立数据结构的集合,链表中的每一个节点通过链或者指针连接在一起。程序通过指针访问链表中的节点。链表一般分为单链表和双链表。 1.单链表 单链表中,每个节点包含指向下一个节点的指针。...
  • linked-list C for single linked list and double linked list single_list 结点结构体 创建结点 创建链表 显示链表的数据 获取链表长度 插入结点 删除结点 查找链表中指定的数据 修改链表中指定位置结点的值 修改...
  • pythonlist是数组还是链表实现的-数组和链表结构(python)-1 数组和链表.pdf
  • 1. 双向链表应用实例 双向链表的操作分析和实现 使用带 head 头的双向链表实现------水浒英雄排行榜 管理单向链表的缺点分析 单向链表,查找的方向只能是一个方向,而双向链表可以向前或者向后查找。 单向链表...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 499,572
精华内容 199,828
关键字:

链表list

友情链接: 9ActiveX.rar