chap searching and the total number of comparisons required is finallyif the list is organized by the transpose heuristicthen the final list will be hand the total number of comparisons required is while self-organizing lists do not generally perform as well as search trees or sorted listboth of which require (log nsearch timethere are many situations in which self-organizing lists prove valuable tool obviously they have an advantage over sorted lists in that they need not be sorted this means that the cost to insert new record is lowwhich could more than make up for the higher search cost when insertions are frequent self-organizing lists are simpler to implement than search trees and are likely to be more efficient for small lists nor do they require additional space finallyin the case of an application where sequential search is "almostfast enoughchanging an unsorted list to self-organizing list might speed the application enough at minor cost in additional code as an example of applying self-organizing listsconsider an algorithm for compressing and transmitting messages the list is self-organized by the move-to-front rule transmission is in the form of words and numbersby the following rules if the word has been seen beforetransmit the current position of the word in the list move the word to the front of the list if the word is seen for the first timetransmit the word place the word at the front of the list both the sender and the receiver keep track of the position of words in the list in the same way (using the move-to-front rule)so they agree on the meaning of the numbers that encode repeated occurrences of words for exampleconsider the following example message to be transmitted (for simplicityignore case in lettersthe car on the left hit the car left the first three words have not been seen beforeso they must be sent as full words the fourth word is the second appearance of "the,which at this point is the third word in the list thuswe only need to transmit the position value " the next two words have not yet been seenso must be sent as full words the seventh word is the third appearance of "the,which coincidentally is again in the third position the eighth word is the second appearance of "car,which is now in the fifth position of the list "iis new wordand the last word "leftis now in the fifth position thus the entire transmission would be