CODEWITHSUNDEEP
javaiteratorlinked-list
hello world123
hello world123

Reputation: 11

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?

Upvotes: 1

Views: 4280

Answers (3)

mayavi
mayavi

Reputation: 11

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)

Upvotes: 0

RichN
RichN

Reputation: 6231

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.

Upvotes: 5

Ryan
Ryan

Reputation: 734

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.

Upvotes: 0

Related Questions