algorithm - 如何检查双向链表是否在java中正确链接？

Question

我正在为 Coin 对象列表实现一个抽象数据类型。这应该是一个双向链表

这些是字段:

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

现在，我的问题是如何检查硬币是否在双向链表中正确链接。

要检查的条件:

• 从头部开始，遍历列表中的所有元素，检查每个元素是否有下一个元素/硬币。
  • 如果是，下一个有前一个吗？
    • 如果是，则它不为空，并且必须是 x。然后，增加x
    • 如果不是，那就不好了!
  • 如果没有(/如果没有下一个元素)...
    • 检查长度是否为1
      • 如果是 1，那很好!
      • 如果是其他的，那就不好了!

(所有这些都应该在一个没有参数的 bool 方法中)。此方法只是检查列表是否采用正确的链接格式(双向链表)

(这不是作业题)

Answer 1

你忘记了几件事:

1. 开始时，检查 head.prev == null。 (在 head 之前不能有节点。)
2. 开始时，检查 tail.next == null。 (在 tail 之后不能有节点。)
3. 保持节点计数，以便如果计数超过大小，则列表不正确。
4. 如果到达 tail 并且计数小于 size，则列表不正确。
5. 如果您遇到除 head 之外的任何节点具有空的 prev 指针，则列表不正确。
6. 如果您遇到除 tail 之外的任何节点都有一个空的 next 指针，则该列表不正确。