Linux Device Driver Tutorial Part 17 – Linked List in Linux Kernel Part 1

This is the Series on Linux Device Driver. The aim of this series is to provide the easy and practical examples that anyone can understand. In our previous tutorials we have seen  work queue. So this is the Linux Device Driver Tutorial Part 17 – Linked List in Linux Kernel Part 1.

Linux Device Driver Tutorial Part 17 – Linked List in Linux Kernel

Introduction about Linked List

A linked list is a data structure that consists of sequence of nodes. Each node is composed of two fields: data field and reference field which is a pointer that points to the next node in the sequence.

linked-list-1 Linux Device Driver Tutorial Part 17 - Linked List in Linux Kernel Part 1

Each node in the list is also called an element. A head pointer is used to track the first element in the linked list, therefore, it always points to the first element.

The elements do not necessarily occupy contiguous regions in memory and thus need to be linked together (each element in the list contains a pointer to the next element).

Advantages of Linked Lists

  • They are a dynamic in nature which allocates the memory when required.
  • Insertion and deletion operations can be easily implemented.
  • Stacks and queues can be easily executed.
  • Linked List reduces the access time.

Disadvantages of Linked Lists

  • The memory is wasted as pointers require extra memory for storage.
  • No element can be accessed randomly; it has to access each node sequentially.
  • Reverse Traversing is difficult in linked list.

Applications of Linked Lists

  • Linked lists are used to implement stacks, queues, graphs, etc.
  • Unlike array, In Linked Lists we don’t need to know the size in advance.

Types of Linked Lists

There are three types of linked lists.

  • Singly Linked List
  • Doubly Linked List
  • Circular Linked List

I’m not going to discuss about its types. Let’s get into the Linked List in Linux kernel.

Linked List in Linux Kernel

Linked list is a very important data structure which allows large number of storage with efficient manipulation on data. Most of the kernel code has been written with help of this data structure. So in Linux kernel no need to implement our own Linked List or no need to use 3rd party library. It has built in Linked List which is Doubly Linked List. It is defined in defined in /lib/modules/$(uname -r)/build/include/linux/list.h.

Normally we used to declared linked list as like below snippet.

But if want to Implement in Linux, then you could write like below snippet.

Where struct list_head is declared in list.h.

Initialize Linked List Head

Before creating any node in linked list, we should create linked list’s head node first. So below macro is used to create a head node.

LIST_HEAD(linked_list);

This macro will create the head node structure in the name of “linked_list” and it will initialize that to its own address.

For example,

I’m going to create head node in the name of “etx_linked_list”.

LIST_HEAD(etx_linked_list);

Let’s see how internally it handles this. The macro is defined like below in list.h.

So it will create like below.

While creating head node, it initializes the prev and next pointer to its own address. Which means that prev and next pointer points to itself. The node is empty If the node’s prev and next pointer points to itself.

Create Node in Linked List

You have to create your linked list node dynamically or statically. Your linked list node should have member defined in struct list_head. Using below inline function, we can initialize that struct list_head.

INIT_LIST_HEAD(struct list_head *list);

For Example, My node is like this.

So we have to initialize the list_head variable using INIT_LIST_HEAD inline function.

Add Node to Linked List

Add after Head Node

After created that node, we need to add that node to the linked list. So we can use this inline function to do that.

inline void list_add(struct list_head *new, struct list_head *head);

Insert a new entry after the specified head. This is good for implementing stacks.

Where,

struct list_head * new – new entry to be added

struct list_head * head – list head to add it after

For Example,

Add before Head Node

Insert a new entry before the specified head. This is useful for implementing queues.

inline void list_add_tail(struct list_head *new, struct list_head *head);

Where,

struct list_head * new – new entry to be added

struct list_head * head – list head to add before the head

For Example,

Delete Node from Linked List

list_del

It will delete the entry node from the list. This function removes the entry node from the linked list by disconnect prev and next pointers from the list, but it doesn’t free any memory space allocated for entry node.

inline void list_del(struct list_head *entry);

Where,

struct list_head * entry– the element to delete from the list.

