encoded stream with the letter at that index in the list. Note the difference between this and the encoding method: The index in the list is used directly instead of looking up each value for its index. i.e. you start again with (abcdefghijklmnopqrstuvwxyz). You take the "1" of the encoded block and look it up in the list, which results in "b". Then move the "b" to front which results in (bacdef...). Then take the next "1", look it up in the list, this results in "a", move the "a" to front ... etc. Implementation Details of implementation are important for performance, particularly for decoding. For encoding, no clear advantage is gained by using a linked list, so using an array to store the list is acceptable, with worst-case performance O(nk), where n is the length of the data to be encoded and k is the number of values (generally a constant for a given implementation). The typical performance is better because frequently-used symbols are more likely to be at the front and will produce earlier hits. This is also the idea behind a Move-to-front self-organizing list. However, for decoding, we can use specialized data structures to greatly improve performance. Python This is a possible implementation of the move-to-front algorithm in Python. # mtfwiki.py from typing import Tuple, Union # Instead of always transmitting an "original" dictionary, it is simpler to just agree on an initial set. # Here we use the 256 possible values of a byte: common_dictionary = list(range(256)) def encode(plain_text: str) -> list[int]: # Change to bytes for 256. plain_text = plain_text.encode("utf-8") # Changing the common dictionary is a bad idea. Make a copy. dictionary = common_dictionary.copy() # Transformation compressed_text = list() # Regular array rank = 0 # Read in each character for c in plain_text: rank = dictionary.index(c) # Find the rank of the character in the dictionary [O(k)] compressed_text.append(rank) # Update the encoded text # Update the dictionary [O(k)] dictionary.pop(rank) dictionary.insert(0, c) return compressed_text # Return the encoded text The inverse will recover the original text: def decode(compressed_data: list[int]) -> str: compressed_text = compressed_data dictionary = common_dictionary.copy() plain_text = [] # Read in each rank in the encoded text for rank in compressed_text: # Read the character of that rank from the dictionary plain_text.append(dictionary[rank]) # Update the dictionary e = dictionary.pop(rank) dictionary.insert(0, e) return bytes(plain_text).decode("utf-8") # Return original string Example output: >>> import mtfwiki