Why can't we manually iterate through a LinkedList?

Question

LinkedList is a data structure, in which each element is coupled with a link to its next element.

So, in theory, this data structure is made for freely iterating through a list, in whichever direction, while performing whatever operations (except, maybe, deleting the element you're currently at).

However, in application, this isn't true. Returning an Iterator from a LinkedList is subject to the general Iterator rules (i.e. no modifying while iterating), and even creating a ListIterator, an improved Iterator, which allows modifying the next/previous element of the iterator, and let's you go forward/backward dynamically, still has severe limitations:

You can't delete elements from the beginning of the list if you're not currently there, and neither can you add elements to the end of the list, unless you're currently there.

So, is there a way to iterate freely through a LinkedList while performing whatever modifications to the list? And if not, why isn't there one? Shouldn't it be one of the main goals of this data structure to realize it?

Answer 1

The choice to make all Iterators failfast was a design decision, just that and nothing more.

Nothing stops you to take the code and starting from that, build a NotSoFailFastIterator for yourself if you think you can use it. However I think you'll quickly revert from using it once yoy see its behaviour and its results in usage scenarios where there's really lots of concurrent activity going on on the underlying List of your iterator.

Answer 2

This behavior is not specific to LinkedLists. When you iterate over a List (any List) with a ListIterator, you can only make structural changes (adding or removing elements) in the current position of the iterator. Otherwise, continuing to use the iterator after a structural change of the List may yield unexpected results.

For adding elements to the start or end of the LinkedList, you have addFirst and addLast methods. You don't have to iterate over the List in order to do that.

A ListIterator instance maintains a state that allows it to locate the next and previous elements as well as support other operations (remove the current element, add an element at the current position). If you make a structural change to a List not via the ListIterator, the state of the iterator may become invalid, leading to unexpected results. Therefore all structural changes must be made via the ListIterator.

I guess that the LinkedList class could supply an implementation of a more complex iterator that supports operations such as addFirst and addLast. I'm not sure how useful that would have been, and whether it would justify the added complexity.

Answer 3

When you have a linked list datastructure, you can add or remove at a particular node, when your cursor is pointing to the right node where you want to add or remove.

Inserts the specified element into the list (optional operation). The element is inserted immediately before the element that would be returned by next(), if any, and after the element that would be returned by previous(), if any. The new element is inserted before the implicit cursor: a subsequent call to next would be unaffected, and a subsequent call to previous would return the new element. (This call increases by one the value that would be returned by a call to nextIndex or previousIndex.)

ListIterator

Instead if its a array structure, then you access by index , and it is possible to add or remove at a particular index limited , by the length of the array. ArrayList does that.

Answer 4

If you want to iterate freely use array or list. Linked lists are meant to be traversed and access the data useful in dynamic allocation of the memory to the data.