How does the Bitcoin client check for double spend? When the Bitcoin client looks at the input of a transaction, it know the hash of the previous transaction from which the funds are coming, however then, how does it know that this output has not been spent already? Does it need to scan the whole blocklist for another transaction spending that same output? Isn't that very inefficient?
Bitcoin-Qt marks outputs as spent in the database once they are spent. To check whether an input's prev-out is spent, Bitcoin just needs to look up the transaction and check whether the output is marked spent.

Other ways of doing it are to have a set of all unspent outputs and check whether the prev-out is in this set (future versions of Bitcoin will do something like this), or to index inputs by their prev-outs.