Почему мы не можем вручную перебрать LinkedList?

Question

LinkedList - это структура данных, в которой каждый элемент связан со ссылкой на следующий элемент.

Таким образом, теоретически эта структура данных предназначена для свободной итерации по списку, в зависимости от того, чтонаправление, при выполнении каких-либо операций (за исключением, может быть, удаления элемента, в котором вы находитесь).

Однако в приложении это не так.Возврат Итератора из LinkedList подчиняется общим правилам Iterator (т.е. без изменения во время итерации) и даже создает ListIterator, улучшенный Iterator, который позволяет изменять следующий / предыдущий элемент итератора, идавайте динамически двигаться вперед / назад, но все еще имеет серьезные ограничения:

Вы не можете удалять элементы из начала списка, если вы в данный момент там не находитесь, и вы также не можете добавлять элементы в конец списка.список, если вы в настоящее время там.

Итак, есть ли способ свободно перебирать LinkedList при выполнении каких-либо изменений в списке?А если нет, то почему нет?Разве это не должно быть одной из основных целей этой структуры данных для ее реализации?

Answer 1

Выбор сделать все Отказоустойчивые итераторы был дизайнерским решением, только это и ничего более.

Ничто не мешает вам взять код и, начиная с этого, создать NotSoFailFastIterator для себяесли вы думаете, что можете использовать это.Однако я думаю, что вы быстро откажетесь от его использования, как только увидите его поведение и его результаты в сценариях использования, когда в базовом списке вашего итератора происходит действительно много одновременных действий.

Answer 2

Это поведение не относится только к LinkedList с.Когда вы перебираете List (любой List) с ListIterator, вы можете вносить структурные изменения (добавлять или удалять элементы) только в текущей позиции итератора.В противном случае продолжение использования итератора после структурного изменения List может привести к неожиданным результатам.

Для добавления элементов в начало или конец LinkedList у вас есть addFirst и addLastметоды.Вам не нужно перебирать List, чтобы сделать это.

Экземпляр ListIterator поддерживает состояние, позволяющее ему находить следующий и предыдущий элементы, а также поддерживать другие операции (удалитьтекущий элемент, добавить элемент в текущей позиции).Если вы внесете структурное изменение в List не через ListIterator, состояние итератора может стать недействительным, что приведет к неожиданным результатам.Поэтому все структурные изменения должны быть сделаны с помощью ListIterator.

Я думаю, что класс LinkedList мог бы обеспечить реализацию более сложного итератора, который поддерживает такие операции, как addFirst и addLast.Я не уверен, насколько это было бы полезно и оправдало ли это дополнительную сложность.

Answer 3

Если у вас есть связанная структура данных списка, вы можете добавлять или удалять ее в определенном узле, когда курсор указывает на правый узел, в который вы хотите добавить или удалить.

Вставка указанного элемента в список (необязательная операция).Элемент вставляется непосредственно перед элементом, который будет возвращен функцией next (), если таковой имеется, и после элемента, который будет возвращен функцией previous (), если таковой имеется.Новый элемент вставляется перед неявным курсором: последующий вызов next не будет затронут, а последующий вызов previous вернет новый элемент.(Этот вызов увеличивает на единицу значение, которое будет возвращено вызовом nextIndex или previousIndex.)

ListIterator

Вместо этого, если это структура массива,затем вы получаете доступ по индексу, и можно добавлять или удалять по определенному индексу, ограниченному длиной массива.ArrayList делает это.

Answer 4

Если вы хотите свободно перебирать, используйте массив или список.Связанные списки предназначены для просмотра и доступа к данным, полезным для динамического выделения памяти для данных.