Круговой связанный список Java без головы или хвоста?

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

«Круговой список не нуждается в голове или хвосте. Вместо этого вам нужна только ссылка на текущий узел, который является nextNode, возвращаемым Iterator. Реализуйте такой класс. Для непустого списка Iterator.hasNext метод всегда будет возвращать true."

Я не совсем уверен, как мне подойти к этому.


java iterator circular-list
person smitty werbenjagermanjensen    schedule 02.03.2014    source источник
comment
Конкретно на чем вы застряли?   -  person ylun.ca    schedule 02.03.2014
comment
Я понимаю, как сделать один связанный список, но я не понимаю, как я могу сделать его круговым связанным списком без какой-либо ссылки на головной или хвостовой узел. Это единственное упоминание о круговых связанных списках во всей книге.   -  person smitty werbenjagermanjensen    schedule 02.03.2014
comment
Хорошо, если вы думаете о круге, в какой точке находится начало и конец круга?   -  person MxLDevs    schedule 02.03.2014

Ответы (2)


arrow_upward
2
arrow_downward

Упражнение составлено таким образом, чтобы не ограничивать вас в принятии решения о реализации: вместо того, чтобы предписывать конкретное решение, оно позволяет вам реализовать список наиболее удобным для вас способом.

У вас должен быть указатель на список, но, поскольку список круговой, ему не нужно указывать куда-то конкретно. Поскольку он не указывает ни на голову, ни на хвост, вы можете назвать его next и оставить его указывающим на любой элемент, который вы считаете удобным:

  • После вставки next может указывать на элемент, который вы только что вставили.
  • После удаления next может указывать на элемент после или перед удаленным
  • После поиска next может остаться без изменений
person Sergey Kalinichenko    schedule 02.03.2014

arrow_upward
0
arrow_downward

Чтобы преобразовать ваш односвязный или двусвязный список в циклический, свяжите голову и хвост. Теперь структура списка циклическая, поэтому нет необходимости иметь голову / хвост. Потому что все узлы взаимосвязаны, и поэтому ни один указатель не имеет следующего узла как нулевого.

Круговой список бывает двух типов. Один циклический список — имеет только метод hasNext() Двойной циклический список — имеет hasNext() и hasPrev()

Вышеупомянутые методы являются способами обхода кругового связанного списка.

person user3256147    schedule 02.03.2014