Java : Iterator pointing to the last element in a LinkedList

In java LinkedLists, we have iterators.

I can use a ListIterator and then do a linear search to find the last element that the Iterator points to. But It will take O(n) 开发者_高级运维time. How can I find an Iterator that points to the last element in O(1) time?

---

The java.util.LinkedList is actually the doubly-linked variant. It can traverse from both ends. Hence, getting the first and getting the last element are equally fast.

At least this is the case with Sun's (Oracle's?) implementation.

---

I'm not sure if this is O(1), but if you really want an iterator to the last element (instead of just getting the last element), you can use the listIterator(index) method, where index is the position in the list you want the iterator to start from.

---

By definition of Linked List, there is a pointer only to the head or first item and access to every other node is possibly only sequentially! So I am afraid the answer is NO! There is no way you can access the last element in O(1) time. You could put the linked-list contents into an array or map and then the next access could be O(1)