Linked List : Delete at Specific Position

  • In this program, you are going to learn

  • How to delete the element at position ?

Topics in this section,

  • In this example, we are going to delete the elements in any position.

  • Add the list of header files to refer the APIs used in this program.

#include <linux/init.h>
#include <linux/module.h>
#include <linux/kernel.h>
#include <linux/list.h>
#include <linux/slab.h>

  • Add the modules macro which lists the information about the license, author and description.

MODULE_LICENSE("GPL");
MODULE_AUTHOR("linux_usr");
MODULE_DESCRIPTION("Linked List");

  • list_head is used to initialize the list.

static struct list_head my_list;

  • INIT_LIST_HEAD is used to initialize a list_head structure.

INIT_LIST_HEAD(&my_list);

INIT_LIST_HEAD(&new_node->list);

  • Add the module init function to execute the function once when the module is loaded to the linux kernel.

static int __init linkedlist_init(void)
{
        INIT_LIST_HEAD(&my_list);

        insert_func(2);
        insert_func(3);
        insert_func(4);
        insert_func(6);

        pr_info("Linked list after insertion : \n");
        display();

        delete_at_pos_ition(3);

        pr_info("Linked list after deleting at specific position : \n");
        display();

        pr_info("Driver loaded\n");

        return 0;
}

  • Add module exit function which is executed once the module is unloaded from the kernel.

static void __exit linkedlist_exit(void)
{
    struct list_node *ptr, *next;

    list_for_each_entry_safe(ptr, next, &my_list, list) {
        list_del(&ptr->list);
        kfree(ptr);
    }

    pr_info("Driver unloaded\n");
}

  • insert_func function inserts a new node at the end with the given value into the linked list.

void insert_func(int value)
{
    struct list_node * new_node;

    new_node = kmalloc(sizeof(struct list_node), GFP_KERNEL);

    if (!new_node) {
            pr_err("Memory allocation failed\n");

            return;
    }

    new_node->data = value;
    INIT_LIST_HEAD(&new_node->list);
    list_add_tail(&new_node->list, &my_list);
}

  • delete_at_pos_ function deletes a new node at a position.

void delete_at_pos_ition(int position)
{
    struct list_head * pos;
    int i = 0;
    struct list_node * node;

    if (list_empty(&my_list)) {
            pr_err("List is a empty, cannot delete at position\n");

            return;
    }

    pos = &my_list;
    while (i < position && pos->next != &my_list) {
            pos = pos->next;
            i++;
    }

    if (pos->next == &my_list) {
            pr_err("Position is not found in the list\n");

            return;
    }

    node = list_entry(pos->next, struct list_node, list);
    list_del(&node->list);
    kfree(node);
}

  • display function iterates through the linked list using list_for_each_entry. It prints the data in each node to the kernel log.

void display(void)
{
    struct list_node * ptr;

    pr_info("Linked list: ");
    list_for_each_entry(ptr, &my_list, list) {
            printk(KERN_CONT "%d -> ", ptr->data);
    }

    printk(KERN_CONT "NULL\n");
}

  • Add the module init and exit which is called when the module is loaded and unloaded.

module_init(linkedlist_init);
module_exit(linkedlist_exit);

  1#include <linux/init.h>
  2#include <linux/module.h>
  3#include <linux/kernel.h>
  4#include <linux/list.h>
  5#include <linux/slab.h>
  6
  7MODULE_LICENSE("GPL");
  8MODULE_AUTHOR("linux_usr");
  9MODULE_DESCRIPTION("Linked List");
 10
 11struct list_node {
 12	int data;
 13	struct list_head list;
 14};
 15
 16static struct list_head my_list;
 17
 18void insert_func(int value)
 19{
 20	struct list_node *new_node;
 21
 22	new_node = kmalloc(sizeof(struct list_node), GFP_KERNEL);
 23	
 24	if (!new_node) {
 25		pr_err("Memory allocation failed\n");
 26		return;
 27	}
 28
 29	new_node->data = value;
 30	INIT_LIST_HEAD(&new_node->list);
 31	list_add_tail(&new_node->list, &my_list);
 32}
 33
 34void delete_at_position(int position)
 35{
 36	struct list_head *pos;
 37	int i = 0;
 38	struct list_node *node;
 39
 40	if (list_empty(&my_list)) {
 41		pr_err("List is a empty, cannot delete at position\n");
 42		return;
 43	}
 44
 45	pos = &my_list;
 46	while (i < position && pos->next != &my_list) {
 47		pos = pos->next;
 48		i++;
 49	}
 50
 51	if (pos->next == &my_list) {
 52		pr_err("Position is not found in the list\n");
 53		return;
 54	}
 55
 56	node = list_entry(pos->next, struct list_node, list);
 57	list_del(&node->list);
 58	kfree(node);
 59}
 60
 61
 62void display(void)
 63{
 64	struct list_node *ptr;
 65
 66	pr_info("Linked list: ");
 67	list_for_each_entry(ptr, &my_list, list) {
 68		printk(KERN_CONT "%d -> ", ptr->data);
 69	}
 70
 71	printk(KERN_CONT "NULL\n");
 72}
 73
 74
 75static int __init linkedlist_init(void)
 76{
 77	INIT_LIST_HEAD(&my_list);
 78
 79	insert_func(2);
 80	insert_func(3);
 81	insert_func(4);
 82	insert_func(6);
 83
 84	pr_info("Linked list after insertion : \n");
 85	display();
 86
 87	delete_at_position(3);
 88
 89	pr_info("Linked list after deleting at specific position : \n");
 90	display();
 91
 92	pr_info("Driver loaded\n");
 93
 94	return 0;
 95}
 96
 97static void __exit linkedlist_exit(void)
 98{
 99	struct list_node *ptr, *next;
100
101	list_for_each_entry_safe(ptr, next, &my_list, list) {
102		list_del(&ptr->list);
103		kfree(ptr);
104	}
105
106	pr_info("Driver unloaded\n");
107}
108
109module_init(linkedlist_init);
110module_exit(linkedlist_exit);

1obj-m += delete.o
2all:
3	make -C /lib/modules/$(shell uname -r)/build M=$(PWD) modules
4clean:
5	make -C /lib/modules/$(shell uname -r)/build M=$(PWD) clean

1$ make all

API

Learning

INIT_LIST_HEAD

To initialize a list_head structure

list_head

To initialize the list

list_for_each_entry

To iterate over list of given type

list_for_each_entry_safe

To iterate over list of given type safe against removal of list entry

list_add_tail

To insert a new entry before the specified head

list_del

To delete entry from list

list_empty

To test whether a list is empty

list_entry

To get the struct for this entry
See Also