  We consider the problem of List Update, one of the most fundamental problems
in online algorithms. We are given a list of elements and requests for these
elements that arrive over time. Our goal is to serve these requests, at a cost
equivalent to their position in the list, with the option of moving them
towards the head of the list. Sleator and Tarjan introduced the famous "Move to
Front" algorithm (wherein any requested element is immediately moved to the
head of the list) and showed that it is 2-competitive. While this bound is
excellent, the absolute cost of the algorithm's solution may be very large
(e.g., requesting the last half elements of the list would result in a solution
cost that is quadratic in the length of the list). Thus, we consider the more
general problem wherein every request arrives with a deadline and must be
served, not immediately, but rather before the deadline. We further allow the
algorithm to serve multiple requests simultaneously. We denote this problem as
List Update with Time Windows. While this generalization benefits from lower
solution costs, it requires new types of algorithms. In particular, for the
simple example of requesting the last half elements of the list with
overlapping time windows, Move-to-Front fails. We show an O(1) competitive
algorithm. The algorithm is natural but the analysis is a bit complicated and a
novel potential function is required. Thereafter we consider the more general
problem of List Update with Delays in which the deadlines are replaced with
arbitrary delay functions. This problem includes as a special case the prize
collecting version in which a request might not be served (up to some deadline)
and instead suffers an arbitrary given penalty. Here we also establish an O(1)
competitive algorithm for general delays. The algorithm for the delay version
is more complex and its analysis is significantly more involved.
