C++ Program to Perform Searching using Self-Organizing Lists

C++ Program to implement Self-Organizing List.

Problem Description

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).

Problem Solution

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.

Program/Source Code

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;
}
Program Explanation

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.

advertisement
advertisement
Runtime Test Cases
Case 1:
 The list state is :->1->2->3->4->5->6->7->8->9
Enter the Element to be searched: 9
item found
 
The list state is :->9->1->2->3->4->5->6->7->8
	Do you want to search more...enter choice(y/n)?y
 
Enter the Element to be searched: 6
item found
 
The list state is :->6->9->1->2->3->4->5->7->8
	Do you want to search more...enter choice(y/n)?n

Sanfoundry Global Education & Learning Series – C++ Algorithms.
To practice all C++ Algorithms, here is complete set of 1000 C++ Algorithms.

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.