What kind of iteration should I use for LinkedList?

I know that traversing LinkedList by indexing is bad, because list.get(n) is executed in linear time O(n). Thus i shouldn't use indexing. I looked at the AbstactList.Itr that is returned by iterator() call, it uses get(cursor) too. I'm confused.

As pointed out by @axtavt开发者_高级运维 , LinkedList.iterator() actually calls listIterator() which returns AbstactList.ListItr which extends AbstactList.Itr and it only adds implementations of ListIterator interface. Thus the machinery for getting next element is still the same as in AbstactList.Itr. `AbstactList.Itr's next(); calls get(n) on the specified list.

---

The foreach loop is very efficient, and easy:

List<String> list = new LinkedList<String>();
list.add("First");
list.add("Second");
list.add("Third");
list.add("Fourth");

for(String s : list) {
    System.out.println(s);
}

---

The best iteration over any List (actually even any Iterable) is the for each loop:

for(Element e : myList){
    // do something
}

---

LinkedList inherits not only from AbstractList, but also from AbstractSequentialList which in turn implements iterator() like this:

public Iterator<E> iterator() {
    return listIterator();
}

and the ListIterator returned by LinkedList is smart about using sequential access.

So whether you use foreach, iterator() or listIterator(), you are always dealing with the same smart iterator type.

---

You should use a foreach loop if you can - that's the most efficient:

List<Item> myList = ...;

for (Item item : myList) {
  ...
}

If you need to modify the list inside the loop, or traverse through multiple collections in one loop, use an iterator:

List<Item> myList = ...;
Iterator<Item> it = myList.iterator();

while (it.hasNext()) {
  Item item = it.next();
  ...
}

And if you need to traverse backwards, or something else specific to linked lists, use listIterator:

ListIterator<Item> it = myList.listIterator();
...

---

You can use iterator, which returned by iterator method. It doesn't require O(n) time to go to next item. It uses ListIterator implementation from LinkedList so it's fast.

---

You can use the Iterator, it gives you a faster access. A sample code for a list:

 List<String> list = new LinkedList<String>();
    list.add("First");
    list.add("Second");
    list.add("Third");
    list.add("Fourth");

    Iterator it = list.iterator();

    while(it.hasNext())
    {
        System.out.println(it.next());
    }