To perform an insert, we check the appropriate list to see whether the element is already in place. If the element turns out to be new, it is inserted at the front of the list, since it is convenient and also because frequently it happens that recently inserted elements are the most likely to be accessed in the near future.