This week's book giveaway is in the OCMJEA forum. We're giving away four copies of OCM Java EE 6 Enterprise Architect Exam Guide and have Paul Allen & Joseph Bambara on-line! See this thread for details.
How would you go through all elements of a Set or Map without using Iterators? List is one of the few that allows direct access. And even then you should be careful; if you have a LinkedList then calling get(...) will always need to iterate from the start or end to that place. That's because those are the only two fixed points in a LinkedList. In this case, using size() and get(...) will work but it will be much slower than using an Iterator, especially if the LinkedList becomes very large.
With an iterator you don't need to make any assumptions about the internals of a data structure. They may come from any source. E.g. you could build an iterator that iterates over millions of entries. But you still hold only the current one and let the data structure decide how to get the next one (e.g. by holding an index and loading the specified entry or by generating the next permutation). If you allow methods like size() or get(int index) you need to know the size in advance and maybe you have to load every object or at least every object until "index".
Oh, and iterator allows you to use the enhanced for loop.