java中如何实现循环链表？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/27767778/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
How to implement circular linked list in java?
提问by SuperManEver
I read a book about "Data structures and algorithms" in which there is assignment which asks me to implement a circular linked list. This is a learning exercise and my code may not be of a very high standard.
我读了一本关于“数据结构和算法”的书，其中有一项任务要求我实现一个循环链表。这是一个学习练习，我的代码可能不是很高的标准。
The main idea behind my implementation of a circular linked list is to have a pointer which points to the last element and each time I add new item, the field 'next' of the last item will be refreshed to point to the newly added item.
我实现循环链表的主要思想是有一个指向最后一个元素的指针，每次我添加新项目时，最后一个项目的“next”字段将被刷新以指向新添加的项目。
The insertion method works fine, I can add item without any problems, but for some reason I can't delete items from the list.
插入方法工作正常，我可以毫无问题地添加项目，但由于某种原因，我无法从列表中删除项目。
Here is the code for 'Link' or 'Node':
这是“链接”或“节点”的代码：
public class Link {
public long data;
public Link next;
public Link(long val) {
data = val;
next = null;
}
public void displayLink() {
System.out.print(data + " ");
}
} // end class
This is the code for class which carries out the work, and the bug is obviously somewhere here:
这是执行工作的类的代码，错误显然在这里的某个地方：
public class CircularList {
Link first;
Link last;
public CircularList() {
first = null;
last = null;
}
public Link find(long key) {
Link current = first;
while(current.data != key) {
current = current.next;
}
return current;
} // end find
public Link delete() {
if(first.next == null)
last = null;
Link temp = first;
first = first.next;
return temp;
} // end delete
public boolean isEmpty() { return (first == null); }
public void insert(long val) {
Link newLink = new Link(val);
if(isEmpty())
last = newLink;
newLink.next = first;
first = newLink;
last.next = first;
} // end insert
public void displayAmount(int n) {
Link current = first;
while(n>0) {
current.displayLink();
current = current.next;
n--;
}
System.out.println("");
} // end displayAmount
} // end class
And the main app code:
和主要的应用程序代码：
public class App {
public static void main(String[] args) {
CircularList cl = new CircularList();
cl.insert(10);
cl.insert(20);
cl.insert(30);
cl.insert(40);
cl.displayAmount(6);
cl.delete();
cl.displayAmount(6);
}
} // end class
The display amount looks kind of silly, I just tried to avoid infinite loop and made something simple that just works.
显示数量看起来有点傻，我只是试图避免无限循环并制作一些简单的东西。
采纳答案by Paul Lo
Add last.next = firstbefore return tempin your delete() function:
在 delete() 函数last.next = first之前添加return temp：
public Link delete() {
if(first.next == null)
last = null;
Link temp = first;
first = first.next;
if(last != null)
last.next = first
return temp;
}
Updated:
更新：
I cannot find a scenario which satisfy first.next == null, and we should take into consideration calling delete() on an empty list.
我找不到满足 的场景first.next == null，我们应该考虑在空列表上调用 delete()。
public Link delete() {
Link temp = first;
if(first == null){
; // or you can throw some exception as a warning
}
else if(first==last){ // only one element
first = null; // reset to initial state
last = null;
}
else{
first = first.next;
last.next = first;
}
return temp;
}
回答by chiastic-security
Your delete()method doesn't handle the circularity of the list. The last element points to the first element; that also needs updating when the first element is deleted.
您的delete()方法不处理列表的循环性。最后一个元素指向第一个元素；删除第一个元素时也需要更新。
In other words, you need to set last.nextto point to the new firstrather than the old first.
换句话说，您需要设置last.next为指向 newfirst而不是 old first。
The other issue you have is that if you delete the final element (so that it's now empty), then you also need to set lastto null.
您遇到的另一个问题是，如果您删除最后一个元素（使其现在为空），那么您还需要last将null.
public Link delete() {
if (first.next == null) {
first = null;
last = null;
}
Link temp = first;
first = first.next;
last.next = first;
return temp;
}
