Задали мне недавно одну задачку, над которой маюсь уже несколько дней. Имеется односвязный список, который используется в многопоточной системе, и изменяется несколькими потоками. Нужно определить, является ли список зацикленным(последний элемент указывает на первый).
Вариант с приравниванием рефералов по двум маркерам аля на каждый оборот внешнего цикла, берущего i-й элемент, внутренним циклом выбираются и сравниваются все последующие рефералы, не подошел. Уже думал над "локальной интерпретацией" этой методы, где при выборке каждого последующего элемента из списка идет сравнение с последующими рефералами, но есть сомнения касательно правильности подхода.
Был бы благодарен за любые предложения касательно решения сей задачи.
Алгоритм следующий:
1) Каждый элемент списка помещаем в нашу обертку, одним из полей которой будет являться ThreadLocal переменная - флаг. Изначально флаг выключен.
2) Когда мы посещаем элемент, поднимаем флаг.
3) Если нашли поднятый флаг - список зациклен. Если уперлись в next==null - нет.
Если такое действие над списком нужно производить не 1 раз, тогда у поднятого флага должно быть 2 значения, которые мы чередуем при каждом запуске.
Касательно п.1, то изначально был набросок варианта с использованием HashSet'а с целью вычисления повторяющегося элемента, вычисляемого выводом метода add, мол "заливать в Set либо до next==null, либо до add-->false.
Вариант конечно, но по подсчету шагов можно и просто при каждом вызове метода получения элемента
делать проверку, прогоняя по циклу аля while(next!=null), с целью упереться либо в стену null, либо всетаки получить next==this, но незнаю насколько этот подход "гуманен".
Armitage89: сразу вспомнилась недавняя лекция на хекслете по спискам Erlang. Они там тоже однонаправленные и добавление новых элементов происходит только в начало, потому что это не требует менять старый список, чтобы получить новый, при этом сохранив одноразовость переменных (и ссылочную прозрачность для многопоточной работы): https://ru.hexlet.io/lessons/practical_erlang_list...
UA3MQJ: хм. А согласно определению википедии, односвязный список имеет характеристику к-ва элементов. Тоись на этапе считывания какбы можно пойти путем пересчета рефералов next. Правда по к-ву шагов, с учетом того, что конструкция может двигаться в момент проверки, это будет эквивалентным. Да и к-во элементов - весч не сталая, а значит начав с 40 элементов, на середине пробежки их может оказаться 30, и... приехали.
предположительно, у нас есть класс, принимающий объекты тематики "список"(аля реализующий интерфейс OneWayList). При этом заранее неизвестно что именно это за реализация - конечная\замкнутая. Отсюда нужно сделать соответствующие телодвижения по определению "с чем имеем дело".
Правда это всё в рамках моих догадок касательно заданного текста задачи.
