CODEWITHSUNDEEP
javalinked-listiteratortime-complexity
Sourish Mukherjee
Sourish Mukherjee

Reputation: 179

Why not use ListIterator for full LinkedList Operation?

TimeComplexity For LinkedList

My main question is if ListIterator or Iterator class reduces the time taken for removal of the elements from a given LinkedList and the same can be said while adding elements in the same given LinkedList using any one of the following classes above. What's the point of using the inbuilt functions of LinkedList class itself? Why should we perform any of the operations through LinkedList functions when we can use the ListIterator functions for better performance?

Upvotes: 2

Views: 236

Answers (1)

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 476574

A ListIterator can indeed efficiently remove the node on which it is positioned. You can thus create a ListIterator, use next() two times to move the cursor, and then remove the node instantly. But evidently you did a lot of work before the actual removal.

Using ListIterator.remove is not more efficient "time complexity"-wise than removing through the LinkedList.remove(int index) if you need to construct the iterator. The LinkedList.remove method takes O(k) time, with k the index of the item you wish to remove. Removing this element with the ListIterator has the same timecomplexity since: (a) we create a ListIterator in constant time; (b) we call .next() k times, each operation in O(1); and (c) we call .remove() which is again O(1). But since we call .next() k times, this is thus an O(k) operation as well.

A similar situation happens for .add(..) on an arbitrary location (an "insert"), except that we here of course insert a node, not remove one.

Now since the two have the same time complexity, one might wonder why a LinkedList has such remove(int index) objects in the first place. The main reason is programmer's convenience. It is more convenient to call mylist.remove(5), than to create an iterator, use a loop to move five places, and then call remove. Furthermore the methods on a linked list guard against some edge-cases like a negative index, etc. By doing this manually you might end removing the first element, which might not be the intended behaviour. Finally code written is sometimes read multiple times. If a future reader reads mylist.remove(5), they understand that it removes the fifth element, wheres a solution with looping will require some extra brain cycles to understand what that part is doing.

As @Andreas says, furthermore the List interface defines these methods, and hence the LinkedList<T> should implement these.

Upvotes: 5

Related Questions