Java编程-循环链表

Question

我正在尝试编写一个 java 类 CircularList，其中包含通常的 Node 内部类和实例变量：

Answer 1

好吧，我不会给你该类的完整实现，但我会给你一些建议。

1. 您不需要保留对最后一个元素的引用。将 Prev 和 Next 引用放置到您的节点上，最后一个节点将位于第一个。Prev

2. 除了循环列表没有结尾这一事实之外，它们与常规列表完全相同，但是您可以在其中找到最后一个项目，如下所示：

   节点 tmp = 第一个；

   while ( tmp.Next != null )
   tmp = tmp.Next;

在循环列表中，想法是这样的：

Node tmp = first;

while ( tmp.Next != first )
   tmp = tmp.Next;

因为你永远找不到指向空的节点，除非列表为空。最后一个建议是，如果您需要实现索引器，请记住在循环列表中不存在索引超出范围之类的情况，因为

list[count] = list[0] = list[count * k]

请记住这一点，因此计算这些方法的索引可能会非常棘手。对于正指数，主要思想是：

index = index % count;

对于负指数略有不同。我希望我的言语能够帮助到你。如果你想要一个实现，我相信如果你礼貌地询问谷歌，应该有一些:)

祝你好运！

Answer 2

我不确定你的问题是什么，你似乎拥有所需的一切。该链表与普通链表之间的唯一区别在于添加到末尾。

在常规链表中，您将创建一个新节点并使最后一个元素指向该节点。在这种情况下，您可以将•Last 节点中的指针更改为指向新节点，并使新节点指向•First。

删除的工作方式与普通链表相同。每当您想要删除一个节点时，您都​​可以找到哪个其他节点指向该节点（无论是前一个节点，还是在删除第一个节点的情况下，请选中“最后一个”），并使其指向被删除的节点所指向的位置。

如果这不能解决您的问题，请告诉我，我会尽力提供帮助。

刚刚注意到有人已经问了完全相同的问题：
我可以使用 java.util .LinkedList构造循环链表？

Answer 3

提示...循环列表应该有下一个和上一个而不是第一个和最后一个。逻辑很重要

Answer 4

class Node    {
    int value;
    Node next;
    Node prev;
    Node(int initialValue)    {
        value = initialValue;
        next =  null;
        prev = null;
    }
    public int getValue()    {
        return this.value;
    }
}

class NodeList    {
    Node pointer;
    NodeList()    {
        pointer = null;
    }
    public void insertNode(int nodeValue)    {
        Node newNode = new Node(nodeValue);
        if( pointer == null )    {
            newNode.next = newNode;
            newNode.prev = newNode;
        }else if( pointer.next == null && pointer.prev == null && pointer != null )    {
            newNode.next = pointer;
            newNode.prev = pointer;
            pointer.prev = newNode;
            pointer.next = newNode;
        }
        else if( pointer != null )    {
            newNode.next = pointer.next;
            newNode.prev = pointer;
            pointer.next.prev = newNode;
            pointer.next = newNode;
        }
        pointer = newNode;
        System.out.println(“Successfully inserted : ” + pointer.getValue());
    }
    public void printRing( boolean direction )    {
        Node tempNode = pointer;
        do    {
            System.out.println( “Value = ” + tempNode.getValue() );
            tempNode = direction ? tempNode.next : tempNode.prev;
        } while( tempNode.value != pointer.value );    
    }    
}