Java ListIterator Performance

Question

I was reading a thread here about the performance of java ArrayList and LinkedList. There is an answer from Mr Kevin Brock that reads the following.

"Linked list add is not always O(1) [or this should say addLast() is O(1)]. This is only true if done from within a ListIterator. The add methods in Java's LinkList implementation must search through the list if additions are not on the head or tail."

I din't understand what he meant by "only if done through ListIterator". Does it mean there is a data structure within the linkedlist that holds the reference of each index and as soon as we get the listiterator from a certain index, listiterator is returned straight away without walking through the list to find that index?

Thanks guys!

score 2 · Accepted Answer · answered Dec 12 '10 at 19:00

2

It means that iterator points to list nodes directly; and so access via get(int) will be O(N), but iterator.next() wil be O(1). Latter has direct reference and does not need to traverse anything; former will need to traverse from head of the list.

answered Dec 12 '10 at 19:00

StaxMan

113,358
34
211
239

Thanks for the prompt answer Staxman. So does it mean ListIterator is something that is maintained in parallel with "linkedlist" to hold the references of nodes? – Abidi Dec 12 '10 at 19:11
1

@Abidi, sort of yes. However, I suspect what you are doing can be done another way more efficiently. Usually, there is another way to do what needs to be done so you don't have to insert in random places into a list. – Peter Lawrey Dec 12 '10 at 19:15

score 0 · Answer 2 · answered Dec 12 '10 at 19:01

0

If you add to a LinkedList where the ListIterator is pointing to, it is O(1). This is the same as adding to the start of the LinkedList or the end of an ArrayList.

answered Dec 12 '10 at 19:01

Peter Lawrey

525,659
79
751
1,130

score 0 · Answer 3 · answered Dec 12 '10 at 21:19

The comment refers to the two argument add method, [add(int,E)][1]. Assuming a linearly distributed index, then this will be O(n) as the list needs to be iterated through to find the appropriate node. It does not apply to add(E).

[1]: http://download.oracle.com/javase/6/docs/api/java/util/LinkedList.html#add(int, E)

Java ListIterator Performance

3 Answers3