我可以使用 java.util.LinkedList 来构造循环/循环链表吗？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/3742168/
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
Can I use java.util.LinkedList to construct a circular/cyclic linked list?
提问by Hristo
I would like to create a circular/cyclic linked list where the tail of the list would point back to the head of the list. So can I use java.util.LinkedListand modify the tail node after creation of the list to make it circular/cyclic? If so, can you show me some code on how that would happen?
我想创建一个循环/循环链表，其中列表的尾部将指向列表的头部。那么我可以java.util.LinkedList在创建列表后使用和修改尾节点以使其循环/循环吗？如果是这样，你能告诉我一些关于如何发生的代码吗？
If I can't use java.util.LinkedList, how should I create my own circular/cyclic linked list implementation? Can you show me the skeletons of how this implementation would look?
如果我不能使用java.util.LinkedList，我应该如何创建自己的循环/循环链表实现？你能告诉我这个实现的框架吗？
Let me know if you need more details and I'll clear up any confusion.
如果您需要更多详细信息，请告诉我，我会清除任何混淆。
采纳答案by Lajos Arpad
class ListNode {
public ListNode next;
public Object data;
public ListNode(Object data, ListNode next) {
this.next = next;
this.data = data;
}
}
class CircularLinkedList {
private ListNode head = null;
private int numberOfElements = 0;
private ListNode actualElement = null;
private int index = 0;
public boolean isEmpty() {
return (numberOfElements == 0);
}
public int getNumberOfElements() {
return numberOfElements;
}
public void insertFirst(Object data) {
if (!(isEmpty())) {
index++;
}
ListNode listNode = new ListNode(data, head);
head = listNode;
numberOfElements++;
}
public void insertAfterActual(Object data) {
ListNode listNode = new ListNode(data, actualElement.next);
actualElement.next = listNode;
numberOfElements++;
}
public boolean deleteFirst() {
if (isEmpty())
return false;
if (index > 0)
index--;
head = head.next;
numberOfElements--;
return true;
}
public boolean deleteActualElement() {
if (index > 0) {
numberOfElements--;
index--;
ListNode listNode = head;
while (listNode.next.equals(actualElement) == false)
listNode = listNode.next;
listNode.next = actualElement.next;
actualElement = listNode;
return true;
}
else {
actualElement = head.next;
index = 0;
return deleteFirst();
}
}
public boolean goToNextElement() {
if (isEmpty())
return false;
index = (index + 1) % numberOfElements;
if (index == 0)
actualElement = head;
else
actualElement = actualElement.next;
return true;
}
public Object getActualElementData() {
return actualElement.data;
}
public void setActualElementData(Object data) {
actualElement.data = data;
}
}
回答by Borealid
java.util.LinkedList is one of the Collections datatypes. The purpose of Collections is to provide utility structures, not bothering the programmer to worry about their internal implementation. If you musthave internals that work in a certain way, and the java.util ones do not guarantee that is how they work, then they are not for you.
java.util.LinkedList 是 Collections 数据类型之一。Collections 的目的是提供实用结构，而不是打扰程序员担心它们的内部实现。如果您必须拥有以某种方式工作的内部结构，并且 java.util 不能保证它们就是这样工作的，那么它们不适合您。
To implement a circular linked list, first create a ListNode class:
要实现循环链表，首先要创建一个 ListNode 类：
class ListNode {
ListNode next;
ListNode prev;
Object data;
}
Then store a ListNode head, and make sure prevof headpoints to the "end" of the list, and nextof the "end" points back to head. Honestly, though, there's little difference between a bidirectionally linked list keeping a tail pointer and a circular linked list.
然后存储ListNode head，并确保prev的head点到列表中的“结束”，并next“寿终正寝”点回head。不过，老实说，保留尾指针的双向链表和循环链表之间几乎没有区别。
回答by bragboy
回答by Tomá? Zálusky
For practical application (e.g. not only playing around or learning) I would personally prefer Guava's Iterables.cycle method - see http://guava-libraries.googlecode.com/svn/trunk/javadoc/com/google/common/collect/Iterables.html#cycle%28java.lang.Iterable%29.
对于实际应用（例如，不仅是玩耍或学习），我个人更喜欢 Guava 的 Iterables.cycle 方法 - 请参阅http://guava-libraries.googlecode.com/svn/trunk/javadoc/com/google/common/collect/Iterables .html#cycle%28java.lang.Iterable%29。
