Iterator Time complexity for a LinkedList in Java?

Question

The code below will be calling the iterator and sending the integer back to the method it was called from. I just wanted to know if by using an Iterator would my time complexity become constant? (i.e O(1)). Because if I use a get with a LinkedList, it will give me linear time(i.e O(n)).

protected int least(int i) {
    if(i >= digits.size()) {
        return 0;           
    }

    // temp++;
    // System.out.println("Time taken=" + temp);
    // long start = System.nanoTime();

    ListIterator<Integer> itr1 = digits.listIterator(digits.size() - i);

    // System.out.println("Time elapsed:" + (System.nanoTime() - start));

    return itr1.previous();
}

Answer 1

Iterator starting at i-th element

If you create an Iterator which directly starts at the i-th index of a LinkedList, you need to know that this also takes O(n). Finding an element in a LinkedList is always slow.

LinkedList does only memorize the head (and tail) element of the list. Every other element needs to be found by traversing the whole list.

Here is an illustration of a doubly linked list (Javas LinkedList is also doubly linked):

So if you create an Iterator starting at the i-th element, it will start at head (or tail) and follow the pointers up to the i-th element. It is like calling:

list.get(i);

This obviously costs O(n).

---

Alternative: ArrayList

If you need a fast index-based access, also called random-access, you may consider using an ArrayList instead. Its structure allows access in O(1) (it can directly compute the position of the element in the memory by start + i * sizeof(type)).

Data-structures that provide such a fast random-access usually implement the interface RandomAccess (documentation and implementing classes) as indicator.

---

How to iterate

Iterating a LinkedList should, as said, not be done by index-based access via list.get(i). You should therefore use an Iterator (or ListIterator if you need to modify the list while iterating).

Here is the usual approach using an Iterator:

Iterator<E> iter = list.iterator();
while (iter.hasNext()) {
    E element = iter.next();
    ...
}

Or you can also use the enhanced for-loop which internally does the same, but looks more compact:

for (E element : list) {
    ...
}

As Javas LinkedList is a doubly-linked list you can also start from the tail and iterate the list reversely. Therefore just use the LinkedList#descendingIterator method (documentation) instead of LinkedList#iterator.

Finally an example that shows how to use ListIterator to modify the list while iterating:

ListIterator<E> listIter = list.listIterator(0);
while (listIter.hasNext()) {
    E element = listIter.next();
    ...
    // Remove the element last polled
    listIter.remove();
    // Inserts an element right before the last polled element
    listIter.add(new Element());
}

You can also traverse the list forwards and backwards with ListIterator by using hasPrevious() and previous() methods. Here is its documentation.