Self-Organizing Linked List in C
A self-organizing linked list is a type of linked list that dynamically rearranges its elements
based on usage patterns to improve search efficiency. These lists adapt over time, optimizing
frequently
accessed elements for faster lookup.
Types of Self-Organizing Strategies:
1. Move-To-Front (MTF): Moves the accessed node to the front of the list.
2. Count-Based: Nodes are reordered based on access frequency.
3. Transpose: Swaps an accessed node with its preceding node to gradually move it forward.
Advantages:
- Improves search efficiency for frequently accessed elements.
- Adaptable to changing access patterns.
- Simple to implement with minimal extra space.
Disadvantages:
- Performance can degrade if access patterns are unpredictable.
- Additional computations are required for reordering.
- MTF strategy may not be optimal if older elements remain frequently accessed.
Use Cases:
- Caching mechanisms where frequently accessed data should be readily available.
- Memory management systems.
- Applications requiring dynamic sorting of elements based on frequency.
C Implementation: Move-To-Front Strategy
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
int count; // For Count-based strategy
struct Node* next;
} Node;
void moveToFront(Node** head, int key) {
if (*head == NULL || (*head)->data == key) return;
Node *prev = NULL, *curr = *head;
while (curr && curr->data != key) {
prev = curr;
curr = curr->next;
}
if (curr && prev) {
prev->next = curr->next;
curr->next = *head;
*head = curr;
}
}
Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->count = 0;
newNode->next = NULL;
return newNode;
}
void printList(Node* head) {
while (head) {
printf("%d -> ", head->data);
head = head->next;
}
printf("NULL\n");
}
int main() {
Node* head = createNode(10);
head->next = createNode(20);
head->next->next = createNode(30);
printf("Before access:\n");
printList(head);
moveToFront(&head, 20);
printf("After accessing 20:\n");
printList(head);
return 0;
}
C Implementation: Count-Based Strategy
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
int count;
struct Node* next;
} Node;
void incrementCount(Node** head, int key) {
Node *curr = *head, *prev = NULL, *temp = NULL;
while (curr && curr->data != key) {
prev = curr;
curr = curr->next;
}
if (curr) {
curr->count++;
if (prev && prev->count < curr->count) {
prev->next = curr->next;
temp = *head;
if (temp->count < curr->count) {
curr->next = temp;
*head = curr;
} else {
while (temp->next && temp->next->count >= curr->count)
temp = temp->next;
curr->next = temp->next;
temp->next = curr;
}
}
}
}
Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->count = 0;
newNode->next = NULL;
return newNode;
}
void printList(Node* head) {
while (head) {
printf("%d(%d) -> ", head->data, head->count);
head = head->next;
}
printf("NULL\n");
}
int main() {
Node* head = createNode(10);
head->next = createNode(20);
head->next->next = createNode(30);
printf("Before access:\n");
printList(head);
incrementCount(&head, 30);
incrementCount(&head, 30);
incrementCount(&head, 20);
printf("After accessing nodes:\n");
printList(head);
return 0;
}
