Self-Organizing Linked List in C
A self-organizing linked list is a data structure that rearranges its nodes dynamically based on
access patterns,
improving search efficiency. The three main strategies used are Move-To-Front (MTF),
Count-Based, and Transpose.
Self-Organizing Strategies:
1. Move-To-Front (MTF): Moves accessed nodes to the front of the list.
2. Count-Based: Reorders nodes based on access frequency.
3. Transpose: Swaps an accessed node with its preceding node, moving it gradually forward.
Advantages:
- Improves search efficiency for frequently accessed elements.
- Adaptable to changing access patterns.
- Simple and lightweight with minimal overhead.
Disadvantages:
- Performance can degrade with unpredictable access patterns.
- Extra processing required to rearrange elements.
- MTF may not be ideal for long-term frequency-based access.
Use Cases:
- Caching mechanisms for frequently accessed data.
- Dynamic priority queues.
- Memory management and data compression.
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;
}
C Implementation: Transpose Strategy
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node* next;
} Node;
void transpose(Node** head, int key) {
if (*head == NULL || (*head)->data == key) return;
Node *prev = NULL, *curr = *head, *pre_prev = NULL;
while (curr && curr->data != key) {
pre_prev = prev;
prev = curr;
curr = curr->next;
}
if (curr && prev) {
prev->next = curr->next;
curr->next = prev;
if (pre_prev)
pre_prev->next = curr;
else
*head = curr;
}
}
Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
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);
transpose(&head, 30);
printf("After accessing 30:\n");
printList(head);
return 0;
}
