Unrolled Linked Lists: The Cache-Friendly Data Structure You Didn't Know You Needed
In the world of data structures, the linked list is a beloved classic, like your grandma's apple pie recipe. It's simple, effective, and everyone understands it. But sometimes, you need something a little more sophisticated—enter the unrolled linked list. This variation on the traditional linked list stores multiple elements in each node, offering significant performance benefits, especially when it comes to cache efficiency.
What is an Unrolled Linked List?
An unrolled linked list is a hybrid data structure that combines the properties of linked lists and arrays. Each node in an unrolled linked list contains an array of elements instead of a single element. This design can dramatically improve cache performance and reduce memory overhead associated with storing list metadata.
A Typical Node Structure
Here's what a typical unrolled linked list node looks like:
//C
typedef struct Node {
struct Node* next; // Reference to the next node
int numElements; // Number of elements in this node
int elements[4]; // Array of elements, with space for up to 4
} Node;
//TypeScript
class Node {
next: Node | null = null;
numElements: number = 0;
elements: number[] = [];
constructor(maxElements: number) {
this.elements = new Array(maxElements);
}
}
In this example, each node can hold up to 4 elements. The numElements field keeps track of how many elements are currently stored in the node.
Why Use Unrolled Linked Lists?
Unrolled linked lists offer several advantages over traditional linked lists:
- Improved Cache Performance: By storing multiple elements in each node, unrolled linked lists make better use of CPU cache lines, reducing the number of cache misses.
- Reduced Memory Overhead: The metadata overhead (references and element counts) is spread over multiple elements, which is more efficient than traditional linked lists where each node typically contains just one element.
Operations on Unrolled Linked Lists
Insertion
To insert a new element, we find the node where the element should be placed and insert it into the array within that node. If the array is full, we create a new node and split the elements between the current node and the new one.
//C
void insert(Node** head, int value) {
Node* current = *head;
while (current->next != NULL && current->numElements == 4) {
current = current->next;
}
if (current->numElements < 4) {
current->elements[current->numElements++] = value;
} else {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->numElements = 2;
newNode->elements[0] = current->elements[2];
newNode->elements[1] = current->elements[3];
current->numElements = 2;
current->elements[2] = value;
newNode->next = current->next;
current->next = newNode;
}
}
//TypeScript
function insert(head: Node, value: number, maxElements: number) {
let current: Node | null = head;
while (current.next !== null && current.numElements === maxElements) {
current = current.next;
}
if (current.numElements < maxElements) {
current.elements[current.numElements++] = value;
} else {
const newNode = new Node(maxElements);
newNode.numElements = Math.floor(maxElements / 2);
for (let i = 0; i < newNode.numElements; i++) {
newNode.elements[i] = current.elements[Math.floor(maxElements / 2) + i];
}
current.numElements = Math.floor(maxElements / 2);
current.elements[current.numElements++] = value;
newNode.next = current.next;
current.next = newNode;
}
}
Deletion
To delete an element, we find the node containing the element and remove it from the array. If the node becomes less than half full, we move elements from the next node to fill it up.
Recommended by LinkedIn
//C
void delete(Node** head, int value) {
Node* current = *head;
Node* prev = NULL;
while (current != NULL) {
for (int i = 0; i < current->numElements; i++) {
if (current->elements[i] == value) {
for (int j = i; j < current->numElements - 1; j++) {
current->elements[j] = current->elements[j + 1];
}
current->numElements--;
if (current->numElements < 2 && current->next != NULL) {
for (int k = 0; k < current->next->numElements; k++) {
current->elements[current->numElements++] = current->next->elements[k];
}
Node* temp = current->next;
current->next = current->next->next;
free(temp);
}
return;
}
}
prev = current;
current = current->next;
}
}
//TypeScript
function remove(head: Node, value: number, maxElements: number) {
let current: Node | null = head;
let prev: Node | null = null;
while (current !== null) {
for (let i = 0; i < current.numElements; i++) {
if (current.elements[i] === value) {
for (let j = i; j < current.numElements - 1; j++) {
current.elements[j] = current.elements[j + 1];
}
current.numElements--;
if (current.numElements < Math.floor(maxElements / 2) && current.next !== null) {
for (let k = 0; k < current.next.numElements; k++) {
current.elements[current.numElements++] = current.next.elements[k];
}
const temp = current.next;
current.next = current.next.next;
// Simulate free in TypeScript by setting the object to null
temp.next = null;
}
return;
}
}
prev = current;
current = current.next;
}
}
Traversal
Traversal is the process of visiting each element in the unrolled linked list. This is typically done to perform some operation on each element, such as printing the list or calculating a sum.
//C
void traverse(Node* head) {
Node* current = head;
while (current != NULL) {
for (int i = 0; i < current->numElements; i++) {
printf("%d ", current->elements[i]);
}
current = current->next;
}
printf("\n");
}
//TypeScript
function traverse(head: Node) {
let current: Node | null = head;
while (current !== null) {
for (let i = 0; i < current.numElements; i++) {
console.log(current.elements[i]);
}
current = current.next;
}
console.log('');
}
Search
Searching for an element in an unrolled linked list involves traversing the list until the element is found.
//C
bool search(Node* head, int value) {
Node* current = head;
while (current != NULL) {
for (int i = 0; i < current->numElements; i++) {
if (current->elements[i] == value) {
return true;
}
}
current = current->next;
}
return false;
}
//TypeScript
function search(head: Node, value: number): boolean {
let current: Node | null = head;
while (current !== null) {
for (let i = 0; i < current.numElements; i++) {
if (current.elements[i] === value) {
return true;
}
}
current = current.next;
}
return false;
}
Update
Updating an element involves finding the element and replacing it with a new value.
//C
bool update(Node* head, int oldValue, int newValue) {
Node* current = head;
while (current != NULL) {
for (int i = 0; i < current->numElements; i++) {
if (current->elements[i] == oldValue) {
current->elements[i] = newValue;
return true;
}
}
current = current->next;
}
return false;
}
//TypeScript
function update(head: Node, oldValue: number, newValue: number): boolean {
let current: Node | null = head;
while (current !== null) {
for (let i = 0; i < current.numElements; i++) {
if (current.elements[i] === oldValue) {
current.elements[i] = newValue;
return true;
}
}
current = current.next;
}
return false;
}
Length Calculation
Calculating the length of the unrolled linked list involves summing up the number of elements in each node.
//C
int length(Node* head) {
Node* current = head;
int totalLength = 0;
while (current != NULL) {
totalLength += current->numElements;
current = current->next;
}
return totalLength;
}
//TypeScript
function length(head: Node): number {
let current: Node | null = head;
let totalLength = 0;
while (current !== null) {
totalLength += current.numElements;
current = current.next;
}
return totalLength;
}
Conclusion
Unrolled linked lists are a powerful alternative to traditional linked lists, offering significant performance and memory efficiency benefits. By understanding how to implement and manipulate these data structures in languages like C and TypeScript, you can optimize your applications for better performance, especially when dealing with large datasets or systems with constrained memory resources.
So, next time you find yourself reaching for a standard linked list, consider giving the unrolled linked list a try. Your CPU cache will thank you!
If you found this article useful, don't forget to like, share, and follow for more insights into advanced data structures and performance optimization!
#LinkedIn #DataStructures #Programming #CProgramming #TypeScript #SoftwareEngineering #PerformanceOptimization #CacheEfficiency