Использование ListIterator в пользовательском LinkedList

У меня есть собственный, общий, одиночный LinkedList, который я создал сам. Я могу добавлять, удалять и т. д. в список просто отлично. Я хотел бы реализовать Java ListIterator в своем классе. Как мне начать это делать? Какие методы мне нужно добавить в мой класс? Все, что я могу найти в Интернете, - это примеры использования ListIterator в Java LinkedList по умолчанию, что мне не подходит. Спасибо!


java listiterator
person Nicklas Olsen    schedule 27.04.2011    source источник
comment
Вы не можете реализовать ListIterator разумным образом в односвязном списке, поскольку ListIterator требует поддержки обратного обхода, а это просто невозможно с односвязным списком!   -  person Joachim Sauer    schedule 27.04.2011
comment
@Joachim - это определенно возможно; просто ужасно неэффективно. Чтобы вернуться назад, вам просто нужно начать с начала списка и двигаться вперед, пока не достигнете узла, в котором текущий узел является следующим элементом.   -  person Ted Hopp    schedule 27.04.2011
comment
@ Шон - он также сказал, что обратный обход просто невозможен.   -  person Ted Hopp    schedule 27.04.2011
comment
@ Тед, технически это правда. Это невозможно, так что вам придется притворяться.   -  person Sean Patrick Floyd    schedule 27.04.2011
comment
@ Шон - я думаю, у нас очень разные представления о том, что означает «невозможно». :-)   -  person Ted Hopp    schedule 27.04.2011
comment
@Ted Я согласен, что формулировка Иоахима была плохой, потому что обратный обход можно сымитировать, начав с головы. Но вы должны согласиться с тем, что реальный обратный обход невозможен.   -  person Sean Patrick Floyd    schedule 27.04.2011
comment
@ Шон Ну, что значит настоящий? Хеш-таблица — это коллекция, которая может (более или менее) напрямую извлекать значение по заданному ключу. Означает ли это, что дерево AVL не может выполнять настоящий поиск, потому что оно должно начинаться с корня и выполнять множество переходов, чтобы получить значение для определенного ключа? Конечно, нет. Я вижу в этом одно и то же: характеристику структуры данных, которая делает обратный обход неэффективным.   -  person Ted Hopp    schedule 27.04.2011
comment
@Ted: моя формулировка могла быть неправильной, но: учитывая (только) последний узел односвязного списка, вы не можете пройти его назад к началу (исключая такие случаи, как одноузел список). Это мое определение разумной реализации.   -  person Joachim Sauer    schedule 28.04.2011

Ответы (5)


arrow_upward
1
arrow_downward

Вы создаете второй класс (обычно это вложенный класс вашего связанного списка), который реализует все функции интерфейса ListIterator. Обратите внимание, что некоторые функции (например, add и remove) являются необязательными, вы можете просто создать исключение UnsupportedOperationException. Ваш класс связанного списка должен реализовать методы listIterator() и listIterator(int), чтобы вернуть экземпляр вашего второго класса.

person Ted Hopp    schedule 27.04.2011

arrow_upward
1
arrow_downward

Вам следует реализовать итератор или ListIterator.

person lesmana    schedule 27.04.2011
comment
Ну интерфейс ListIterator по его вопросу, но да, вы правы. - person Liv; 27.04.2011

arrow_upward
0
arrow_downward

Найдите методы, которые есть у ListIterator. Вам нужно будет убедиться, что ваша версия имеет те же самые методы.

Если можете, найдите Interface, который использует ListIterator, и реализуйте этот интерфейс.

person cdeszaq    schedule 27.04.2011

arrow_upward
0
arrow_downward

Для повышения производительности вы можете реализовать ListIterator и сохранить «обратную» версию списка по мере его повторения. Это будет эмулировать двусвязный список, но только для итератора.

Однако, вероятно, безопаснее просто реализовать свой связанный список как двусвязный список внизу.

person Jeremy    schedule 27.04.2011

arrow_upward
0
arrow_downward

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

Либо сделайте свой список двусвязным, либо вам придется накидать UnsupportedOperationException на множество методов. (Или жить с производительностью O (n) в половине методов)

person Sean Patrick Floyd    schedule 27.04.2011
comment
Я не думаю, что исключение UnsupportedOperationException является законной реализацией previous(); это не один из методов, задокументированных как необязательные. Кроме того, почему одиночный (прямой) связанный список имеет производительность O (n) для next()? - person Ted Hopp; 27.04.2011
comment
@ Тед а) я знаю. Вот почему я бы сказал, что это не может быть действительной реализацией java.util.List b) хорошо, вы меня поняли: 5 из 9 методов будут работать разумно - person Sean Patrick Floyd; 27.04.2011