java - 循环链表中索引处的元素

Question

我正在阅读有关循环链表的内容。这是一段代码，我不明白它是如何工作的。

public int elementAt(int index){
        if(index>size){
            return -1;
        }
        Node n = head;
        while(index-1!=0){ // this line is unclear for me
            n=n.next;
            index--;
        }
        return n.data;
    }

我会以这种方式编写相同的代码:

public int elementAt(int index){
        if(index>size){
            return -1;
        }
        Node n = head;
        while(n.size != index){ // here is my change in the code
            n=n.next;
        }
        return n.data;
    }

这是完整的代码:http://algorithms.tutorialhorizon.com/circular-linked-list-complete-implementation/

我在第二个代码中做得对吗？

谢谢

Answer 1

示例代码使用从 1 开始的索引:1, 2, 3, ..., 大小。这在计算机科学中很奇怪，人们会期望:0，..，size-1。

不幸的是size是整个列表的属性，而不是列表中单个节点的属性。所以他们的解决方案很好。

尽管当索引 <= 0 时，美好的事情就会发生。

<小时/>

对于真正的循环列表，节点有一个previous字段。最后一个节点双向链接到第一个节点。

在这种情况下，您可以沿着下一个或上一个双向行走。然后，当索引 < size/2 时，将按 next 转发到索引，否则按 previous 返回大约 (size - index) 个步骤。为了采取最少的步骤。