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.

Answer 2

No.

Linked lists are not designed to be accessed randomly in O(1) time. Using an iterator to access it is still O(n).

To understand why, we need to dig into the implementation of listIterator(int):

public ListIterator<E> listIterator(int index) {
    checkPositionIndex(index);
    return new ListItr(index);
}

This methods returns a new ListItr, let's see how this is created:

    ListItr(int index) {
        // assert isPositionIndex(index);
        next = (index == size) ? null : node(index);
        nextIndex = index;
    }

The constructor calls node, which is implemented like this:

Node<E> node(int index) {
    // assert isElementIndex(index);

    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++) <<<<< HERE!
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--) <<<<<< HERE!
            x = x.prev;
        return x;
    }
}

Now do you see it? A for loop iterating over the nodes all the way up to the one at index index. This means that it is O(n)! The speed of getting an iterator increases linearly as the elements in the linked list and your index increases.

Answer 3

If your intention is to get the last-but-one element, then since the LinkedList implementation is a doubly linked list, then there should be a reference to the tail and the head available to the instance, as well as the size.

This means that a List.descendingIterator() would probably be a better starting point, if you have to start at the end, but you are always going to be in O(n) time to index into LinkedList structure.

If you are regularly dereferencing by index, you should normally use a random access structure, such as an ArrayList.

If you are actually iterating through the list in either direction, then you should return your iterator, not the value.