I thought the transactions within a block are stored in a Merkle tree, but the blocks themselves are stored as a linked list. So if you wanted to find a particular transaction you'd still have to traverse all the blocks (O(length)) and then inspect each block (O(log(depth))). I have no idea what dominates in verifying a Bitcoin transaction, so maybe in practice the cost of finding a particular block is amortized because you're spending most of your time within a block.

But from the original bitcoin paper[1] I got the impression that to verify any particular transaction you need to traverse the whole list of blocks.

[1]: https://bitcoin.org/bitcoin.pdf

In practice you can look up a tx by its hash from the transaction index (implemented with a Merkle tree)