Java中的循环LinkedList实现 [英] Circular LinkedList implementation in Java
问题描述
这是一项任务。我必须创建一个循环链表并删除列表中的每三个数字。当我的程序到达列表的末尾时，它应该返回到头部并继续该过程，直到只剩下一个数字。
This is an assignment. I have to create a circular linked list and remove every third number in the list. When my program reaches the end of the list it should go back to the head and continue the process until only one number remains.
我在网上搜索了一些其他参考文献书但无法解决我的问题。我发现的大多数参考文献都说如下：
I've searched online and some other reference books but couldn't solve my problem. Most of the references that I've found say things such as:
除了循环列表没有结束这一事实外，它们完全是与常规列表相同
Beside the fact that circular lists have no end, they are quite the same as regular lists
或（取自我的教科书）：
or (taken from my textbook):
如果最后一个节点的后续节点是第一个
A singly-linked list is circularly linked if the successor of the last node is the first
，则单链表是循环链接的但是这些不要告诉怎么做。我也试过使用我在这个网站上找到的一些代码，但是没有清楚。
But these don't tell how to do it. I've also tried using some code I found on this site, but that did not clear anything up.
我可以创建一个列表（我不知道）知道它是否是循环链表并显示它，但元素的顺序很奇怪：
I can get as far as creating a list (I don't know if it's a circular linked list) and displaying it, but the order of the elements is strange:
- 如果列表有6个数字，列表将是1,6,5,4,3,2。
- 如果列表有8个数字，列表将是1,8,7,6,5,4 ，3,2。
如果没有正确的列表，我可以正确删除。以下代码有什么问题：
Without getting a correct list, I can do the deletion properly. What is wrong with the following code:
public class LastNumberDemo {
public static void main(String[] args) {
LastNumberNode ll=new LastNumberNode();
System.out.println("how long is the list: ");
Scanner keyboard = new Scanner(System.in);
int input = keyboard.nextInt();
if(input<=0) {
System.out.println("no number to creat list");
}
if(input==1) {
System.out.println("The Last number is 1.");
}
else {
String[] n=new String[input];
for(int index=0; index<n.length; index++)
n[index]=Integer.toString(index+1);
for(String e:n)
ll.add(e);
System.out.print("The list contains: \n");
ll.print();
System.out.print("\nThe last number is: ");
ll.remove();
ll.print();
}
}
}
//The circular linked list class
class LastNumberNode{
private class Node{
String value;
Node next;
Node(String val, Node n){
value = val;
next = n;
}
Node(String val){
value=val;
next=null;
}
} //This brace was missing - Edd
private Node first;
public LastNumberNode(){
first = null;
}
public boolean isEmpty(){
return first == null;
}
public int size(){
int count = 0;
Node p = first.next;
while (p != first){
count ++;
p = p.next;
}
return count;
}
public void add(String e) {
Node p=new Node(e);
if(first==null){
first=p;
first.next=first;
}
else{
first.next=new Node(e,first.next);
}
}
public void remove(){
while(size()>0){
Node target=first.next.next;
Node temp=first;
target=target.next;
last.next=temp;
first=target;
}
}
public void print(){
Node ref=first;
for(int index=-1; index<size();index++)
System.out.print(ref.value+" ");
ref=ref.next;
}
} //Extra brace removed - Edd
推荐答案
当您向列表添加新的节点时，将新的节点添加到第二个position（ first.next 指向新添加的节点），但这个新添加的节点有 first 作为其下一个节点，使列表的其余部分未被引用（因此垃圾收集和销毁）。使用添加方法，您的列表不可能包含0,1或2以外的任何内容节点秒。将新的 Node 添加到列表中间有点奇怪;要么将它添加到前面（ newnode.next = first; first = newnode; last.next = first; ），要么保留对列表后面的引用（如其他人建议），并在那里添加。
When you add a new Node to your list, you add the new Node into the second position (first.next points to your newly added node), but this newly added node has first as its next node, leaving the rest of the list unreferenced (And thus garbage-collected and destroyed). With your add method as it is, it's impossible for your list to contain anything other than 0, 1 or 2 Nodes. It's a bit odd to add new Node into the middle of the list; either add it to the front (newnode.next = first; first = newnode; last.next = first;), or keep a reference to the back of the list (as others have suggested), and add it there.
我个人重构 LastNumberNode 类，以便它有以下方法来操作链表：
Personally, I'd restructure the LastNumberNode class so that it has the following methods for manipulating the linkedlist:
-
private void addNode（Node node） -
private void removeNode（Node node） -
private节点findNode（Node nextNode）
private void addNode(Node node)private void removeNode(Node node)private Node findNode(Node nextNode)
如果您保持对列表中最后一个节点的引用，那么 addNode（节点节点）方法可能如下所示：
If you maintain a reference to the last node in the list then your addNode(Node node) method can be something like the following:
if(isEmpty()) {
first = node;
last = node;
}
else {
Node tail = last;
tail.next = node;
node.next = first;
last = node;
}
removeNode（节点节点）基于以下内容：
Node prevNode = findNode(node);
if(node == first) {
first = node.next;
last.next = first;
}
else if(node == last) {
prevNode.next = first;
last = prevNode;
}
else {
prevNode.next = node.next;
}
如果我要实施这个，我可能会减少使用这种方法列出一个节点：
If I were to implement of this I'd probably do the reduction of the list down to a single Node using this sort of approach:
public String reduceList() {
Node curNode = first;
while(first != last) {
removeNode(curNode.getNext().getNext());
curNode = curNode.getNext().getNext();
}
return first.getValue();
}
作为最后一点，我不打算用序号来填充数组然后走它以将元素添加到列表中。我只是直接寻找以下内容：
As a final point, I wouldn't bother filling an array with sequential numbers and then walking it to add the elements to your list. I'd just go straight for something like the following:
for(int i = 1; i <= input; i++) {
linkedlist.add(new Integer(i).toString());
}
这篇关于Java中的循环LinkedList实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
