how to understand that the time complexity of Find(x) in linked list is Theta(1)?

Question

I run into this when I reading the book but I don't understand. Don't we still have to compare through the list to find a specific element? Thanks.

Answer 1

Yes you do. I'm not sure what attributes the linked list in your book includes, but it is possible (with indexing or another strategy) to have a search faster than O(n). Check out http://en.wikipedia.org/wiki/Linked_list#Speeding_up_search for more information on search optimization.