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

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

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

双向链表基础操作拓展

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

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);}
}

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

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链表中去

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

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;
}

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);
}

/*** 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);
}

/*** 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);}
}

看到这里，你就会明白为什么上面三个函数没有重新初始化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);}
}

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

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

>>     本博文由my_live_123原创()，转载请注明出处!   

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