Linux双向链表(三)——基础操作拓展拆分与捻接

古城微笑少年丶 2022-09-18 13:47 42阅读 0赞

## 双向链表基础操作拓展 ##

在[第一篇博文][Link 1]当中讨论的链表操作，是基础的增，删，改！而在本博文当中，将要拓展基础操作——链表的拆分与重组，废话少说，开干！(+)\_(+)

### 1、左向移动结点 ###

static inline void list_rotate_left(struct list_head *head)
    {
    	struct list_head *first;
    
    	if (!list_empty(head)) {
    		first = head->next;
    		list_move_tail(first, head);
    	}
    }

![SouthEast][]

用途：即从头->尾场景，比如轮转法操作链表。出队->操作->入队。如果链表有序，通过此操作，循环一定次数，能做到对链表的逆序

### 2、链表分割成两个——内部函数 ###

static inline void __list_cut_position(struct list_head *list,
    		struct list_head *head, struct list_head *entry)
    {
    	struct list_head *new_first = entry->next;
    	list->next = head->next;
    	list->next->prev = list;
    	list->prev = entry;
    	entry->next = list;
    	head->next = new_first;
    	new_first->prev = head;
    }

功能：将head之后到entry（包含entry）所有结点，转移到list链表中去

![SouthEast 1][]

注意：内部函数只提供基本操作功能，不提供安全机制，安全机制封装到外部函数中。见下文

### 3、链表分割成两个——外部函数 ###

/**
     * list_cut_position - cut a list into two
     * @list: a new list to add all removed entries
     * @head: a list with entries
     * @entry: an entry within head, could be the head itself
     *	and if so we won't cut the list
     *
     * This helper moves the initial part of @head, up to and
     * including @entry, from @head to @list. You should
     * pass on @entry an element you know is on @head. @list
     * should be an empty list or a list you do not care about
     * losing its data.
     *
     */
    static inline void list_cut_position(struct list_head *list,
    		struct list_head *head, struct list_head *entry)
    {
    	if (list_empty(head))
    		return;
    	if (list_is_singular(head) &&
    		(head->next != entry && head != entry))
    		return;
    	if (entry == head)
    		INIT_LIST_HEAD(list);
    	else
    		__list_cut_position(list, head, entry);
    }

很明显它是对内部函数的封装，增加安全机制——链表空，单个元素链表时entry不是head也不是head的next元素都不能执行。如果head和entry一致，则list初始化为空。否则，执行分割函数。

### 4、链表捻接——内部函数 ###

static inline void __list_splice(const struct list_head *list,
    				 struct list_head *prev,
    				 struct list_head *next)
    {
    	struct list_head *first = list->next;
    	struct list_head *last = list->prev;
    
    	first->prev = prev;
    	prev->next = first;
    
    	last->next = next;
    	next->prev = last;
    }

![SouthEast 2][]

### 5、链表捻接——外部函数     ###

/**
     * list_splice - join two lists, this is designed for stacks
     * @list: the new list to add.
     * @head: the place to add it in the first list.
     */
    static inline void list_splice(const struct list_head *list,
    				struct list_head *head)
    {
    	if (!list_empty(list))
    		__list_splice(list, head, head->next);
    }

![SouthEast 3][]

/**
     * list_splice_tail - join two lists, each list being a queue
     * @list: the new list to add.
     * @head: the place to add it in the first list.
     */
    static inline void list_splice_tail(struct list_head *list,
    				struct list_head *head)
    {
    	if (!list_empty(list))
    		__list_splice(list, head->prev, head);
    }

![SouthEast 4][]

/**
     * list_splice_init - join two lists and reinitialise the emptied list.
     * @list: the new list to add.
     * @head: the place to add it in the first list.
     *
     * The list at @list is reinitialised
     */
    static inline void list_splice_init(struct list_head *list,
    				    struct list_head *head)
    {
    	if (!list_empty(list)) {
    		__list_splice(list, head, head->next);
    		INIT_LIST_HEAD(list);
    	}
    }

![SouthEast 5][]

看到这里，你就会明白为什么上面三个函数没有重新初始化list了。

/**
     * list_splice_tail_init - join two lists and reinitialise the emptied list
     * @list: the new list to add.
     * @head: the place to add it in the first list.
     *
     * Each of the lists is a queue.
     * The list at @list is reinitialised
     */
    static inline void list_splice_tail_init(struct list_head *list,
    					 struct list_head *head)
    {
    	if (!list_empty(list)) {
    		__list_splice(list, head->prev, head);
    		INIT_LIST_HEAD(list);
    	}
    }

![SouthEast 6][]

>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>声明<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<

>>     知识要传播，劳动要尊重! 受益于开源，回馈于社会! 大家共参与，服务全人类!

>>     本博文由my\_live\_123原创(http://blog.csdn.net/cwcmcw)，转载请注明出处!

>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>^\_^<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<

[Link 1]: http://blog.csdn.net/cwcmcw/article/details/16966401
[SouthEast]: /images/20220828/59c3b4798dec4209ae4f3c62cc5bd2fb.png
[SouthEast 1]: /images/20220828/02906dac155a4a06910424de1c54acc0.png
[SouthEast 2]: /images/20220828/c826d2c240ec48f6b660abd02bc8a9a9.png
[SouthEast 3]: /images/20220828/bfae946fb02b4477a91bc3238402c678.png
[SouthEast 4]: /images/20220828/0e18c3507f194b8c8442e7316e7b88d4.png
[SouthEast 5]: /images/20220828/b4b8b7c1be89427e9a83791e193a0cfa.png
[SouthEast 6]: /images/20220828/7c3b3aaa327746eab8fbb64b96b5753e.png