Certainly an interesting discussion of some algorithms here, however...<p>"In fact the number of checks grows quadratically with the length of your list"<p>No, no this is not necessarily true at all? If you are talking about an interview-style question where we are discussing a linked list in memory not some giant implicit list of integers, then it is very easy to beat O(n^2). If the list size is known, it's very easy to construct a hash table or hash set where collisions are extremely low and O(1) lookups are expected, giving an O(n) algorithm. A binary search tree would give O(n log n)