// HACKER NEWS — CYBERSECURITY
Intrusive Linked Lists
This post will teach you what intrusive linked lists are and how they are used to manage processes in Linux.
Intrusive linked lists are a variation of linked lists where the links are embedded in the structure that’s being linked.
In a typical linked list implementation, a list node contains a data pointer to the linked data and a next pointer to the next node in the list.
In an intrusive linked list implementation, the list node contains next pointer to the next list node, but no data pointer because the list is embedded in the linked object itself.
A list structure for an intrusive singly linked list contains a single next pointer to another list node:
The list structure is then embedded in the structure that will be linked. For example, you might have a item structure with a val member:
To add a new item i2 to the list of i1, you set the items.next pointer of i1 to the address of i2.items:
You can access the object that contains a list node by first getting the address of the list object (e.g. the value of i1.items.next). You then subtract the offset of the list member from the address of the list object.
The offset is the number of bytes a member is positioned from the beginning of its containing object.
Consider a list object in an object i2 at memory address 0x18. The list member is offset 8 bytes from the beginning of the item data structure. Therefore, the beginning address of the i2 object is 0x18 - 8 = 0x10.