Self Organizing list is a list that re-organizes or re-arranges itself for better performance. In a simple list, an item to be searched is looked for in a sequential manner which gives the time complexity of O(n). But in real scenario not all the items are searched frequently and most of the time only few items are searched multiple times.Â
So, a self organizing list uses this property (also known as locality of reference) that brings the most frequent used items at the head of the list. This increases the probability of finding the item at the start of the list and those elements which are rarely used are pushed to the back of the list.Â
In Count Method, the number of time each node is searched for is counted (i.e. the frequency of search is maintained). So an extra storage is associated with each node that is incremented every time a node is searched. And then the nodes are arranged in non-increasing order of count or frequency of its searches. So this ensures that the most frequently accessed node is kept at the head of the list.Â
Examples:
Input : list : 1, 2, 3, 4, 5
searched : 4
Output : list : 4, 1, 2, 3, 5
Input : list : 4, 1, 2, 3, 5
searched : 5
searched : 5
searched : 2
Output : list : 5, 2, 4, 1, 3
Explanation : 5 is searched 2 times (i.e. the
most searched) 2 is searched 1 time and 4 is
also searched 1 time (but since 2 is searched
recently, it is kept ahead of 4) rest are not
searched, so they maintained order in which
they were inserted.
Implementation:
CPP
// CPP Program to implement self-organizing list// using count method#include <iostream>using namespace std;Â
// structure for self organizing liststruct self_list {Â Â Â Â int value;Â Â Â Â int count;Â Â Â Â struct self_list* next;};Â
// head and rear pointing to start and end of list resp.self_list *head = NULL, *rear = NULL;Â
// function to insert an elementvoid insert_self_list(int number){    // creating a node    self_list* temp = (self_list*)malloc(sizeof(self_list));Â
    // assigning value to the created node;    temp->value = number;    temp->count = 0;    temp->next = NULL;Â
    // first element of list    if (head == NULL)        head = rear = temp;Â
    // rest elements of list    else {        rear->next = temp;        rear = temp;    }}Â
// function to search the key in list// and re-arrange self-organizing listbool search_self_list(int key){    // pointer to current node    self_list* current = head;Â
    // pointer to previous node    self_list* prev = NULL;Â
    // searching for the key    while (current != NULL) {Â
        // if key is found        if (current->value == key) {Â
            // increment the count of node            current->count = current->count + 1;Â
            // if it is not the first element            if (current != head) {                self_list* temp = head;                self_list* temp_prev = NULL;Â
                // finding the place to arrange the searched node                while (current->count < temp->count) {                    temp_prev = temp;                    temp = temp->next;                }Â
                // if the place is other than its own place                if (current != temp) {                    prev->next = current->next;                    current->next = temp;Â
                    // if it is to be placed at beginning                    if (temp == head)                        head = current;                    else                        temp_prev->next = current;                }            }            return true;        }        prev = current;        current = current->next;    }    return false;}Â
// function to display the listvoid display(){Â Â Â Â if (head == NULL) {Â Â Â Â Â Â Â Â cout << "List is empty" << endl;Â Â Â Â Â Â Â Â return;Â Â Â Â }Â
    // temporary pointer pointing to head    self_list* temp = head;    cout << "List: ";Â
    // sequentially displaying nodes    while (temp != NULL) {        cout << temp->value << "(" << temp->count << ")";        if (temp->next != NULL)            cout << " --> ";Â
        // incrementing node pointer.        temp = temp->next;    }    cout << endl        << endl;}Â
// Driver Codeint main(){Â Â Â Â /* inserting five values */Â Â Â Â insert_self_list(1);Â Â Â Â insert_self_list(2);Â Â Â Â insert_self_list(3);Â Â Â Â insert_self_list(4);Â Â Â Â insert_self_list(5);Â
    // Display the list    display();Â
    search_self_list(4);    search_self_list(2);    display();Â
    search_self_list(4);    search_self_list(4);    search_self_list(5);    display();Â
    search_self_list(5);    search_self_list(2);    search_self_list(2);    search_self_list(2);    display();    return 0;} |
Python3
# Python3 Program to implement self-organizing list# using count methodÂ
# self organize list classclass self_organize_list(object):  # default constructor  def __init__(self):    self.__list = list()    self.__size = 0     # constructor to initialize list  def __init__(self, lst):    self.__list = [ [x, 0] for x in lst ]    self.__size = len(lst)Â
  # method to display the list  def display(self):    print(self.__list)Â
  # method to search key in list  def search(self, key):    index = -1    # find key in search organize list    for i in range(self.__size):      if self.__list[i][0] == key:        index = i        break             # check if key found    if index == -1:      return False    # Increment the frequency of key    self.__list[index][1] = self.__list[index][1] + 1    # finding new position for the key    new_pos = index    for i in range(index-1, -1, -1):      if self.__list[index][1] >= self.__list[i][1]:        new_pos = i    # Inserting the key in new position    bkp = self.__list[index]    self.__list.pop(index)    self.__list.insert(new_pos, bkp)    return True       # method to insert key in self organize list  def insert(self, key):    self.__list.append([key, 0])    self.__size = self.__size + 1Â
if __name__ == "__main__":  # initial list of four elements  lst = [1, 2, 3, 4]  sol = self_organize_list(lst)     # inserting new element and display  sol.insert(5)  sol.display()Â
  # sequence of search and display  sol.search(4)  sol.search(2)  sol.display()Â
  # sequence of search and display  sol.search(4)  sol.search(4)  sol.search(5)  sol.display()Â
  # sequence of search and display  sol.search(5)  sol.search(2)  sol.search(2)  sol.search(2)  sol.display() |
Output
List: 1(0) --> 2(0) --> 3(0) --> 4(0) --> 5(0) List: 2(1) --> 4(1) --> 1(0) --> 3(0) --> 5(0) List: 4(3) --> 5(1) --> 2(1) --> 1(0) --> 3(0) List: 2(4) --> 4(3) --> 5(2) --> 1(0) --> 3(0)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
