CODEWITHSUNDEEP
javalistiteratorlinked-list
Abidi
Abidi

Reputation: 7996

Java ListIterator Performance

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!

Upvotes: 1

Views: 2748

Answers (3)

Tom Hawtin - tackline
Tom Hawtin - tackline

Reputation: 147154

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)

Upvotes: 0

Peter Lawrey
Peter Lawrey

Reputation: 533492

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.

Upvotes: 0

StaxMan
StaxMan

Reputation: 116502

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.

Upvotes: 2

Related Questions