Как проверить, правильно ли связан двусвязный список в Java?

Question

Я реализую абстрактный тип данных для списков Coin объектов.Это должен быть список с двойной связью

Это поля:

private Coin prev, next; 
private Card head, tail;
private int size;

Теперь мой вопрос: как я могу проверить, правильно ли связаны монеты в двойной связи?list.

условие для проверки:

• , начиная с головы и, пройдя все элементы списка, проверяет наличие каждого элемента / монеты.
  • если да, то есть ли у следующего предыдущий?
    • если да, то оно не равно нулю и должно быть х.Затем увеличьте x
    • , если нет, тогда это не хорошо!
  • , если нет (/ если следующего элемента нет) ...
    • проверьте, если длина равна 1
      • , если это 1, то это хорошо!
      • , если другое, то это плохо!

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

(это не домашнее задание)

Answer 1

1. Создать набор для хранения повторяющейся монеты.Set iterated = new HashSet ();
2. Итерация из HEAD Coin, если следующее не присутствует в наборе, проверьте, является ли следующее пустым, если next пустым, тогда закончите проверку, в противном случае проверьте, текущее== current.next.previous, затем поместите текущую монету в набор.в противном случае есть некоторая ошибка в «двойной связи», вы можете вернуть false и остановить проверку.
3. , если следующий находится в наборе, тогда проверьте, является ли следующий монетой HEAD, если нет, то тамявляется частичным циклом в списке ссылок (не уверен, является ли это законным или нет, но это хороший вопрос)Если следующей является монета «ГОЛОВА», то это циклический двойной связанный список, поэтому предыдущая монета «ГОЛОВА» должна быть монетой «ХВОСТ».в противном случае это недопустимо.
4. Если вы достигнете нуля во время итерации, то это означает, что LOOP отсутствует, поэтому предыдущее значение HEAD должно быть NULL.
5. Сохраняйте счет во время итерации и проверьте, еслисчет правильный.
6. Проверьте голову и хвост соответственно.

Answer 2

Вы забыли несколько вещей:

1. В начале проверьте, чтобы увидеть head.prev == null.(Не может быть узла до head.)
2. В начале проверьте, чтобы увидеть tail.next == null.(Не может быть узла после tail.)
3. Сохраняйте количество узлов, чтобы, если число превышает size, список был неверным.
4. Если вы достигнете tail и ваш счет меньше size, тогда список неверен.
5. Если вы встретите какой-либо узел, кроме head, с нулевым указателем prev, то список неверен.
6. Если вы встретите какой-либо узел, кроме tail, который имеет нулевой указатель next, то список неверен.