You don't need timestamps for this. Just move each item to the head of the list every time it is used. Then the LRU item is at the end of the list, on the average.
There's also a rather good algorithm in Knuth volume 1 that doesn't deliver true LRU but settles down in time to a very good approximation. It just consists of a ring of bits: you set the item's bit on every access, and when looking for a free slot you scan the ring, clearing set bits until you find one already clear. That means it hasn't been used for at least one trip right around the ring. Next time you scan, start from the place where you stopped this time.