Linked lists are a very frequently used data structure in the linux kernel and to make the programming easier the linux kernel provides an easy of creating the linked lists. Using the inbuilt method available in the kernel we can create circular doubly linked lists easily and use them in which ever required in the code.
To be able to use this feature available in the kernel we need to add the header file linux/list.h. The structure that is used for creation of the list"list_head" defined in types.h
To use this structure for creation of a linked list we need to include the structure as a member of the main structure of which we want to create the list. For example to create a linked list called k_list in which we will create a list of numbers we will have to create the structure as
In the above structure "temp" is the real data that we want to store and test_list, which is a structure of the kind "list_head" will be used for the creation of the link list.
Then we will need to create a head for the linked list which will be used start the creation of the list. To create a head we can make use of th macro INIT_LIST_HEAD, which will declared and initialize the list at runtime, or we can use the function LIST_HEAD to initialize the list at compile time.
Once list has been created we can add nodes to the linked list using the function
Let us say we want to add create a linked list of three nodes of the kind k_list structure shown above. let us first create three structures and populate it with data that we want to store in it.
Thus we have created three structures "one","two" and "three" of kind k_list in which we have stored data "10","20", and "30" respectively.
Now to form a linked list of these three structures using lines_add
The first argument to list_add is the pointed to the structure of kind list_head which is a member of k_list and the second argument is a pointer to the head node initialized using INIT_LIST_HEAD.
To traverse through the linked list we can make use of another function available in the kernel
In our example we can use this function as
Where ptr is
Now as we traverse through the list we need to be able to access the data that we have stored in the structure k_list. To be able to ge a pointer to the k_list structures through the pointer to the nodes we can make use of the function
Note: This structure works similar to the function "container_of"
Thus in the example above to get a pointer of kind k_list using the pointer "ptr" we need to use the function as
Where entry is
Putting all the above pieces of code into one module we can test the functions related to the creation of linked list in kernel.
create_list.c
Makefile required to compile the module
To see the output first compile the module using
Insert it into the kernel
To see the output
We can see in the output of dmesg that we have been able to traverse the list using list_for_each successfully.