list_del_init

It will delete the entry node from the list and reinitialize it. This function removes the entry node from the linked list by disconnect prev and next pointers from the list, but it doesn’t free any memory space allocated for entry node.

inline void list_del_init(struct list_head *entry);

Where,

struct list_head * entry– the element to delete from the list.

Replace Node in Linked List

list_replace

This function is used to replace the old node with new node.

inline void list_replace(struct list_head *old, struct list_head *new);

Where,

struct list_head * old– the element to be replaced

struct list_head * new– the new element to insert

If old was empty, it will be overwritten.

list_replace_init

This function is used to replace the old node with new node and reinitialize the old entry.

inline void list_replace_init(struct list_head *old, struct list_head *new);

Where,

struct list_head * old– the element to be replaced

struct list_head * new– the new element to insert

If old was empty, it will be overwritten.

Moving Node in Linked List

list_move

This will delete one list from the linked list and again adds to after the head node.

inline void list_move(struct list_head *list, struct list_head *head);

Where,

struct list_head * list – the entry to move

struct list_head * head– the head that will precede our entry

list_move_tail

This will delete one list from the linked list and again adds to before the head node.

inline void list_move_tail(struct list_head *list, struct list_head *head);

Where,

struct list_head * list – the entry to move

struct list_head * head– the head that will precede our entry

Rotate Node in Linked List

This will rotate the list to the left.

inline void list_rotate_left(struct list_head *head);

Where,

head – the head of the list

Test the Linked List Entry

list_is_last

This tests whether list is the last entry in list head.

inline int list_is_last(const struct list_head *list, const struct list_head *head);

Where,

const struct list_head * list – the entry to test

const struct list_head * head – the head of the list

It returns 1 if it is last entry otherwise 0.

list_empty

It tests whether a list is empty or not.

inline int list_empty(const struct list_head *head);

Where,

const struct list_head * head – the head of the list

It returns 1 if it is empty otherwise 0.

list_is_singular

This will tests whether a list has just one entry.

inline int list_is_singular(const struct list_head *head);

Where,

const struct list_head * head – the head of the list

It returns 1 if it has only one entry otherwise 0.

Split Linked List into two part

This cut a list into two.

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 headlist should be an empty list or a list you do not care about losing its data.

inline void list_cut_position(struct list_head *list, struct list_head *head, struct list_head *entry);

Where,

struct list_head * list – a new list to add all removed entries

struct list_head * head– a list with entries

struct list_head * entry– an entry within head, could be the head itself and if so we won’t cut the list

Join Two Linked Lists

 This will join two lists, this is designed for stacks.

inline void list_splice(const struct list_head *list, struct list_head *head);

Where,

const struct list_head * list – the new list to add.

struct list_head * head – the place to add it in the first list.

Traverse Linked List

list_entry

 This macro is used to get the struct for this entry.

list_entry(ptr, type, member);

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.

list_for_each

This macro used to iterate over a list.

list_for_each(pos, head);

pos –  the &struct list_head to use as a loop cursor.

head –  the head for your list.

So using those above two macros, we can traverse the linked list. We will see the example in next tutorial. We can also use these below methods also.

list_for_each_entry

This is used to iterate over list of given type.

list_for_each_entry(pos, head, member);

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.

list_for_each_entry_safe

This will iterate over list of given type safe against removal of list entry.

list_for_each_entry_safe ( pos, n, head, member);

Where,

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_head within the struct.

We can also traverse the linked list in reverse side also using below macros.

list_for_each_prev

This will used to iterate over a list backwards.

list_for_each_prev(pos, head);

pos – the &struct list_head to use as a loop cursor.

head – the head for your list.

list_for_each_entry_reverse

This macro used to iterate backwards over list of given type.

list_for_each_entry_reverse(pos, head, member);

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.

So, We have gone through all the functions which is useful for Kernel Linked List. Please go through the next tutorial (Part 2) for Linked List sample program .

Download our new Android app. You can learn all Embedded Tutorials from your Android Phone easily.

Click Here to Download App!