> I don't understand is why his data structure for finding the least-recently-used item wasn't just a linked list
Because he is not talking about expiring the Least Recently Used item, but to expire the items whose "cache time" has expired. That is, when you add a new item to the cache, you add it with some lifetime (e.g.: an integer). Then you have some clock (another integer) and what Varnish wants to do is expire all items whose lifetime is lower than the current clock.
With a (doubly-)linked list you would have to traverse the list on insertion to place the item in the correct spot...
Because he is not talking about expiring the Least Recently Used item, but to expire the items whose "cache time" has expired. That is, when you add a new item to the cache, you add it with some lifetime (e.g.: an integer). Then you have some clock (another integer) and what Varnish wants to do is expire all items whose lifetime is lower than the current clock.
With a (doubly-)linked list you would have to traverse the list on insertion to place the item in the correct spot...