C++ Program to implement Self-Organizing List.
1. Self-Organizing list updates on the basis of last searched item.
2. The sequential searching approach is used.
3. In general search, 80% time only specific 20% of data is accessed.
4. This algorithm shifts the more important data to the beginning of the list.
5. The time complexity of search is O(n).
1. Create a linked list with the data element.
2. Search the element in the list.
3. If element found, delete it from the list and add at the beginning of the list.
4. Exit.
C++ program to compare Binary and Sequential Search.
This program is successfully run on Dev-C++ using TDM-GCC 4.9.2 MinGW compiler on a Windows system.
#include<iostream> using namespace std; // A structure to representing a node. struct node { int data; node *next; }; // A function to create a new node. node* CreateNode(int data) { node *newnode = new node; newnode->data = data; newnode->next = NULL; return newnode; } // A function to add the data at the end of the list. node* InsertIntoList(node *head, int data) { node *temp = CreateNode(data); node *t = new node; t = head; if(head == NULL) { head = temp; return head; } else { // Traversing to the end of the list. while(t->next != NULL) t = t->next; // Add the node at the end. t->next = temp; } return head; } void Display(node *head) { node *temp = new node; temp = head; cout<<"\n The list state is :"; // Display the list. while(temp->next != NULL) { cout<<"->"<<temp->data; temp = temp->next; } } node* SearchItem(node *head, int item) { int flag = 0; node *temp = new node; node *t = new node; temp = head; if(temp->data == item) { cout<<"\nItem found at head node"; flag = 5; Display(head); return head; } else { while((temp->next)->next != NULL) { if((temp->next)->data == item) { cout<<"\n item found"; flag = 5; break; } temp = temp->next; } // Organising the list. // Shifting the searched node to the head. t = (temp->next)->next; (temp->next)->next = head; head = temp->next; temp->next = t; if(flag == 5) Display(head); else cout<<"\nItem not found."; } return head; } int main() { int i, n; char ch; node *head = new node; head = NULL; for(i = 1; i < 11; i++) head = InsertIntoList(head, i); Display(head); up: cout<<"\nEnter the Element to be searched: "; cin>>n; // Update the head of the list. head = SearchItem(head, n); cout<<"\n\n\tDo you want to search more...enter choice(y/n)?"; cin>>ch; if(ch == 'y' || ch == 'Y') goto up; return 0; }
1. Add the data into the linked list using InsertIntoList().
2. Display the list using Display().
3. Take the input of the item to be searched.
4. Call SearchItem().
5. If item found, shift that node to beginning and display the list.
6. If not found, simply return to the main() and ask the user for another search.
7. Display the state of the list.
8. Exit.