Linux: The Intrusive Linked List Implementation

A linked list is a basic data structure widely used among developers to implement stack, queue, hash table, graph, etc. It is quite extensively used in the Linux kernel to implement process and memory management. In this blog, I will explain why the Linux kernel implements linked lists differently and how.

A generic Linked List node contains data and reference pointers pointing to the next or previous node.

struct node {
    int data;
    struct node *prev;
    struct node *next;
}

The head pointer points to the start of the linked list. A typical linked list implementation requires three basic routines -

1. initialize(struct node *head);
2. struct node * add_entry(struct node *head, struct node *new_node);
3. struct node * remove_entry(struct node *head);

1. initialize: To initialize a linked list head.
2. add_entry: Add a new node at the start of the list.
3. remove_entry: Remove a node from the start of the list.

The problem with this approach

Let us say I want to create another linked list struct student and use these routines for list operations.

Will it work? The answer is - NO! Why?