KERNEL DATA STRUCTURE

A kernel data structure is a structure maintained inside the kernel to

store and manage information about system resources.
such as:
 Processes
 Memory
 Files
 Devices
 I/O operations
They allow the kernel to efficiently track, schedule, and control how
resources are used.

Key Kernel Data Structures (with Examples)

Here are the most common ones:
Purpose Data Structure Description
Holds info about each process
Process Process Control — process ID, state, CPU
management Block (PCB) registers, memory limits, open
files, priority, etc.
Memory Maps virtual addresses to
Page tables
management physical memory addresses.
Tracks which physical memory
Frame table
frames are allocated or free.
Purpose Data Structure Description
Free list / buddy Used to manage free memory
system blocks efficiently.
Stores metadata about files
File management Inode table (size, permissions, owner, disk
location).
File descriptor Keeps track of open files for
table each process.
Device control Store status and configuration
Device management
blocks (DCBs) info for I/O devices.
Queues of processes waiting for
Ready queue / CPU or I/O. Typically
Scheduling
waiting queue implemented as linked lists or
priority queues.
System calls / Interrupt Vector Maps interrupt numbers to the
interrupts Table corresponding service routines.

What is a Linked List?

A linked list is a linear data structure where elements are stored in nodes.
Each node typically has:
  Data → the actual value
 Pointer (link) → the address of the next node in the list
Unlike arrays, linked lists:
 Don’t require contiguous memory blocks.
 Can grow or shrink dynamically.
 Are efficient for insertion and deletion (especially in the middle).
1. Singly Linked List
Structure:
Each node contains:
[data | next]
 data: stores the value
 next: pointer to the next node
The last node’s next points to NULL (end of the list).
Example:
Head → [10 | •] → [20 | •] → [30 | NULL]
Pros:
 Simple and memory-efficient (only one pointer per node).
 Easy to traverse in one direction.
Cons:
 Can only move forward.
 Hard to reverse or go backward.
🔸 2. Doubly Linked List
Structure:
Each node contains:
[prev | data | next]
 prev: pointer to the previous node
 next: pointer to the next node
The first node’s prev = NULL, and the last node’s next = NULL.
Example:
NULL ← [10 | • | •] ↔ [20 | • | •] ↔ [30 | • | NULL]
Pros:
 Can be traversed in both directions.
 Easier to insert/delete nodes (no need to track previous node
manually).
Cons:
 Uses more memory (two pointers per node).
 Slightly more complex to implement.

🔁 3. Circular Linked List

Structure:
Like a singly or doubly linked list, but:
 The last node points back to the first node, forming a loop.
There are two types:
  Singly circular: last node’s next points to the first node.
 Doubly circular: last node’s next → first node, and first node’s
prev → last node.
Example (Singly Circular):
Head → [10 | •] → [20 | •] → [30 | •] ─┐
↑──────────────────────────────┘
Pros:
 Can traverse infinitely from any node.
 No NULL references (good for round-robin scheduling or
queues).
Cons:
 Care needed to avoid infinite loops during traversal.
 Slightly trickier insertion/deletion logic.
 Quick Comparison Table

Singly Linked Doubly Linked

Feature Circular Linked List
List List
Links per node 1 (next) 2 (prev, next) 1 or 2
Forward &
Traversal Forward only Forward or both (depending on type)
backward
End node points NULL NULL First node
to
Memory use Least More Same as singly/doubly
Circular queues, round-robin
Common uses Stack, simple lists Deques, navigation
scheduling
A Hash Map (also known as a Hash Table) is a data structure that
stores key–value pairs and allows fast data retrieval, insertion, and
deletion — typically in O(1) time on average.
It’s widely used in programming languages:
 C++: unordered_map
 Java: HashMap
 Python: dict
  Go: map
A bitmap (also called a bit array) is a data structure that uses bits
(0s and 1s) to represent a set of values or the status of objects
efficiently.
Each bit represents the presence (1) or absence (0) of a particular
element or condition.

💡 Basic Idea
 A bitmap is simply a sequence of bits.
 Each bit corresponds to an item, position, or state.