Manipulating Linked Lists
A family of functions is provided to manipulate linked lists. They all take pointers to one or more list_head structures. The functions are implemented as inlines in generic C and can be found in <linux/list.h>.
Interestingly, all these functions are O(1). This means they execute in constant time, regardless of the size of the list or any other inputs. For example, it takes the same amount of time to add or remove an entry to or from a list whether that list has 3 or 3,000 entries. This is perhaps not surprising, but still good to know.
To add a node to a linked list:
list_add(struct list_head *new, struct list_head *head)
This function adds the new node to the given list immediately after the head node. Because the list is circular and generally has no concept of first or last nodes, you can pass any element for head. If you do pass the "last" element, however, this function can be used to implement a stack.
To add a node to the end of a linked list:
list_add_tail(struct list_head *new, struct list_head *head)
This function adds the new node to the given list immediately before the head node. As with list_add(), because the lists are circular you can generally pass any element for head. This function can be used to implement a queue, however, if you do indeed pass the "first" element.
To delete a node from a linked list,
list_del(struct list_head *entry)
This function removes the element entry from the list. Note, it does not free any memory belonging to enTRy or the data structure in which it is embedded; this function merely removes the element from the list. After calling this, you would typically destroy your data structure and the list_head inside it.
To delete a node from a linked list and reinitialize it,
list_del_init(struct list_head *entry)
This function is the same as list_del(), except it also reinitializes the given list_head with the rationale that you no longer want the entry in the list, but you can reuse the data structure itself.
To move a node from one list to another,
list_move(struct list_head *list, struct list_head *head)
To move a node from one list to the end of another,
list_move_tail(struct list_head *list, struct list_head *head)
To check if a list is empty,
list_empty(struct list_head *head)
To splice two unconnected list together:
list_splice(struct list_head *list, struct list_head *head)
To splice two unconnected lists together and reinitialize the old list,
list_splice_init(struct list_head *list, struct list_head *head)